Ist dies eine korrekte Implementierung von Quicksort?

Question

Ich würde gerne überprüfen, ob dies eine korrekte Implementierung von QuickSort ist, scheint es die Arbeit zu tun, aber verpasse ich etwas?

public class QuickSort implements Sorter { 

public void sort(Comparable[] items) { 
    QuickSort(items, 0, items.length - 1); 
} 

static void QuickSort(Comparable[] items, int a, int b) { 
    int lo = a; 
    int hi = b; 
    if (lo >= hi) { 
     return; 
    } 
    Comparable mid = items[(lo + hi)/2]; 
    Comparable T; 

    while (lo < hi) { 
     while (items[lo].compareTo(mid)<0) { 
      lo++; 
     } 
     while (mid.compareTo(items[hi])<0) { 
      hi--; 
     } 
     if (lo < hi) { 
      T = items[lo]; 
      items[lo] = items[hi]; 
      items[hi] = T; 
     } 
    } 

    QuickSort(items, a, lo); 
    QuickSort(items, lo == a ? lo + 1 : lo, b); 

} 

}

behoben:

private static void quickSort(Comparable[] items, int a, int b) { 
    int i = a; 
    int j = b; 

    Comparable x = items[(a+ b)/2]; 
    Comparable h; 

    do { 
     while (items[i].compareTo(x) < 0) { 
      i++; 
     } 
     while (items[j].compareTo(x) > 0) { 
      j--; 
     } 
     if (i <= j) { 
      h = items[i]; 
      items[i] = items[j]; 
      items[j] = h; 
      i++; 
      j--; 
     } 
    } while (i <= j); 

    if (a < j) { 
     quickSort(items, a, j); 
    } 
    if (i < b) { 
     quickSort(items, i, b); 
    } 
} 

Answer 1

public static void quicksort(Comparable [ ] a) { 

quicksort(a, 0, a.length - 1); 
} 
private static final int CUTOFF = 10; 
private static void quicksort(Comparable [ ] a, int low, int high) { 
if(low + CUTOFF > high) 
insertionSort(a, low, high); 
else { 
int middle = (low + high)/2; 
if(a[ middle ].compareTo(a[ low ]) < 0) 
swapReferences(a, low, middle); 
if(a[ high ].compareTo(a[ low ]) < 0) 
swapReferences(a, low, high); 
if(a[ high ].compareTo(a[ middle ]) < 0) 
swapReferences(a, middle, high); 
swapReferences(a, middle, high - 1); 
Comparable pivot = a[ high - 1 ]; 
int i, j; 
for(i = low, j = high - 1; ;) { 
while(a[ ++i ].compareTo(pivot) < 0) 
; 
while(pivot.compareTo(a[ --j ]) < 0) 
; 
if(i >= j) 
break; 
swapReferences(a, i, j); 
} 
swapReferences(a, i, high - 1 
quicksort(a, low, i - 1); // Sort small elements 
quicksort(a, i + 1, high); // Sort large elements 
} 
} 
public static final void swapReferences(Object [ ] a, int index1, int index2) 
{ 
Object tmp = a[ index1 ]; 
a[ index1 ] = a[ index2 ]; 
a[ index2 ] = tmp; 
} 
private static void insertionSort(Comparable [ ] a, int low, int high) { 
for(int p = low + 1; p <= high; p++) { 
Comparable tmp = a[ p ]; 
int j; 
for(j = p; j > low && tmp.compareTo(a[ j - 1 ]) < 0; j--) 
a[ j ] = a[ j - 1 ]; 
a[ j ] = tmp; 
} 
} 

Von http://java-blackberry.blogspot.com/2007/12/quick-sort-implementation-with-median.html

Answer 2

1 kleine punkt- gibt es ein Potential int Überlauf hier:

(lo + hallo)/2

Answer 3

EDIT: Mein schlechtes für fehlt der Java-Tag, sorry ... Der unter C# generic QuickSort ist ... ich es hier sowieso für .net Leser verlassen würde ...

Es befindet sich auf dem ersten Blick sieht ok, aber wie über diese generic ein?

public class QuickSort<T> where T : IComparable<T> 
{ 
    #region private variable to sort inplace 
    readonly private IList<T> itms; 
    #endregion private variable to sort inplace 

    #region ctor 
    private QuickSort() { } // Hide parameterless constructor 
    /// <summary> 
    /// Constructor requires IList<T> T must implement CompareTo() method.../> 
    /// </summary> 
    /// <param name="Lst">List<T> of elements to sort</param> 
    public QuickSort(IList<T> Lst):this)() { itms = Lst; } 
    #endregion ctor 

    #region public sort method 
    public void Sort() { Sort(0, itms.Count - 1); } 
    /// <summary> 
    /// Executes QuickSort algorithm 
    /// </summary> 
    /// <param name="L">Index of left-hand boundary of partition to sort</param> 
    /// <param name="R">Index of right-hand boundary of partition to sort</param> 
    private void Sort(long L, long R) 
    { 
     // Calls iSort (insertion-sort) for partitions smaller than 5 elements 
     if (R - L < 4) iSort(L, R); 
     else 
     { 
      long i = (L + R)/2, j = R - 1; 
      // Next three lines to set upper and lower bounds 
      if (itms[L].CompareTo(itms[i]) > 0) Swap(L, i); 
      if (itms[L].CompareTo(itms[R]) > 0) Swap(L, R); 
      if (itms[i].CompareTo(itms[R]) > 0) Swap(i, R); 
      Swap(i, j); 
      // -------------------------------- 
      T p = itms[j]; // p = itms[j] is pivot element 
      i = L; 
      while (true) 
      { 
       while (itms[++i].CompareTo(p) < 0) {} 
       while (itms[--j].CompareTo(p) > 0) {} 
       if (j < i) break; 
       Swap(i, j); 
      } 
      Swap(i, R - 1); 
      Sort(L, i);  // Sort Left partition -- HERE WAS TYPO BUG 
      Sort(i + 1, R); // Sort Right partition 
     } 
    } 
    #endregion public sort method 

    #region private Helper methods 
    private void Swap(long L, long R) 
    { 
     T t = itms[L]; 
     itms[L] = itms[R]; 
     itms[R] = t; 
    } 
    private void iSort(long L, long R) 
    { 
     for (long i = L; i <= R; i++) 
     { 
      T t = itms[i]; 
      long j = i; 
      while ((j > L) && (itms[j - 1].CompareTo(t) > 0)) 
      { 
       itms[j] = itms[j - 1]; 
       j--; 
      } 
      itms[j] = t; 
     } 
    } 
    #endregion private Helper methods 
} 

Answer 4

Nutzen Sie diese Gelegenheit, um zu lernen, wie man einen Komponententest schreibt. (Google auf "Junit" zum Beispiel). Generieren Sie große Arrays und stellen Sie sicher, dass sie richtig sortiert sind, z. B. Arrays, die mit Zufallszahlen gefüllt sind, Arrays, die mit 0, 1, Integer.MAX_INT gefüllt sind. Versuchen Sie Dinge wie Integer-Überlauf und andere seltsame Ecken zu provozieren.

Answer 5

Und hier ist eine JavaScript-Version ... QuickSort (a, comp, desc)

• a ist natürlich das Array sortiert werden.
• comp ist die Vergleichsfunktion, die zwei Werte annehmen und -1, 0 oder +1 zurückgeben muss, abhängig davon, wie die 2 Argumente sortiert werden sollen.

• desc ist boolean, um die Sortierreihenfolge umzukehren.

  function QuickSort(a, comp, desc) { 
      function defComp(L, R) {return((L>R)? 1: (L<R)? -1: 0);} 
      var cmp = (comp)? comp: defComp; 
      var siz = a.length; 
      qSort(0, siz-1); 
      if (desc) reverse(); 
      // ------------------ 
      function qSort(L, R) { 
       if (R - L < 4) {iSort(L, R);} // insertion-sort-- 
       else { 
        var i = parseInt((L+R) /2), j=R-1; 
        if (cmp(a[L], a[i]) > 0) swap(L,i); 
        if (cmp(a[L], a[R]) > 0) swap(L,R); 
        if (cmp(a[i], a[R]) > 0) swap(i,R); 
        swap(i,j); 
        // ------------------------------------------ 
        var p=a[j]; // p=a[j] is pivot 
        i=L; 
        while (true) { 
         while(cmp(a[++i], p) < 0); 
         while(cmp(a[--j], p) > 0);  
         if (j < i) break; 
         swap(i,j); 
        } 
        swap(i,R-1); 
        qSort(L,i); // Left Partition 
        qSort(i+1,R); // Right Partition 
       } 
      } 
      function swap(L,R) {var t=a[L]; a[L]=a[R]; a[R]=t;} 
      function reverse() 
       {for(var i=0; i<parseInt(siz/2); i++) swap(i,(siz-i-1));} 
      // insertion-sort 
      function iSort(L,R) { 
       var j,t; 
       for(var i=L; i<=R; i++) { 
        t = a[i], j = i; 
        while ((j>L) && (cmp(a[j-1], t) > 0)) 
         {a[j] = a[j-1]; j--;} 
        a[j] = t; 
       } 
      } 
  }