Действительно ли это - корректная реализация quicksort? [закрытый]

1 маленькая точка - существует потенциальное международное переполнение здесь:

(lo + привет) / 2

Воспользуйтесь этой возможностью, чтобы изучить, как записать модульный тест. (Google на "junit", например). Генерируйте большие массивы и удостоверьтесь, что они отсортированы правильно, например: массивы заполняются случайными числами, массивы, заполненные 0, 1, Целое число. MAX_INT. Попытайтесь вызвать вещи как целочисленное переполнение и другой странный cornercases.

Править: Мое плохое для пропавших без вести тега Java, извините... Ниже универсальный quickSort C#... Я оставлю его здесь так или иначе для читателей .NET...

Это смотрит хорошо на первый взгляд, но как насчет этого универсального?

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
}

И вот версия JavaScript... QuickSort (a, аккомпанемент, desc)

• конечно, массива, который будет отсортирован.
• аккомпанемент является сравнить функцией, которая должна принять два значения и возвратиться-1, 0 или +1 в зависимости от того, как эти 2 аргумента должны отсортировать.

• desc является булевской переменной для инвертирования порядка сортировки.

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