Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
роботи
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
Не вказано
Кафедра:
Кафедра програмного забезпечення
Інформація про роботу
Рік:
2008
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Алгоритми і структури даних
Група:
ПІ-11
Частина тексту файла (без зображень, графіків і формул):
Міністерство науки і освіти України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
кафедра програмного забезпечення
Звіт з лабораторної роботи № 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();
}
Результат роботи програми
Висновок: Вивчив та дослідив метод сортування, як один із методів обробки даних. Ознайомився із методом сортування підрахунком. Виконав лабораторну роботу використавши здобуті знання з методів сортування, зокрема методу сортування підрахунком.
28.01.2013 14:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора