Results 1 to 5 of 5
Thread: my Quicksort attempt has failed
 11152009, 06:13 AM #1Member
 Join Date
 Feb 2009
 Posts
 12
 Rep Power
 0
my Quicksort attempt has failed
I have an array of intergers i need to sort with quicksort. I tried using what is on Wikipedia: en.wikipedia.org/wiki/Quicksort ...but it did not go so well. I am getting Array out of bound errors. And I kind of winged it, so there could be a whole bunch of errors. Dunno.
Java Code:public static int[] quickSort(int[] list) { int[] L = new int[list.length]; int[] G = new int[list.length]; int[] all = new int[list.length]; int lcount, gcount; lcount = gcount = 0; if(list.length <= 1) return list; int p = list[list.length1]; for(int i = 0; i < list.length; i++) { if(list[i] <= p) { L[lcount] = list[i]; lcount++; } else { G[gcount] = list[i]; gcount++; } } int i = 0; for(int j = 0; j < lcount; j++) { all[i] = L[j]; i++; } all[i] = p; i++; for(int j = 0; j < gcount; j++) { all[i] = G[j]; i++; } return all; }
the way i did it seems kind of messy... but i'm having difficulty doing it with an array. please help
 11152009, 06:36 AM #2
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,372
 Blog Entries
 1
 Rep Power
 20
Your for loop cause for that,
Java Code:for (int j = 0; j < (gcount  1); j++) { all[i] = G[j]; i++; }
 11152009, 07:55 AM #3Member
 Join Date
 Feb 2009
 Posts
 92
 Rep Power
 0
If I am reading your code correctly, you are picking a pivot value, then placing the rest of the elements in one of two arrays such that one array contains values less than the pivot, and the other has value greater than the pivot. This is part of the algorithm.
Then you copy each array back into another array such that the small values are in one partition, and the high values in another partition. This is sort of correct, but you still don't have a sorted array, only one that is partitioned into a low partition and a high partition.
Quick sort is recursive. You now have to quicksort each partition that you created.
Naively, the base case that triggers the recursive returns is an array that has either one or two elements. If there is only one element, return the element; if there are two elements, order them as appropriate and return. The texts suggest that an insertion sort can be done with a sufficiently small array.
I don't see the recursive calls. Quicksort can be done in place. I don't think I'm wrong in saying that you aren't doing that either.
What you need to do is add code at the end of the routine that says:
SolutionArray= [quicksort(L);quicksort(G)]
To rephrase, what I see you doing is this:
SolutionArray=[L;G]
The literature will explain it more completely and better, but I hope this helps with the concepts.
 11152009, 05:44 PM #4Member
 Join Date
 Feb 2009
 Posts
 92
 Rep Power
 0
{15, 8, 55, 60, 37, 85, 25, 71, 2};
I put your code into eclipse and ran it through the debugger.
What I found was that 2 was put in L, everything else went into G.
p is the pivot value (Edit) of 2
So when we got to the part of the routine to transfer L to A, there is only
one element in L and all = {2,0,0,0,0,0,0,0,0}, i = 1
Now the line a[i] = a[1] = p = 2. This puts the pivot value at the end of the L partition,and between L and G. This seems to be correct. Psuedocode generally shows
something like [qsort(L),pivot,qsort(G)].
But the debugger shows:
all = {2,2,0,0,0,0,0,0,0}.
You are assigning the pivot to a partition AND and ALSO adding it as an element in all;
I didn't follow this through to see where the index value went out of bounds, but I suspect that if you solve this problem, you will solve the other.
Edit: L.len gth+ G.length = list.length; L.length + G.length + p.length = list.length + 1
I've written a quicksort in Lisp that had a similar problem. In my case, the partitions had every value in one partition, and no value in the other. The list never got sorted because there was no progress. Moral: you have to be careful how pivot values are chosen and assigned. Simply choosing the last value in an array may select a poor value. If the list is sorted, or nearly sorted, quick sort degenerates from n*log(n) to n*n.
Suggested preventive measures include randomizing the array before sorting. You can also preprocess the list to find an acceptable or even a good value.
For example, pick a median value for the pivot. You have to add a O(n) process, but O(2n) is still O(n), and O(2n*log(n)) is still < O(n^2); In my test array, the average is about 45. The other method to pick a pivot is median of 3. In my sample array, this could be {15 [0], 8[1], 55[2]} > 15 or {15[1st],37[middle],2[last]} > 15. It is simply a coincidence that the values for pivot are the same. IIRC, I processed my array sub lists, which were lists of line segments to be sorted in the line direction, by finding the average value, thereby guaranteeing that each sublist was n/2, preventing degeneration to a linear sort.Last edited by rdtindsm; 11152009 at 05:52 PM.
 11162009, 02:56 AM #5
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,372
 Blog Entries
 1
 Rep Power
 20
To sort any array you can easily use java.util.Arrays.sort method. Only thing in that UNICODE string array you've do some adjustments.
Similar Threads

problem with quicksort
By jvasilj1 in forum New To JavaReplies: 2Last Post: 03052009, 12:09 AM 
quicksort program
By jvasilj1 in forum New To JavaReplies: 5Last Post: 03032009, 03:47 AM 
HIERARCHY_REQUEST_ERR: An attempt was made to insert a node where it is not permitted
By R O C K Y in forum XMLReplies: 0Last Post: 02182009, 05:20 AM 
Quicksort
By little_polarbear in forum New To JavaReplies: 12Last Post: 07122008, 09:20 PM 
Security Violation:attempt to use Restricted Class: sun.jdbc.odbc.JdbcOdbcDriver
By Heather in forum Advanced JavaReplies: 1Last Post: 07142007, 05:59 PM
Bookmarks