Menggunakan quicksort pada array string

Saya seorang mahasiswa pemrograman dan daripada memposting seluruh tugas, saya hanya akan meminta bantuan untuk memecahkan apa yang telah saya coba pahami selama berjam-jam. Saya ditugaskan untuk mengurutkan array string menggunakan metode quicksort. Segala sesuatu yang lain yang ditugaskan kepada saya sebagai bagian dari masalah ini baik-baik saja tetapi ketika saya menguji metode penyortiran dengan mencetak String Array, itu benar-benar campur aduk tanpa alasan atau alasan apa pun. Tolong bantu saya menemukan kesalahan dalam kode saya, atau beberapa kesalahan mencolok yang saya abaikan. Array string yang disediakan adalah daftar 65 nama berikut: http://pastebin.com/jRrgeV1E dan kode metodenya di bawah:

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 sumber
comment
Apa Masalah Anda sebenarnya? Bukankah itu memilah. Apakah itu menunjukkan nilai beberapa kali, sejak saya mengujinya dan tampaknya berfungsi dengan baik   -  person SomeJavaGuy    schedule 27.03.2015
comment
Ini berhasil untuk Anda?? Mungkin saya harus memposting sisa kode saya... Ini menunjukkan urutan ini untuk saya ketika saya mencetaknya setelah menyortir: pastebin .com/5969hxGs sungguh aneh!   -  person Mackenzie    schedule 27.03.2015

Jawaban (2)


arrow_upward
6
arrow_downward

Oke, saya salah mengira itu akan berhasil dan menemukan kesalahan kecil Anda.

Lihatlah kode semu wikipedia

Anda akan melihat bahwa kondisi Anda di loop while menyebabkan kesalahan

jika Anda mengubah (a[i].compareTo(pivot) < 0 && i <= end && j > i) dan (a[j].compareTo(pivot) > 0 && j >= start && j >= i) menjadi

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

person SomeJavaGuy    schedule 27.03.2015
comment
Terima kasih banyak! Ini berfungsi untuk saya sekarang juga, dan saya melihat itu hanya disebabkan oleh satu kesalahan yang menjadi kehancuran saya. Terima kasih banyak, sekarang saya bisa tenang! - person Mackenzie; 27.03.2015

arrow_upward
0
arrow_downward

Saya pikir ini akan membantu bagi mereka yang mencari algoritma pengurutan string berdasarkan metode pengurutan cepat.

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