Czy to jest poprawna implementacja quicksort?

Question

Chciałbym sprawdzić, czy jest to poprawna implementacja QuickSorta, Wydaje się, że wykonuje tę pracę, ale czy czegoś mi brakuje?

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

} 

}

stałej:

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

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

Answer 2

1 niewielki punkt-istnieje potencjalne Int przelewowy tutaj:

(Ni + Hi)/2

Answer 3

EDYCJA: Moje złe dla brakuje znacznika Java, przepraszam ... poniższej C# rodzajowe Quicksort ... będę go tu zostawić i tak NET czytelników ...

Wygląda ok na pierwszy rzut oka, ale jak o tym generic jeden?

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

Skorzystaj z okazji, aby nauczyć się pisać test jednostek. (Google na przykład "junit"). Wygeneruj duże tablice i upewnij się, że są one poprawnie posortowane, na przykład: tablice wypełnione liczbami losowymi, tablice wypełnione 0, 1, Integer.MAX_INT. Spróbuj sprowokować takie rzeczy, jak przepełnienie w liczbach całkowitych i inne dziwne przypadki.

Answer 5

A oto wersja javascript ... QuickSort (a, zarys, desc)

• a jest oczywiście tablica być posortowane.
• comp jest funkcją porównywania, która musi przyjmować dwie wartości i zwracać -1, 0 lub +1, w zależności od tego, jak należy sortować 2 argumenty.

• desc jest wartością logiczną, aby odwrócić kolejność sortowania.

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