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.

It still not working.

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.

Given that the array has five elements, using 0 and 4 as subscripts you want to sort would be better. The fifth subscript is actually the sixth element counting from one, and so on.

This is not my code, i found it in the C language book, by Kernighan and Ritchie.
I was calling the function with qsort instead of quicksort.
It works very well.
But the code is not very clear, i should study it.

Code:

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

int main(void) {
    int arr[] = { 3, 5, 1, 2, 4 };
    qicksort( arr, 0, 4 );    
    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;
    }

Yeah, that's where I and qsort() have our differences.

Because to me, Quicksort is a classic "divide and conquer" algorithm. What qsort does is to move the pivot out of the way, and then partition the whole sub-array space. (while i < right

What I like to have it do, is to leave the pivot value where it started from, and then stop the partitioning, when the left index is greater than the right index (while i < j).

The result is about the same, but the second version is quicker, in my several tests, and easier to understand, imo.

Code:

//Quicksort w/o a separate compare function :)
void quicksort(int A[], int lo, int hi) {
  int i, j, pivot, temp;

  if(lo == hi) return; 
  i=lo; 
  j=hi;
  pivot= A[(lo+hi)/2]; 

  /* Split the array into two parts */
  do {    
    while (A[i] < pivot) i++; 
    while (A[j] > pivot) j--;
    if (i<=j) {
      //swap(A, i, j);   //this line works fine if you have a separate swap function
        temp= A[i];     //rem out the swap code on these 3 lines of code
        A[i]= A[j];
        A[j]=temp;
      i++;
      j--;
    }
  } while (i<=j);
    
  if (lo < j) quicksort(A, lo, j);
  if (i < hi) quicksort(A, i, hi);
}