2018-01-08
231
1. Brian W. KernighanandDennis M. Ritchie «The C ProgrammingLanguage» (SecondEdition). — 1988. [ISBN 0–13–110362–8]
2. Donald E. Knuth «TheArtofComputerProgramming»: «Volume 3: SortingandSearching» (SecondEdition). — 1998. [ISBN 0–201–89685–0]
3. C. A. R. Hoare «Quicksort» // TheComputerJournal, Volume 5, Number 1. — 1962. [ISSN 0010–4620]
Лабораторна робота № 6
Лабораторна робота № 6
Тема роботи: Метод сортування підрахунком.
Мета роботи: Вивчити алгоритм сортування підрахунком. Здійснити програмну реалізацію алгоритму сортування підрахунком. Дослідити швидкодію алгоритму сортування підрахунком.
Короткі теоретичні відомості
Сортування підрахунком (англійською «CountingSort») — алгоритм впорядкування, що застосовується при малій кількості різних елементів (ключів) у масиві даних. Час його роботи лінійно залежить як від загальної кількості елементів у масиві так і від кількості різних елементів.
Ідея алгоритму полягає в наступному: спочатку підрахувати скільки разів кожен елемент (ключ) зустрічається в вихідному масиві. Спираючись на ці дані можна одразу вирахувати на якому місці має стояти кожен елемент, а потім за один прохід поставити всі елементи на свої місця.
|
|
|
В алгоритмі присутні тільки прості цикли довжини N (довжина масиву), та один цикл довжини K (величина діапазону). Отже, обчислювальна складність роботи алгоритму становить O (N + K).
В алгоритмі використовується додатковий масив. Тому алгоритм потребує E (K) додаткової пам’яті.
В такій реалізації алгоритм є стабільним. Саме ця його властивість дозволяє використовувати його як частину інших алгоритмів сортування (наприклад, сортування за розрядами).
Використання даного алгоритму є доцільним тільки у випадку малих K.
