Sử dụng quicksort trên mảng chuỗi

Question

Tôi là sinh viên lập trình và thay vì đăng bài tập toàn bộ, tôi sẽ chỉ yêu cầu trợ giúp giải quyết những gì tôi đã cố gắng hàng giờ để hiểu. Tôi được giao nhiệm vụ phân loại một chuỗi các chuỗi bằng cách sử dụng phương thức quicksort. Mọi thứ khác tôi đã được giao nhiệm vụ như là một phần của vấn đề này là tốt nhưng khi tôi thử nghiệm phương pháp phân loại bằng cách in ra String Array, nó hoàn toàn lộn xộn mà không có bất kỳ vần điệu hay lý do nào. Xin vui lòng giúp tôi xác định lỗi trong mã của tôi, hoặc một số lỗi rõ ràng tôi đã bỏ qua. Các mảng các chuỗi cung cấp là danh sách này là 65 tên: http://pastebin.com/jRrgeV1E và mã của phương pháp là dưới đây:

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

Answer 1

Ok, tôi đã sai lầm rằng nó sẽ làm việc và phát hiện sai lầm nhỏ của bạn.

Hãy xem wikipedias pseudo code

Bạn sẽ nhận thấy rằng điều kiện của bạn trong vòng lặp while được gây ra lỗi

nếu bạn thay đổi (a[i].compareTo(pivot) < 0 && i <= end && j > i) và (a[j].compareTo(pivot) > 0 && j >= start && j >= i) để

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

Answer 2

Suy nghĩ điều này sẽ giúp ích cho những người tìm kiếm thuật toán sắp xếp chuỗi dựa trên phương pháp phân loại nhanh.

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