7.5 Алгоритм быстрой сортировки

    Классификационное название этого алгоритма − обменная сортировка с разделением.


    Разработан Чарльзом Э. Р. Хоаром в 1962 г.


    Один из лучших из универсальных алгоритмов (одновременно не очень сложных), разработанных к настоящему времени. Относится к группе алгоритмов обменной сортировки (как и пузырьковая сортировка).


    Сортируемый массив разбивается на два подмассива, для чего сначала выбирается пограничное значение − компаранд (т.е. значение, с которым будут сравниваться другие элементы массива). Все элементы, бОльшие компаранда, переносятся в один подмассив, а меньшие − в другой. Весь процесс повторяется для каждого подмассива до тех пор, пока весь массив не будет упорядочен.

    Процесс сортировки носит рекурсивный характер.


    Перенос в подмассивы может происходить следующим образом:
    Пусть имеются два индекса − i и j, причем сначала i = 0, j = N − 1.
    Сравниваются элементы k[ i ] и k[ j ], если обмен не требуется, то j уменьшается на единицу и сравнения повторяются, и j с каждым шагом уменьшается на 1.
    После первого обмена i увеличивается на единицу и сравнения повторяются с увеличением i на 1, пока не произойдет следующий обмен, после которого опять начинает уменьшаться j. И так до тех пор, пока i и j не станут равны друг другу.


    Представляет интерес вопрос о выборе компаранда. Существуют варианты:
    − случайный выбор − иногда бывает наилучшим;
    − выборка небольшого числа элементов из подмассива и использовании в качестве компаранда медианы этой выборки. Широко распространенным и эффективнным является метод выборки трех элементов и взятие среднего из них;
    − один из экстремумов − наихудший вариант, хотя алгоритм работает и в этом случае;
    − элемент, находящиися в середине каждого из подмассивов.


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

    Процедура быстрой сортировки (метод Хоара) на языке "Паскаль"

    procedure quicksort(item:array of char; left,right:integer);
    var
      i,j:Integer;
      x,y:char;
    begin
      i:=left;
      j:=right;
      x:=item[int((left+right)/2)];
      repeat
        while (item[i]<x) and (i<right) do
          i:=i+1;
        while (x<item[j]) and (j>left) do
          j:=j-1;
        if i<=j then
        begin
          y:=item[i];
          item[i]:=item[j];
          item[j]:=y;
          i:=i+1;
          j:=j-1;
        end;
      until i<j;
      if left<j then
        quick(item,left,j);
      if i<right then
        quick(item,i,right);
    end.

    Аналогичная процедура на языках C/C++

    void quick_sort(char* item,int left,int right)
    {
      int i,j;
      char comp,buf;
      i=left; j=right;
      comp=item[(left+right)/2];    // Компаранд
      do {
        while(item[i]<comp && i<right)
          i++;
        while(comp<item[j] && j>left)
          j--;
        if(i<=j) {
          buf=item[i];  // Обмен
          item[i]=item[j];
          item[j]=buf;
          i++; j--;
        }
      } while(i<=j);
      if(left<j)
        quick_sort(item,left,j);  // Рекурсивный вызов
      if(i<right)
        quick_sort(item,i,right);
    }


    Изменение массива при сортировке по алгоритму Хоара будет имеет вид:

      f, d, a, c, b, e
      e, d, a, c, b, f
      b, c, a, d, e, f
      a, b, c, d, e, f


    Для оптимальной сортировки в качестве компаранда следует выбрать элемент, расположенный точно в середине диапазона значений текущего подмассива. Однако для большинства наборов данных поиск такого элемента может вылиться в самостоятельную сортировку.


    Характеристики: Среднее число сравнений Nlog2N, среднее число перестановок 1/6Nlog2N.


    У этого алгоритма есть одна отрицательная особенность: если для каждого текущего подмассива компарандом является текущий экстремум, то алгоритм становится N-квадратичным. Однако вероятность такого события невысока.


    < Назад | Вперед >

    Хостинг от uCoz