Быстрая сортировка на C#

Пошаговое описание алгоритма

1. Из массива выбирается элемент a[i]. Как правило, в качестве этого элемента берется центральный элемент массива.
2. Остальные элементы распределяются таким образом, чтобы слева от a[i] оказались все элементы, меньшие или равные a[i]. Элементы, большие или равные a[i], помещаются справа. В результате массив будет выглядеть так:
   
3. Производится проверка количества элементов в левой и правой частях массива. Если какая-либо часть (или обе части) содержит более двух элементов, то для этой части (или частей) запускается та же процедура сортировки с помощью рекурсивного вызова.

Реализация на C#

Класс QuickSorting, содержащий функцию быстрой сортировки, и класс Test для тестирования этой функции:

class QuickSorting {
   public static void sorting(double[] arr, long first, long last) {
      double p = arr[(last - first)/2 + first];
      double temp;
      long i = first, j = last;
      while(i  p && j >= first) --j;
            if(i  first) sorting(arr, first, j);
      if(i  key");
      System.Console.ReadLine();
   }
}

Смотрие также

• Сортировка и поиск: Рецептурный справочник

1.

31K

06 сентября 2007 года

homa.andy

6 / / 06.09.2007

7 апреля 2011, 15:43:03

Я уже молчу про строчку 4 (как пронумеровано выше). Ну зачем же делать перестановку, если i == j?

2.

31K

06 сентября 2007 года

homa.andy

6 / / 06.09.2007

7 апреля 2011, 15:29:43

А теперь попробуйте заполнить массив одинаковыми числами и посмотрите, что делает ваш цикл:

Код:

while(i <= j) {

  while(arr[ i ] < p && i <= last)  ++i;

  while(arr[ j ] > p && j >= first) --j;

    if(i <= j) {

         temp = arr[ i ];

         arr[ i ] = arr[ j ];

         arr[ j ] = temp;

         ++i; --j;

       }

  }

Строки 2 и 3 не выполняются (там строгое неравенство), поэтому всегда срабатывает перестановка. ВСЕГДА!!!

Обычная реализация этого алгоритма хуже всего работает на массивах, изначально переставленных в ОБРАТНОМ порядке. Вы придумали реализацию алгоритма, для которой существует еще одна неприятная вариация: она очень не любит одинаковые элементы.

В общем, КГ/АМ, уж извините.