Алгоритмы сортировок и их реализации


Главная
Меню сайта
Статистика

Наш опрос
Оцените мой сайт
Всего ответов: 267

Быстрая сортировка



Быстрая сортировка (англ. quicksort) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Даёт в среднем O(n log n) сравнений при упорядочении n элементов. В худшем случае, однако, получается O(n2) сравнений. Обычно на практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n log n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре, и на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.

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

 

Алгоритм

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

  1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом.
  2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него.
  3. Рекурсивно упорядочиваем подсписки, лежащие слева и справа от опорного элемента.

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

Улучшения

При выборе опорного элемента из данного диапазона случайным образом, худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки — O(n log n).

Достоинства и недостатки

Достоинства:

  • Самый быстродействующий из всех существующих алгоритмов обменной сортировки — быстрее него только специализированные алгоритмы, использующие специфику сортируемых данных.
  • Простая реализация.
  • Хорошо сочетается с алгоритмами кэширования и подкачки памяти.
  • Хорошо работает на «почти отсортированных» данных.

Недостатки:

  • Требует много дополнительной памяти — n ячеек в худшем случае. Правда, вероятность такого расклада ничтожна.
  • Неустойчив — если требуется устойчивость, приходится расширять ключ.

Реализация на С

 int partition (int *a, int p, int r)
{
int x = a[r];
int i = p - 1;
int j;
int tmp;
for (j = p; j < r; j++)
if (a[j] < x)
{
i++;
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
i++;
tmp = a[r];
a[r] = a[i];
a[i] = tmp;
return i;
} // partition
 void quicksort (int *a, int p, int r)
{
int q;
if (p < r)
{
q = partition (a, p, r);
quicksort (a, p, q-1);
quicksort (a, q+1, r);
} // quicksort
}


Реализация на Pascal
type
list = array[1..max] of integer;

procedure quicksort(var a: list; Lo,Hi: integer);

procedure sort(l,r: integer);
var
i,j,x,y: integer;
begin
i:=l; j:=r; x:=a[(l+r) DIV 2];
repeat
while a[i]<x do i:=i+1;
while x<a[j] do j:=j-1;
if i<=j then
begin
if a[i] <> a[j] then BEGIN y:=a[i]; a[i]:=a[j]; a[j]:=y; END;
i:=i+1; j:=j-1;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;

begin {quicksort};
sort(Lo,Hi);
end;



Литература



Copyright MyCorp © 2024
Создать бесплатный сайт с uCoz