Why does this quicksort work?

Question

I believe this Quicksort deployment approach is confusing and flawed, but it seems to work. I mean this pseudo code . Note : they also have a C implementation at the end of the article, but it is very different from their pseudo-code, so I don't care.

I also wrote this in C, like this, trying as much as possible to stay true to the pseudo-code, even if it means that you are doing some strange C stuff:

#include <stdio.h> int partition(int a[], int p, int r) { int x = a[p]; int i = p - 1; int j = r + 1; while (1) { do j = j - 1; while (!(a[j] <= x)); do i = i + 1; while (!(a[i] >= x)); if (i < j) { int t = a[i]; a[i] = a[j]; a[j] = t; } else { for (i = 1; i <= a[0]; ++i) printf("%d ", a[i]); printf("- %d\n", j); return j; } } } int main() { int a[100] = //{8, 6,10,13,15,8,3,2,12}; {7, 7, 6, 2, 3, 8, 4, 1}; partition(a, 1, a[0]); return 0; } 

If you run this, you will get the following output:

1 6 2 3 4 8 7 - 5

However, this is wrong, isn't it? It is clear that a[5] does not have all the values ​​before it is lower, since a[2] = 6 > a[5] = 4 . Not to mention that 7 must be rotary (initial a[p] ), and yet its position is incorrect and lost.

The following partition algorithm is taken from wikipedia :

 int partition2(int a[], int p, int r) { int x = a[r]; int store = p; for (int i = p; i < r; ++i) { if (a[i] <= x) { int t = a[i]; a[i] = a[store]; a[store] = t; ++store; } } int t = a[r]; a[r] = a[store]; a[store] = t; for (int i = 1; i <= a[0]; ++i) printf("%d ", a[i]); printf("- %d\n", store); return store; } 

And produces this conclusion:

1 6 2 3 8 4 7 - 1

What is the correct result, in my opinion: the axis ( a[r] = a[7] ) has reached the final position.

However, if I use the initial sectioning function in the following algorithm:

 void Quicksort(int a[], int p, int r) { if (p < r) { int q = partition(a, p, r); // initial partitioning function Quicksort(a, p, q); Quicksort(a, q + 1, r); // I'm pretty sure q + r was a typo, it doesn't work with q + r. } } 

... this seems to be the correct sorting algorithm. I tested it on a variety of random inputs, including all 0-1 arrays of length 20.

I also tried using this separation function for a selection algorithm in which it was not able to get the correct results. It seems to work, and it even works very fast as part of a quick sort algorithm.

So my questions are:

• Can someone post an example where the algorithm does NOT work?
• If not, then why does it work, as part of the section seems wrong? Is this another separation approach that I don't know about?

Answer 1

I think the partition is correct. 7 - a core. The original array is divided into an auxiliary array of length 5, containing elements less than or equal to 7, and an auxiliary array of length 2, containing elements greater than or equal to 7.

Answer 2

Continued from above here is what should look like

 void swap(int *a, int *b) { int x; x = *a; *a = *b; *b = x; } int partition(int s[], int l, int h) { int i; int p;/* pivot element index */ int firsthigh;/* divider position for pivot element */ p = h; firsthigh = l; for (i = l; i < h; i++) if(s[i] < s[p]) { swap(&s[i], &s[firsthigh]); firsthigh++; } swap(&s[p], &s[firsthigh]); return(firsthigh); } void quicksort(int s[], int l, int h) { int p;/* index of partition */ if ((h - l) > 0) { p = partition(s, l, h); quicksort(s, l, p - 1); quicksort(s, p + 1, h); } } int main() { int a[100] = //{8, 6,10,13,15,8,3,2,12}; {7, 7, 6, 2, 3, 8, 4, 1}; quicksort(a, 0, 7); return 0; } 

Answer 3

From Wikipedia (I emphasized the part that, in my opinion, relates directly to your question):

This is the internal section of the algorithm. It divides the part of the array between the left and right indexes, inclusive, by moving all elements less than or equal to array [pivotIndex] before the start of the subarray, leaving more and more elements to follow. the process also finds the final for the rotation element that it returns. It temporarily moves the rotary element to the end of the subarray so that it does not hit the path. Because it uses only exchanges, the final list has the same elements as the source list. notice that the item can be exchanged several times before last place. It should also be noted that in the case of summary duplicates in the input array, they can be distributed in the left subarray, possibly in random order. This does not mean partitioning, since the sorting will be changed and, finally, “glue” them together.

Maybe this is what you were missing?

Answer 4

You lose the meaning between the index of the element and the value of iten

Look at your headline

 int partition(int a[], int p, int r) ; 

Now, if we change the data type in array a to some weird data type, you will see the problem

 int partition( Otherdatatype a[], int p, int r) ; 

You call a function from your main page with

 partition(a, 1, a[0]); 

See problem a [0] - the value of the record in [0], not the index value.

Imagine that [0] has a value of 200 in your code, simply changing the value of the first element to 200, and you get a run-time error of "attempting to access memory out of range" because if you follow through [0] = 200, which is passed to the partition as the value of r, then follows what happens inside the partition.

It should be remembered that this is a sorting routine in the section header, the list in array a may not be the same type as the indexes. The p and r of your header are explicitly indexes related to the position of the index and this is the list to be sorted.

So your main start in sorting

 partition(a, 0, items_in_array-1); 

Do you understand why? Array a runs from [0] ... a [items_in_array-1]

So, in the above example, you preloaded 8 values ​​into your array so that your section call from main should be

 partition(a, 0, 7);