Швидке сортування

Матеріал з Вікіпедії — вільної енциклопедії.

Швидке сортування (англ. Quick Sort) — алгоритм сортування, що не потребує додаткової пам'яті і виконує в середньому $\;O(n\log\;n)$ операцій. Так як алгоритм використовує дуже прості цикли і операції, він працює швидше інших алгоритмів, що мають таку ж асимптотичну оцінку складності.

Ідея алгоритму полягає в переставлянні елементів масиву таким чином, щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої. Впорядкування кожної з частин вудбувається рекурсивно. Алгоритм швидкого сортування може бути реалізован як на масиві, так і на двонаправленому списку.

Зміст

1 Історія
2 Псевдокод алгоритму
- 2.1 Класичний алгоритм
- 2.2 Сучасний алгоритм
3 Аналіз
4 Модифікації

[ред.] Історія

Алгоритм розробив англійський вчений в області інформатики Чарльз Хоар. Швидке сортування розроблялось для використання при машинному перекладі. На сьогодні, це найбільш популярний алгоритм сортування і він входить до стандартних бібліотек більшості мов програмування.

[ред.] Псевдокод алгоритму

[ред.] Класичний алгоритм

В класичному варіанті, запропонованому Хоаром, з масиву обирався один елемент, і весь масив розбивався на дві частини по принцупу: в першій частині — ті що не більші даного елементу, в другій частині — ті що не менші даного елемента. Процедура $Q u i c k s o r t (A, p, q)$ здійснює часткове впорядкування масиву $\;A$ з p-го по q-ий індекс:


1 if  return;
2 
3 
4 
5 while  do
6       repeat
7             
8       until 
9       repeat
10            
11      until 
12      if 
13         then Поміняти 
14 
15

[ред.] Сучасний алгоритм

На сьогодні в стандартних бібліотеках використовують таку реалізацію алгоритму:


1 
2 
3 for  to  
4 do  if 
5     then 
6          Поміняти 
7 
8 Поміняти 
9 return


1 if  return;
2 
3 
4

[ред.] Аналіз

[ред.] Модифікації

Отримано від "http://uk.wikipedia.org../../../%D1%88/%D0%B2/%D0%B8/%D0%A8%D0%B2%D0%B8%D0%B4%D0%BA%D0%B5_%D1%81%D0%BE%D1%80%D1%82%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F.html"

Категорія: Алгоритми сортування

Швидке сортування

Матеріал з Вікіпедії — вільної енциклопедії.

Зміст

[ред.] Історія

[ред.] Псевдокод алгоритму

[ред.] Класичний алгоритм

[ред.] Сучасний алгоритм

[ред.] Аналіз

[ред.] Модифікації

Views

Навігація

Пошук

Іншими мовами