¿Es esta una implementación correcta de quicksort?

Question

Me gustaría comprobar si esta es una implementación correcta de QuickSort, parece estar haciendo el trabajo, pero ¿me estoy perdiendo de algo?

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

} 

}

fijo:

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

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

Answer 2

1 pequeño punto- hay un int potencial desbordamiento aquí:

(lo + hi)/2

Answer 3

EDITAR: Mi mal por falta la etiqueta de Java, lo siento ... La continuación es C# QuickSort genérica ... lo dejaré aquí de todos modos para los lectores .net ...

Se ve bien a primera vista, pero ¿qué tal esto genérica ¿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

Aproveche esta oportunidad para aprender a escribir una prueba unitaria. (Google en "junit", por ejemplo). Genere matrices grandes y asegúrese de que estén ordenadas correctamente, por ejemplo: matrices rellenas con números aleatorios, matrices rellenas con 0, 1, Integer.MAX_INT. Intenta provocar cosas como el desbordamiento de enteros y otros rincón extraños.

Answer 5

Y aquí es una versión javascript ... QuickSort (a, comp, desc)

• una es por supuesto el array a ordenar.
• comp es la función de comparación que tiene que tomar dos valores y devolver -1, 0 o +1 dependiendo de cómo se clasifiquen los 2 argumentos.

• desc es booleano para invertir el orden de clasificación.

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