Java - My sort is not working

Question

I have created the following class to sort an array of strings.

public class StringSort {
private String[] hotelNames;
private int arrayLength;

public void sortHotel(String[] hotelArray) {
    if (hotelArray.length <= 1) {
        return;
    }
    this.hotelNames = hotelArray;
    arrayLength = hotelArray.length;
    quicksort(0, arrayLength - 1);
}

private void quicksort(int low, int high) {
    int i = low, j = high;
    String first = hotelNames[low];
    String last = hotelNames[high];     
    String pivot = hotelNames[low + (high - low) / 2];

    while( (first.compareTo(last)) < 0 ) { // first is less than last
        while( (hotelNames[i].compareTo(pivot)) < 0 ) { // ith element is < pivot
            i++;
        }
        while( (hotelNames[j].compareTo(pivot)) > 0) { // jth element is > pivot
            j--;
        }
        if ( ( hotelNames[i].compareTo( hotelNames[j] )) <= 0 ) {
            swap(i, j);
            i++;
            j--;                
        }

        //recursive calls
        if (low < j) {
            quicksort(low, j);
        }
        if (i < high) {
            quicksort(i, high);
        }
    }
}

private void swap(int i, int j) {
    String temp = hotelNames[i];
    hotelNames[i] = hotelNames[j];
    hotelNames[j] = temp;
}

}

However in my main class (a class to test StringSort), when I do:

StringSort str = new StringSort();
String[] hotel1 = {"zzzz", "wwww", "dddd", "bbbbb", "bbbba", "aaaf", "aaag", "zzz"};
str.sortHotel(hotel1);

And then I have another method that prints out the array. However when it prints out, it outputs the hotel1 array as it is, unchanged. There is no 'sorting' happening, I'm not sure where I've gone wrong.

What debugging have you done? Add a printout to swap() and see if it's doing the swaps you would expect. — John Kugelman
– John Kugelman, Commented Mar 31, 2013 at 20:05
I thought compareTo was suitable as it compares strings lexicographically. — Khalid
– Khalid, Commented Mar 31, 2013 at 20:13

John Kugelman · Accepted Answer · 2013-03-31 20:18:57Z

6

There are several problems in your implementation of quicksort:

First/last comparison. This code will made your quicksort not do anything as long as first element is less than the last element, regardless of any other order.
```
while( (first.compareTo(last)) < 0 ) { // first is less than last
```

Check before swap. This line is unnecessary:

if ( ( hotelNames[i].compareTo( hotelNames[j] )) <= 0 ) {

What you really want to do is see if the i is still less than j and bail out of the loop then. If not, then swap. After you finished with the partitioning loop, then make the recursive call, as long as there are more than two elements in each subarray.

edited Mar 31, 2013 at 20:18

John Kugelman

365k70 gold badges555 silver badges600 bronze badges

answered Mar 31, 2013 at 20:12

angelatlarge

4,1502 gold badges21 silver badges37 bronze badges

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

3 Comments

Khalid Over a year ago

Thank you, I knew that that line was dodgy, I was confusing high/low with my pointers i and j. I Changed it and it now works. I was basing this class of another quicksort I made for integers, that made me bit confused with i's and j's. Thanks man.

angelatlarge Over a year ago

Awesome! Beware though that there may be other problems lurking in there: your algorithm may perform badly on data that has lots of dupes, and on already sorted data.

Khalid Over a year ago

I will be thoroughly testing it, before implementing it into my program, thank you for pointing it out. I love this site!

Collectives™ on Stack Overflow

Java - My sort is not working

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related