Inplace Quicksort Implementation

[Cervantes]

My first attempt at implementing quicksort in Java. I did it completely in place, which is nice.

Java:

public class Sort {   public static void quick(int[] arr) {     quickAux(arr, 0, arr.length - 1);   }     private static void quickAux(int[] arr, int start, int end) {     if (start < end) {       int pivot = arr[end];       int i = start;       int j = end;       while (i != j) {         if (arr[i] < pivot) {           i = i + 1;         }         else {           arr[j] = arr[i];           arr[i] = arr[j-1];           j = j - 1;         }       }       arr[j] = pivot;       quickAux(arr, start, j-1);       quickAux(arr, j+1, end);     }   }     public static void printArr(int[] arr) {     for (int i = 0; i < arr.length; i++) {       System.out.print(arr[i] + "|");     }     System.out.println("");   }     public static void main(String[] args) {     int[] a = {4,8,6,7,3,1,3,13,2,5,-4};     quick(a);     printArr(a);   } }

While doing this, I questioned why the code in the main method there works, but

Java:

quick({4,8,6,7,3,1,3,13,2,5,-4});

fails.

[bugzpodder]

most quicksorts are in place... try a inplace merge sort

[Cervantes]

I did. It wasn't loads of fun.

[wtd]

The second attempt failed because:

code:

{4,8,6,7,3,1,3,13,2,5,-4}

Is not a Java array literal. It's just an exception in Java's syntax used to make C and C++ programmer's slightly less disgruntled when they have to use Java.

code:

quick(new int[] {4,8,6,7,3,1,3,13,2,5,-4});

Oh, and do try to make it generic. Either by sorting any Comparable object, or by using Java 1.5 generics.

[klopyrev]

I was thinking about it, but I can't think of anyway to implement Mergesort in place? Any hints?

KL

[Cervantes]

wtd, thanks for enlightening me on that. Of course it makes sense now. I should have known to include the new int[].

I did this simply with integers simply because this was done to study for my CS exam and we didn't have to know about Comparable or generics for the exam. I know it's nothing more than an excuse, but it was rather necessary, given my time constraints. =/



KL, I thought of a way to do it, but it involved doing some shifting.

The trouble is writing a function that takes your array, and 3 (or 4 if you really want to be general) integers representing start, mid, and end, and sorts it, assuming that the data from start to mid is sorted and the data from mid+1 to end is sorted.

Here's an example. I hope you can pick up on the syntax convention I'll use:

[6 8 | 7 9] (compare 6 and 7)
6 [8 | 7 9] (compare 8 and 7)
6 7 [8 | 9] (compare 8 and 9)
6 7 8 [| 9] (throw in the rest of the second array)
6 7 8 9

Another example:
[3 4 | 1 2] (compare 3 and 1)
1 [3 4 | 2] (compare 3 and 2)
1 2 [3 4|] (throw in the rest of the first array)
1 2 3 4


The second example in particular illustrates that some shifting will need to be done. For example, when you move 1 to the front, you have to shift both the 3 and the 4 one over.

That's why I said this wasn't loads of fun. Maybe there's a better way to do it though.

[klopyrev]

I was thinking about that, but that ruins the runtime of mergesort completely. It leaves you with a runtime of O(N^2logN), which is worse than bubblesort.

KL