Computer Science Canada

Got some sorting problems.
Author:  Reality Check [ Mon May 26, 2008 9:12 am ]
Post subject:  Got some sorting problems.
I have an array list of friends (from my friend class) and I want to sort them by first name. This is my method for sorting:

code:

    public static void quickSort (ArrayList f1, int start, int end)
    {
        int i = start;
        int k = end;
        Friend f = (Friend) f1.get (i);
        Friend f2 = (Friend) f1.get (k);
        if (end - start >= 1)
        {
            Friend f3 = (Friend) f1.get (start);
            String pivot = f3.getFirstName ();

            while (k > i)
            {
                while (f.getFirstName ().compareToIgnoreCase (pivot) >= 0 && i <= end && k > i)
                {
                    i++;
                    f = (Friend) f1.get (i);
                }
                while (f2.getFirstName ().compareToIgnoreCase (pivot) < 0 && k >= start && k >= i)
                {
                    k--;
                    f2 = (Friend) f1.get (k);
                }
                if (k > i)
                    swap (f1, i, k);
            }
            switcher (f1, start, k);

            quickSort (f1, start, k - 1);
            quickSort (f1, k + 1, end);
        }


        else
        {
            return;
        }
    }


    public static void switcher (ArrayList f1, int index1, int index2)
    {
        Friend temp = (Friend) f1.get (index1);
        f1.set (index1, f1.get (index2));
        f1.set (index2, temp);
    }


I'm calling it like this (f1 is my arraylist):

code:

quickSort (f1, 0, f1.size() - 1);


When I run it, it runs fine and gets past quick sort but it is not sorted for some reason. It comes out the way it went in and I can't figure out where my logic falters.

Here is the code in context if you need it.
Author:  Reality Check [ Mon May 26, 2008 9:48 am ]
Post subject:  Re: Got some sorting problems.
Hmm so I just added more friends and I get an Index out of bounds error when it's more than 1 friend and it runs if its one friend. My method works in a more constrained environment as so:

code:

// The "Qick" class.
public class Qick
{
    static int[] array = {1, 3, 2, 12, 13, 11, 9, 8, 2, 10, 5, 3};
    public static void main (String[] args)
    {
        quickSort (array, 0, array.length - 1);
        for (int i = 0; i < array.length ; i ++)
        System.out.println (array [i]);
    } // main method




    public static void quickSort (int array[], int start, int end)
    {
        int i = start;
        int k = end;

        if (end - start >= 1)
        {
            int pivot = array [start];

            while (k > i)
            {
                while (array [i] <= pivot && i <= end && k > i)
                    i++;
                while (array [k] > pivot && k >= start && k >= i)
                    k--;
                if (k > i)
                    swap (array, i, k);
            }
            swap (array, start, k);

            quickSort (array, start, k - 1);
            quickSort (array, k + 1, end);
        }


        else
        {
            return;
        }
    }


    public static void swap (int array[], int index1, int index2)
    {
        int temp = array [index1];
        array [index1] = array [index2];
        array [index2] = temp;
    }
} // Qick class


This works perfectly so I'm not sure why my ArrayList version in my code is giving me problems.
Author:  Reality Check [ Tue May 27, 2008 7:59 pm ]
Post subject:  Re: Got some sorting problems.
Ok I fixed it. It was, as expected, a stupid error that I overlooked. My first while loop should've had "<= 0" and not ">=0" and the second while loop was also the wrong way.

Also, my Friend Object declarations should have been under the parent while loop where I wrote "while (k > i)". Because I was making a friend object based on the index k ABOVE this statement, there was the possibility of a negative k and therefore an index out of bounds. I hate these stupid careless errors.

But yea, thanks to anyone that was going to answer Smile

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy