Сортування підрахунком

В даній роботі буде розглядатися швидке сортування (англ. Quick Sort), алгоритм якого був розроблений Чарльзом Хоаром (англ. Charles А. Hoare) – англійським вченим, що працює в галузі інформатики та обчислювальної техніки. Доречи, Хоар розробив цей метод в 1960 році для машинного перекладу: річ у тім, що в той час словник зберігався на магнітній стрічці, і якщо впорядкувати все слова в тексті, їх переклади можна отримати за один прогін стрічки. Цей метод є розвиненням метода простого обміну і настільки ефективний, що його почали називати методом швидкого сортування.
У наш час цей алгоритм сортування використовується в задачах обробки даних, пошуку об’єктів, для оптимізації розміщення даних, стиснення інформації, криптографії, цифровій обробці сигналів та інше.

ВСТУП…………………………………………………………………………….....3
ПОСТАНОВКА ЗАДАЧІ……………………………………………………..….…4
ВХІДНІ ТА ВИХІДНІ ДАНІ……………………………………………………….4
1.ОПИС ШВИДКОГО СОРТУВАННЯ ……………………………………...........5
1.1.Етап розбиття………………………………………………………………….6
2. ЕФЕКТИВНІСТЬ ШВИДКОГО СОРТУВАННЯ…………………………..…..9
2.1. Випадки поведінки алгоритму……………………………………………....9
2.2. Переваги та недоліки………………………………………………………..11
2.3. Способи покращення алгоритму…………………………………………...12
2.4. Порівняння ефективності деяких алгоритмів сортувань…………………14
ВИСНОВОК…………………………………………………………………..…….17
ДОДАТОК 1……………………………………………………………………..….18
ДОДАТОК 2………………………………………………………………………...20
СПИСОК ЛІТЕРАТУРИ…………………………………………………………...23