Share via

Работающая быстрая сортировка (quicksort) на C#...

  • Article

????? ???????, ??????? ?????? ?????????? ?????? ????? ?????? ??????? ? ?????? ?????? ????? ?????? ??????????????? ??????? ?? C#, C++ ? Python, ????????? ????? ?? ??????? ?????????? (quicksort). ? ??? ???????? ????? ???????? ????????? ????? ????????? ??????? ???????? ? ???????? ????????? ?????. ??-??, ????, ??? ????????? ?????????? ? ?????????? ??????, ?? ?????????? ????????? ???????? ??? ???????, ? ????? ????????? ??????????? ? ??????. ? ??? ??? ??????????. ????? ????????. ???-?????? ????? ????

static public void Quicksort(int[] ar)
{
     if (ar.Length > 1) Quicksort(ar, 0, ar.Length - 1);
}

static private void Quicksort(int[] ar, int left, int right)
{
     if (left == right) return;
     int i = left + 1;
     int j = right;
     int pivot = ar[left];

     // Loop invariant i <= j
     while (i < j)
{
          if (ar[i] <= pivot) i++;
          else if (ar[j] > pivot) j--;
          else
          { // Swap ith and jth elements
               int m = ar[i]; ar[i] = ar[j]; ar[j] = m;
}
}
     // Now i == j

     if (ar[j] <= pivot /* it also means that i == right, because j was never moved */)
{
          // Left most element is array's maximum
          int m = ar[left]; ar[left] = ar[right]; ar[right] = m;
Quicksort(ar, left, right-1);
}
     else
     {
Quicksort(ar, left, i - 1);
Quicksort(ar, i, right);
}
}

???? ??????? ??????? ???????? ?? ???????? ??????: ??? ?? ?? ?????????????? ??????, ?????????? ????????????? ??????? Quicksort (????? i<j) ?????? ????? ????? ??????? ????? ????. ??????? ????????, ? ????? ????? ??????. ?????? ????????? ????? ??? ?????: https://www.eldar.com/node/154 (??, ??, ? ????? ????????? ??????????? ????? ?? ??????. ??????? ????? ????????? ?? ??????? ??? ?? ????????).

? ??, ???, ??? ??????, ????? ???? ? ????????????? ?????.

Comments

  • Anonymous
    January 01, 2003
    Спасибо, Сэм! И правда хорошо. Я, пожалуй, об этом еще и отдельно напишу.

  • Anonymous
    April 18, 2008
    Как-то смотрел "Three Beautiful Quicksorts" - понравилось, а вам? http://www.youtube.com/watch?v=aMnn0Jq0J-E