Verwendung von Quicksort in einem String-Array

Question

Ich bin ein Programmierstudent und anstatt die gesamte Aufgabe zu posten, werde ich einfach um Hilfe bitten, was ich seit Stunden versucht habe zu verstehen. Ich bin beauftragt, ein Array von Strings mit der Quicksort-Methode zu sortieren. Alles andere, mit dem ich als Teil dieses Problems beauftragt wurde, ist in Ordnung, aber wenn ich die Sortiermethode durch Ausdrucken des String-Arrays testete, ist es komplett durcheinandergewürfelt ohne irgendeinen scheinbaren Reim oder Grund. Bitte helfen Sie mir, den Fehler in meinem Code oder die verschiedenen eklatanten Fehler, die ich übersehen habe, genau zu bestimmen. Das Array von Strings vorgesehen ist diese Liste von 65 Namen: http://pastebin.com/jRrgeV1E und der Code der Methode unten:

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, ich war falsch, dass es funktionieren würde, und fand Ihre kleine Fehler.

Werfen Sie einen Blick auf wikipedias pseudo code

werden Sie feststellen, dass Ihre Bedingungen in der while-Schleife

den Fehler verursachen, wenn Sie (a[i].compareTo(pivot) < 0 && i <= end && j > i) und (a[j].compareTo(pivot) > 0 && j >= start && j >= i) zu

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

Answer 2

Dachte, dies würde für diejenigen, die nach einem String Sorting-Algorithmus auf der Grundlage schneller Sortierung Methode helfen würde.

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