Warum ist meine schnelle Art so langsam?

Question

Ich übe das Schreiben von Sortieralgorithmen als Teil einer Interviewvorbereitung, und ich frage mich, ob jemand mir helfen kann zu erkennen, warum diese schnelle Sortierung nicht sehr schnell ist? Es scheint die richtige Laufzeit-Komplexität zu haben, aber es ist langsamer als meine Merge-Sortierung nach einem konstanten Faktor von etwa 2. Ich würde auch alle Kommentare, die meinen Code verbessern würden, schätzen, die nicht unbedingt die Frage beantworten.

Vielen Dank für Ihre Hilfe! Bitte zögere nicht, mich wissen zu lassen, wenn ich irgendwelche Etikette Fehler gemacht habe. Das ist meine erste Frage hier.

private class QuickSort implements Sort { 

     @Override 
     public int[] sortItems(int[] ts) { 
      List<Integer> toSort = new ArrayList<Integer>(); 
      for (int i : ts) { 
       toSort.add(i); 
      } 
      toSort = partition(toSort); 
      int[] ret = new int[ts.length]; 
      for (int i = 0; i < toSort.size(); i++) { 
       ret[i] = toSort.get(i); 
      } 
      return ret; 
     } 

     private List<Integer> partition(List<Integer> toSort) { 
      if (toSort.size() <= 1) 
       return toSort; 
      int pivotIndex = myRandom.nextInt(toSort.size()); 
      Integer pivot = toSort.get(pivotIndex); 
      toSort.remove(pivotIndex); 
      List<Integer> left = new ArrayList<Integer>(); 
      List<Integer> right = new ArrayList<Integer>(); 
      for (int i : toSort) { 
       if (i > pivot) 
        right.add(i); 
       else 
        left.add(i); 
      } 
      left = partition(left); 
      right = partition(right); 
      left.add(pivot); 
      left.addAll(right); 
      return left; 
     } 

} 

Vielen Dank, jeder der geholfen hat!

Das ist meine viel verbesserte Klasse für die Nachwelt:

private class QuickSort implements Sort { 

     @Override 
     public int[] sortItems(int[] ts) { 
      int[] ret = ts.clone(); 
      partition(ret,0,ret.length); 
      return ret; 
     } 

     private void partition(int[] toSort,int start,int end) { 
      if(end-start<1) return; 
      int pivotIndex = start+myRandom.nextInt(end-start); 
      int pivot = toSort[pivotIndex]; 
      int curSorted = start; 
      swap(toSort,pivotIndex,start); 
      for(int j = start+1; j < end; j++) { 
       if(toSort[j]<pivot) { 
        if(j!=curSorted+1) 
         swap(toSort,curSorted,curSorted+1); 
        swap(toSort,j,curSorted++); 
       } 
      } 
      // Now pivot is at curSorted 
      partition(toSort,start,curSorted); 
      partition(toSort,curSorted+1,end); 
     } 
    } 

Answer 1

Einer der größten Vorteile von Quicksort ist, dass es als ein In-Place implementiert werden kann. Erstellen Sie keine neuen Listen, sondern sortieren Sie stattdessen die Elemente an Ort und Stelle.

Answer 2

Neben Listen nicht wiederverwendet, konvertieren Sie zwischen Integer und int in jedem Schritt:

 for (int i : toSort) { // converts from Integer to int 
      if (i > pivot) 
       right.add(i); // converts from int to Integer 
      else 
       left.add(i); // converts from int to Integer 
     } 

Hinweis, dass die Umwandlung von int nach Integer im allgemeinen ein neues Objekt erfordert geschaffen werden.

Und schließlich random.nextInt() könnte eine nicht-triviale Operation sein. Vielleicht wäre es besser, nur einen zufälligen Pivot auszuwählen, wenn der toSort eine bestimmte Größe überschreitet und ansonsten eine einfachere Pivor-Auswahlstrategie verwendet (Messen Sie es!).