Quick sort programmed in C

Question

I am reading ANSI C on K & R. I came across a qsort program. I want to help a little bit. Suppose I have 9 elements with an index of 0-> 8. Please read the comments to see if I understand this correctly. Thanks so much for your efforts.

void qsort(int v[] , int left, int right) { int i, j, last; void swap(int v[], int i, int j); if(left >= right) /*if the array has only one element return it*/ return; swap(v,left, (left+right)/2); /* now, left=(left+right)/2= 0+8/2= 4 we have 4 as left*/ last= left; /* putting left = last of the first partition group ie last=4*/ for(i=left+1; i<=right,i++) /* now looping from 4+1=5 to 8 with increment of 1*/ if(v[i] < v[left]) /*if value at 5th is less than value at 4th */ swap(v, ++last, i); 

I have a problem in this last step of the swap. Since my values ​​suggest swap ++ 4, i.e. before i i.e. 4 + 1 = 5 (replacing 5 positions with 5?). How can I understand that? Should there be a replacement between 4 and 5, not 5 and 5?

the code continues

 swap(v,left, last); qsort(v,left,last-1); qsort(v,last+1,right); } 

Answer 1

Firstly, you have a slight misconception regarding the swap function. Let's say the function prototype is

 swap(int array[], int i, int j) 

The swap function replaces the numbers in the location array [i] and array [j]. Thus, the swap function changes the elements in the array. So the line is -

 swap(v, left, (left + right) / 2); 

Means that the middle element in the array is replaced by the left-most element. Obviously, quicksort takes the middle element as a hinge. This exchange does not affect local variables or parameters. According to your data entry example, the value is 'left' = 0 and the value is right = '8', even after replacement. Here you are confused. Array elements are swapped, not variable values. So now the line is -

 last = left; 

does, the "last" indicates the location of the rotation ("left"), so here the value of "last" = 0 is not 4. So, the loop,

 for(i = left + 1; i <= right; i++) 

It works from i = 1 to 8. By the way, you forgot the semicolon ..! Then the line,

 if(v[i] < v[left]) 

checks if the current element ('v [i]') is smaller than the pivot point ('v [left]') or not. Then, respectively, swaps the smaller elements, as in a line,

  swap(v, ++last, i); 

from the location (last + 1) to the place where it increases. So, the elements to the left of the "last" are smaller than the pivot points, and the elements to the right are larger. I think that you are missing one more line, where we return the anchor point to the middle, which was in the place "v [left]" during the execution of the algorithm. Then recursive calls play their part. If you're looking for help sorting quickly, this is a good place to start!

Hope my answer helped you, if so, let me know ..! ☺