my Quicksort attempt has failed

[Jeremy8]

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.

    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

[Eranga]

Your for loop cause for that,

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

[rdtindsm]

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.

[rdtindsm]

{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.

[Eranga]

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.