----------------------------------- Cervantes Tue Apr 17, 2007 5:16 pm Inplace Quicksort Implementation ----------------------------------- My first attempt at implementing quicksort in Java. I did it completely in place, which is nice. public class Sort { public static void quick(int While doing this, I questioned why the code in the main method there works, but quick({4,8,6,7,3,1,3,13,2,5,-4}); fails. ----------------------------------- bugzpodder Tue Apr 17, 2007 5:32 pm RE:Inplace Quicksort Implementation ----------------------------------- most quicksorts are in place... try a inplace merge sort ----------------------------------- Cervantes Tue Apr 17, 2007 6:33 pm RE:Inplace Quicksort Implementation ----------------------------------- I did. It wasn't loads of fun. ----------------------------------- wtd Wed Apr 18, 2007 1:22 pm RE:Inplace Quicksort Implementation ----------------------------------- The second attempt failed because: {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. 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 Wed Apr 18, 2007 3:42 pm 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 Wed Apr 18, 2007 10:25 pm 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 Thu Apr 19, 2007 7:44 am 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