Использование быстрой сортировки массива строк

Я изучаю программирование, и вместо того, чтобы публиковать все задание, я просто попрошу помощи в решении того, что я пытался понять уже несколько часов. Мне поручено отсортировать массив строк с помощью метода быстрой сортировки. Все остальное, что мне было поручено в рамках этой проблемы, в порядке, но когда я протестировал метод сортировки, распечатав массив строк, он полностью перемешался без какой-либо видимой рифмы или причины. Пожалуйста, помогите мне определить ошибку в моем коде или несколько явных ошибок, которые я пропустил. Предоставляемый массив строк представляет собой список из 65 имен: http://pastebin.com/jRrgeV1E и код метода. ниже:

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;
    }

java arrays string sorting quicksort
person Mackenzie    schedule 27.03.2015    source источник
comment
Какова ваша точная проблема? Разве это не сортирует. Показывает ли он значения несколько раз, так как я тестировал его, и, похоже, он работает нормально   -  person SomeJavaGuy    schedule 27.03.2015
comment
Это сработало для вас?? Может быть, тогда мне следует опубликовать остальную часть моего кода... Он показывает этот порядок для меня, когда я распечатываю его после сортировки: pastebin .com/5969hxGs это так странно!   -  person Mackenzie    schedule 27.03.2015

Ответы (2)


arrow_upward
6
arrow_downward

Хорошо, я ошибался, что это сработает, и нашел вашу крошечную ошибку.

Взгляните на псевдокод википедии

Вы заметите, что ваши условия в цикле while вызывают ошибку

если вы измените (a[i].compareTo(pivot) < 0 && i <= end && j > i) и (a[j].compareTo(pivot) > 0 && j >= start && j >= i) на

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

person SomeJavaGuy    schedule 27.03.2015
comment
Большое спасибо! Теперь это работает и для меня, и я вижу, что это было просто из-за одной ошибки, которая погубила меня. Огромное спасибо, теперь я могу спать спокойно! - person Mackenzie; 27.03.2015

arrow_upward
0
arrow_downward

Думал, это поможет тем, кто ищет алгоритм сортировки строк, основанный на методе быстрой сортировки.

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;
    }
}
person John Smith    schedule 18.04.2016