Si tratta di un'implementazione corretta di quicksort?

Question

Vorrei verificare se questa è una corretta implementazione di QuickSort, sembra che stia facendo il lavoro, ma sto perdendo qualcosa?

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

} 

}

fisso:

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

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

Answer 2

1 piccola point c'è un potenziale int trabocco qui:

(lo + hi)/2

Answer 3

EDIT: Il mio male per manca il tag java, scusa ... Il sotto è C# QUICKSORT generico ... lascio qui comunque per i lettori .net ...

sembra ok a prima vista, ma come su questo generici uno?

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

Cogli questa occasione per imparare come scrivere un test unitario. (Google su "junit", per esempio). Generare array di grandi dimensioni e assicurarsi che siano ordinati correttamente, ad esempio: array riempiti con numeri casuali, array riempiti con 0, 1, Integer.MAX_INT. Cerca di provocare cose come il trabocco di interi e altre strane cornette.

Answer 5

Ed ecco una versione javascript ... QuickSort (a, comp, disc)

• una è ovviamente la matrice da ordinare.
• comp è la funzione di confronto che deve prendere due valori e restituire -1, 0 o +1 a seconda di come devono essere ordinati i 2 argomenti.

• desc è booleano per invertire l'ordine.

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