Міністерство науки і освіти України Національний університет “Львівська політехніка” Інститут комп’ютерних наук та інформаційних технологій кафедра програмного забезпечення Звіт з лабораторної роботи № 7 з дисципліни “Алгоритми і структури даних ” Львів 2008 Тема роботи: Ознайомлення із методами сортування. Алгоритм сортування пірахунком Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із методом сортування підрахунком. Виконати лабораторну роботу використавши здобуті знання з методів сортування, зокрема методу сортування підрахунком. ТЕОРЕТИЧНІ ВІДОМОСТІ Сортування підрахунком (англ. Counting sort) — алгоритм впорядкування, що застосовується при малій кількості різних елементів (ключів) у масиві даних. Час його роботи лінійно залежить як від загальної кількості елементів у масиві так і від кількості різних елементів. Ідея алгоритму полягає в наступному: спочатку підрахувати скільки разів кожен елемент (ключ) зуcтрічається в вихідному масиві. Спираючись на ці дані можна одразу вирахувати на якому місці має стояти кожен елемент, а потім за один прохід поставити всі елементи на свої місця. Обчислювальна складність роботи алгоритму становить O(N + K), де N — довжина масиву, та K — величина діапазону. В алгоритмі використовуються додатковий масив, тому ємнісна складність становить E(N + K). В такій реалізації алгоритм є стабільним (не змінює порядок елементів з однаковим ключем). Використання даного алгоритму є доцільним тільки у випадку малих K. Текст програми #include<stdio.h> #include<conio.h> #include<stdlib.h> void main() { unsigned char mas[60000]; unsigned int mas2[256]; int k=0,i,ver=1; for( i=0; i<60000; i++) mas[i]=rand()%256; for(i=0; i<256; i++) mas2[i]=0; for(i=0; i<60000; i++) mas2[mas[i]]++; for(i=0; i<=255; i++) while(mas2[i]>0) { mas[k]=i; mas2[i]--; k++; } for(i=0; i<60000-1; i++) if(mas[i]>mas[i+1]) { puts("Ne sortuje!"); ver=0; break; } if(ver==1) puts("Sortuje!"); getch(); } Результат роботи програми