Inplace Quicksort Implementation
Author 
Message 
Cervantes

Posted: Tue Apr 17, 2007 5:16 pm Post subject: Inplace Quicksort Implementation 


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.






Sponsor Sponsor



bugzpodder

Posted: Tue Apr 17, 2007 5:32 pm Post subject: RE:Inplace Quicksort Implementation 


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






Cervantes

Posted: Tue Apr 17, 2007 6:33 pm Post subject: RE:Inplace Quicksort Implementation 


I did. It wasn't loads of fun.






wtd

Posted: Wed Apr 18, 2007 1:22 pm Post subject: RE:Inplace Quicksort Implementation 


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

Posted: Wed Apr 18, 2007 3:42 pm Post subject: Re: Inplace Quicksort Implementation 


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






Cervantes

Posted: Wed Apr 18, 2007 10:25 pm Post subject: RE:Inplace Quicksort Implementation 


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

Posted: Thu Apr 19, 2007 7:44 am Post subject: Re: Inplace Quicksort Implementation 


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







