Using quicksort on a string array

Question

I'm a programming student and rather than post the whole assignment I'll just ask for help solving what I've tried for hours now to understand. I'm tasked with sorting an array of strings using the quicksort method. Everything else I've been tasked with as part of this problem is fine but when I tested the sorting method by printing out the String Array, it's completely jumbled up without any seeming rhyme or reason. Please help me pinpoint the error in my code, or the several glaring errors I've overlooked. The array of strings provided is this list of 65 names: http://pastebin.com/jRrgeV1E and the method's code is below:

private static void quickSort(String[] a, int start, int end)
{
        // index for the "left-to-right scan"
        int i = start;
        // index for the "right-to-left scan"
        int j = end;

        // only examine arrays of 2 or more elements.
        if (j - i >= 1)
        {
            // The pivot point of the sort method is arbitrarily set to the first element int the array.
            String pivot = a[i];
            // only scan between the two indexes, until they meet.
            while (j > i)
            {
                // from the left, if the current element is lexicographically less than the (original)
                // first element in the String array, move on. Stop advancing the counter when we reach
                // the right or an element that is lexicographically greater than the pivot String.
                while (a[i].compareTo(pivot) < 0 && i <= end && j > i){
                    i++;
                }
                // from the right, if the current element is lexicographically greater than the (original)
                // first element in the String array, move on. Stop advancing the counter when we reach
                // the left or an element that is lexicographically less than the pivot String.
                while (a[j].compareTo(pivot) > 0 && j >= start && j >= i){
                    j--;
                }
                // check the two elements in the center, the last comparison before the scans cross.
                if (j > i)
                    swap(a, i, j);
            }
            // At this point, the two scans have crossed each other in the center of the array and stop.
            // The left partition and right partition contain the right groups of numbers but are not
            // sorted themselves. The following recursive code sorts the left and right partitions.

            // Swap the pivot point with the last element of the left partition.
            swap(a, start, j);
            // sort left partition
            quickSort(a, start, j - 1);
            // sort right partition
            quickSort(a, j + 1, end);
        }
    }
    /**
     * This method facilitates the quickSort method's need to swap two elements, Towers of Hanoi style.
     */
    private static void swap(String[] a, int i, int j)
    {
    String temp = a[i];
    a[i] = a[j];
    a[j] = temp;
    }

What´s your exact Problem? Doesn´t it sort. Does it show values multiple times, since I tested it and it seems to be working fine — SomeJavaGuy
– SomeJavaGuy, Commented Mar 27, 2015 at 7:17
It worked for you?? Maybe I should post the rest of my code then... It shows this order for me when I print it out after "sorting": pastebin.com/5969hxGs it's so strange! — Mackenzie
– Mackenzie, Commented Mar 27, 2015 at 7:30

SomeJavaGuy · Accepted Answer · 2015-03-27 07:40:55Z

7

Ok, i was mistaken that it would work and found your tiny mistake.

Take a look at wikipedias pseudo code

You will notice that your conditions in the while loop are causing the error

if you change (a[i].compareTo(pivot) < 0 && i <= end && j > i) and (a[j].compareTo(pivot) > 0 && j >= start && j >= i) to

(a[i].compareTo(pivot) <= 0 && i < end && j > i) and (a[j].compareTo(pivot) >= 0 && j > start && j >= i).

answered Mar 27, 2015 at 7:40

SomeJavaGuy

7,3872 gold badges24 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mackenzie Over a year ago

Thank you very much! It works for me now too, and I see it was just simple off by one errors that were my undoing. Thanks a million, now I can rest easy!

John Smith · Accepted Answer · 2016-04-18 20:46:14Z

Thought this would help for those who seek for a string sorting algorithm based on quick sorting method.

public class StringQuickSort {

    String names[];
    int length;

    public static void main(String[] args) {
        StringQuickSort sorter = new StringQuickSort();
        String words[] = {"zz", "aa", "cc", "hh", "bb", "ee", "ll"}; // the strings need to be sorted are put inside this array
        sorter.sort(words);

        for (String i : words) {
            System.out.print(i);
            System.out.print(" ");
        }
    }

    void sort(String array[]) {
        if (array == null || array.length == 0) {
            return;
        }
        this.names = array;
        this.length = array.length;
        quickSort(0, length - 1);
    }

    void quickSort(int lowerIndex, int higherIndex) {
        int i = lowerIndex;
        int j = higherIndex;
        String pivot = this.names[lowerIndex + (higherIndex - lowerIndex) / 2];

        while (i <= j) {
            while (this.names[i].compareToIgnoreCase(pivot) < 0) {
                i++;
            }

            while (this.names[j].compareToIgnoreCase(pivot) > 0) {
                j--;
            }

            if (i <= j) {
                exchangeNames(i, j);
                i++;
                j--;
            }
        }
        //call quickSort recursively
        if (lowerIndex < j) {
            quickSort(lowerIndex, j);
        }
        if (i < higherIndex) {
            quickSort(i, higherIndex);
        }
    }

    void exchangeNames(int i, int j) {
        String temp = this.names[i];
        this.names[i] = this.names[j];
        this.names[j] = temp;
    }
}

Collectives™ on Stack Overflow

Using quicksort on a string array

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related