# qsort example

• 10-13-2010
blob84
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;     }```
• 10-13-2010
Salem
0 and 5 would be good.
That is, the subscripts of the two ends of the array you want to sort.
• 10-13-2010
blob84
It still not working.
• 10-13-2010
Salem
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.
• 10-13-2010
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.
• 10-13-2010
whiteflags
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.
• 10-14-2010
blob84
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;     }```
• 10-14-2010
```//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); }```