Results 1 to 5 of 5
  1. #1
    Jeremy8 is offline Member
    Join Date
    Feb 2009
    Posts
    12
    Rep Power
    0

    Default 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.length-1];
            
            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 main method just makes a bunch of random integers and then displays them after calling this method

    the way i did it seems kind of messy... but i'm having difficulty doing it with an array. please help

  2. #2
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,371
    Blog Entries
    1
    Rep Power
    20

    Default

    Your for loop cause for that,

    Java Code:
            for (int j = 0; j < (gcount - 1); j++) {
                all[i] = G[j];
                i++;
            }

  3. #3
    rdtindsm is offline Member
    Join Date
    Feb 2009
    Posts
    92
    Rep Power
    0

    Default

    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.

  4. #4
    rdtindsm is offline Member
    Join Date
    Feb 2009
    Posts
    92
    Rep Power
    0

    Default

    {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 pre-process 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; 11-15-2009 at 06:52 PM.

  5. #5
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,371
    Blog Entries
    1
    Rep Power
    20

Similar Threads

  1. problem with quicksort
    By jvasilj1 in forum New To Java
    Replies: 2
    Last Post: 03-05-2009, 01:09 AM
  2. quicksort program
    By jvasilj1 in forum New To Java
    Replies: 5
    Last Post: 03-03-2009, 04:47 AM
  3. Replies: 0
    Last Post: 02-18-2009, 06:20 AM
  4. Quicksort
    By little_polarbear in forum New To Java
    Replies: 12
    Last Post: 07-12-2008, 10:20 PM
  5. Replies: 1
    Last Post: 07-14-2007, 06:59 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •