Warum sortiert mein Quicksort das Array in umgekehrter Reihenfolge?

Question

Ich versuche, ein Quicksort für ein Array von Zeichenfolgen zu implementieren, aber es scheint, dass es das Array sortiert, aber in umgekehrter Reihenfolge, frage ich mich, warum ist das und wie kann ich dieses Problem lösen, um es normal zu sortieren ... Das ist meine Implementierung:

public class Main { 

    public static void main(String[] args) { 
     String[] list = {"a", "f", "c", "b"}; 
     quickSort(list, 0, list.length - 1); 
     for (String s : list) { 
      System.out.println(s); 
     } 
    } 

    private static void quickSort(String[] list, int start, int end) { 
     if (start < end) { 
      int pIndex = partition(list, start, end); 
      quickSort(list, start, pIndex - 1); 
      quickSort(list, pIndex + 1, end); 
     } 
    } 

    private static int partition(String[] list, int start, int end) { 
     String pivot = list[end]; 

     int leftCounter = start; 
     int rightCounter = end; 

     while (leftCounter < rightCounter) { 
      while (list[leftCounter].compareTo(pivot) <= 0 && leftCounter < end && rightCounter > leftCounter) { 
       leftCounter++; 
      } 
      while (list[rightCounter].compareTo(pivot) >= 0 && rightCounter > start && rightCounter >= leftCounter) { 
       rightCounter--; 
      } 
      if (leftCounter < rightCounter) { 
       swap(list, leftCounter, rightCounter); 
      } 
     } 
     swap(list, start, end); 
     return end; 
    } 

    private static void swap(String[] list, int start, int end) { 
     String aux = list[start]; 
     list[start] = list[end]; 
     list[end] = aux; 
    } 
} 

Answer 1

Die Implementierung, die in der Frage zur Verfügung gestellt wird, verwirrt mich. Das heißt nicht, dass es nicht korrekt ist (oder zumindest nahe ist), aber ich finde es schwierig zu lesen (was wohl wichtiger ist). Es ist möglich, dass ich nur langsam bin und diese Implementierung ist eigentlich sehr intuitiv, aber ich bin darauf ausgerichtet, dass die Implementierung schlauer als kohärent ist.

Im Allgemeinen ist Quicksort ein rekursiver Algorithmus, der eine Reihe von Daten in drei Bins relativ zu einem Pivot (kleiner als, gleich und größer als) aufteilt und dann die nicht gleichen Bins sortiert (mit demselben Algorithmus). und führt dann die Ergebnisse zu einem sortierten Dataset zusammen. Im Englischen ist es sehr intuitiv, wie es funktionieren soll. Es gibt keinen Grund, dass es im Code nicht gleich sein kann. Ich würde immer darauf abzielen, Code zu schreiben, den Sie verstehen können (und dann effizienter machen als notwendig), anstatt zu versuchen, etwas zu schreiben, das Sie nicht verstehen können und dann sind der Bach, wenn es nicht funktioniert.

Unten ist eine ausführlichere Implementierung, die (zumindest für mich) in ihrer Funktionsweise klarer zu sein scheint. Es ist auch sehr ineffizient (es macht ein halbes Dutzend verschiedene Listen und Arrays, nur um einen einzelnen Datensatz zu sortieren). Ich entschuldige mich dafür nicht; Ich gehe davon aus, dass diese Frage akademischer Natur ist. Wenn Sie es effizienter machen müssen, ist das eine Übung für den Benutzer, aber es gibt keinen Grund, warum es nicht in intuitive Schritte unterteilt werden kann, wie unten beschrieben (es wird Ihnen viel Kopfzerbrechen bereiten).

public class QuickSortTest { 
    private static String[] data = new String[] {"a", "b", "c", "f", "b", "e", "b"}; 

    public static void main(String[] args) { 
     String[] sortedData = quickSort(data); 
     for (String str : sortedData) { 
      System.out.println(str); 
     } 
    } 

    private static String[] quickSort(String[] data) { 
     // Edge case: return just the data if there are 0 or 1 elements (already sorted) 
     if (data.length <= 1) { 
      return data; 
     } 

     // Initialize the return structure 
     String[] sortedData = new String[data.length]; 

     // Choose the pivot (can be any value) 
     String pivot = data[data.length - 1]; 

     // Initialize the bins 
     ArrayList<String> lessThan = new ArrayList<String>(); 
     ArrayList<String> equalTo = new ArrayList<String>(); 
     ArrayList<String> greaterThan = new ArrayList<String>(); 

     // Place the data into bins (based on the pivot) 
     for (String str : data) { 
      int compareValue = str.compareTo(pivot); 
      if (compareValue < 0) { 
       lessThan.add(str); 
      } 
      else if (compareValue > 0) { 
       greaterThan.add(str); 
      } 
      else { 
       equalTo.add(str); 
      } 
     } 

     // Sort the non-equal data 
     String[] lessThanSorted = quickSort(lessThan.toArray(new String[0])); 
     String[] greaterThanSorted = quickSort(greaterThan.toArray(new String[0])); 

     // Merge the data 
     int length = 0; 
     for (String less : lessThanSorted) { 
      sortedData[length++] = less; 
     } 
     for (String equal : equalTo) { 
      sortedData[length++] = equal; 
     } 
     for (String greater : greaterThanSorted) { 
      sortedData[length++] = greater; 
     } 

     return sortedData; 
    } 
} 

Als beiseite, wenn jemand sucht Daten in der Praxis zu sortieren, verwenden Sie einfach Collections.sort()

Answer 2

Das Problem in Ihrer partition Methode ist:

private static int partition(String[] list, int start, int end) { 
     String pivot = list[end]; 

     int leftCounter = start; 
     int rightCounter = end; 

     while (leftCounter < rightCounter) { 
      while (list[leftCounter].compareTo(pivot) <= 0 && leftCounter < end && rightCounter > leftCounter) { 
       leftCounter++; 
      } 
      while (list[rightCounter].compareTo(pivot) >= 0 && rightCounter > start && rightCounter >= leftCounter) { 
       rightCounter--; 
      } 
      if (leftCounter < rightCounter) { 
       swap(list, leftCounter, rightCounter); 
      } 
     } 

Bis zu diesem Punkt, das ist im Grunde der Standard Hoare partition. Am Ende dieser Schleife sieht Ihre Liste wie [l1, l2, ..., lx, g1, g2, ..., gy, pivot] aus, wobei l1, l2, ..., lx alle kleiner oder gleich dem Drehpunkt sind und g1, g2, ..., gy größer oder gleich dem Drehpunkt sind. leftCounter zeigt auf g1 und zeigt auf lx. Sie müssen sicherstellen, dass der Schwenk die beiden Sätze trennt und dass Sie den richtigen Index zurück:

 swap(list, start, end); 
     return end; 
    } 

Diese beiden Linien sind die Quelle des Problems. Sie müssen swap(list, leftCounter, end) verschieben, um den Drehpunkt an die richtige Stelle in der Liste zu verschieben. Jetzt wird Ihre Liste wie [l1, l2, ..., lx, pivot, g2, g3, ..., gy, g1] aussehen. Sie müssen den Index des Pivots, der leftCounter ist, zurückgeben.

---

Warum in umgekehrter Reihenfolge sortiert: Sie hatten Glück. Versuchen Sie es an anderen Eingängen, es sortiert nicht immer in umgekehrter Reihenfolge.

String[] list = { "a", "c", "a", "b","c","f","g","a","b" } 

[a, g, b, a, f, c, c, b, a]