I recently started to learn about the Quicksort. The textbook showed an example of recursive quicksort. However, even after copying everything from the textbook (so please forgive me if the name of the array and methods are not appropriate), the result was not so good.
It seemed like the algorithm couldn't reach the second partition of the array.
Here is the example from the textbook:
1 class Quicksort {
2 static void qsort(int items[]) {
3 qs(items, 0, items.length-1);
4 }
5 }
6
7
8 private static void qs(int items[], int left, int right) {
9 int i, j;
10 int x, y;
11
12 i = left; j = right;
13 x = items[(left+right)/2];
14 System.out.println("Comparand is " + x);
15
16 do {
17 while((items[i] < x) && (i < right)) i++;
18 System.out.print(items[i]);
19 while((x < items[j]) && (j > left)) j--;
20 System.out.println(" and " + items[j]);
21
22 if(i <= j) {
23 y = items[i];
24 items[i] = items[j];
25 items[j] = y;
26 i++; j--;
27 }
28 } while (i <= j);
29
30 for(i = 0; i < items.length; i++)
31 System.out.print(items[i]);
32 System.out.println("");
33
34 if(left < j) qs(items, left, j);
35 if(i < right) qs(items, i, right);
36 }
37 }
...and here is the result:
Original array: 3164597
Comparand is 4
6 and 4
3146597
Comparand is 1
3 and 1
1346597
Sorted array: 1346597
Please let me know which part is wrong and how should I fix it. Thank you.
Here is the culprit:
for(i = 0; i < items.length; i++) // line 30, i == 0
System.out.print(items[i]); // line 31
System.out.println(""); // line 32, i == items.length
You're using a local variable i to loop through your array. But by doing so, you overwrite the value of i set by the partition loop above.
Use another variable to loop through your array:
for (int t = 0; t < items.length; t++)
System.out.print(items[t]);
System.out.println("");
Or better yet, use a foreach loop to avoid this type of errors:
for (item : items)
System.out.print(item);
System.out.println("");