Thread: qsort example

Hi, i found this piece of code in K&R book, but i have not understood how it works, page 74,
for example, what represent "int left, int right" variables and how should i use it?
I know this is not the complete qsort code inside standard library.

Code:

/* qsort: sort v[left]...v[right] into increasing order */
void qsort(int v[], int left, int right)
{
int i, last;
void swap(int v[], int i, int j);
if (left >= right) /* do nothing if array contains */
return;
/* fewer than two elements */
swap(v, left, (left + right)/2); /* move partition elem */
last = left;
/* to v[0] */
for (i = left + 1; i <= right; i++) /* partition */
if (v[i] < v[left])
swap(v, ++last, i);
swap(v, left, last);
/* restore partition elem */
qsort(v, left, last-1);
qsort(v, last+1, right);
}

/* swap: interchange v[i] and v[j] */
void swap(int v[], int i, int j)
{
int temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}

i tried to implement it :
I renamed qsort to quicksort, because it conflicts with the qsort in the standard library.

Code:

#include <stdio.h>
void qicksort( int v[], int left, int right );

int main(void) {
    int arr[] = { 3, 5, 1, 2, 4 };
    qsort( arr, 0, 5 );    
    int i;
    for ( i = 0; i < 5; i++ )    
        printf("num=%d\n",  arr[i] );
}

    /* qsort: sort v[left]...v[right] into increasing order */
    void qicksort(int v[], int left, int right) {
        int i, last;
        void swap(int v[], int i, int j);
        if (left >= right) /* do nothing if array contains */
        return;
        /* fewer than two elements */
        swap(v, left, (left + right)/2); /* move partition elem */
        last = left;
        /* to v[0] */
        for (i = left + 1; i <= right; i++) /* partition */
        if (v[i] < v[left])
        swap(v, ++last, i);
        swap(v, left, last);
        /* restore partition elem */
        qicksort(v, left, last-1);
        qicksort(v, last+1, right);
        }

    /* swap: interchange v[i] and v[j] */
    void swap(int v[], int i, int j) {
        int temp;
        temp = v[i];
        v[i] = v[j];
        v[j] = temp;
    }

0 and 5 would be good.
That is, the subscripts of the two ends of the array you want to sort.

Well that is unfortunate.

Does it compile - if not, post error messages
Does it run - if not, post error messages
Are the results wrong - post results

We're here to guide you towards an answer, but you need to do actual work of investigation and reporting feedback.

We don't typically take your first code, spend however long it takes to polish it to perfection and then post the result you can just run to teacher with.

This is the part that I find very suspect:

Code:

        for (i = left + 1; i <= right; i++) /* partition */
        if (v[i] < v[left])
        swap(v, ++last, i);
        swap(v, left, last);
        /* restore partition elem */
        qicksort(v, left, last-1);
        qicksort(v, last+1, right);
        }

A few things:
* This should be a do loop or while loop: ie.:

Code:

do {
   //inside the loop, you have two while loops, which increment or decrement
   //the left (i) and right (j) indeces:
  while(v[i] < your pivot) ++i;
  while(v[j] > your pivot) --j;
  if(i <= j) {
      swap(your v[i] with v[j]);
}while(i<=j);

//two calls for the partitions of the array, here

Your logic is working with i in a mechanical way, and iteratively (imo), rather than flexibly, in a recursive way. Also, you don't do anything with j. You only work with left, right, and i.

Since you're not swapping v[i] with v[j], I don't understand your swaps.