Дослідження алгоритму сортування за лінійний час
Автор: optimist2001 • Февраль 21, 2019 • Лабораторная работа • 1,365 Слов (6 Страниц) • 578 Просмотры
Міністерство освіти і науки України
Вінницький національний технічний університет
Факультет інформаційних технологій та комп’ютерної інженерії
Кафедра комп’ютерних наук
Лабораторна робота №6
З дисципліни: “Теорія алгоритмів”
Тема: “ Дослідження алгоритму сортування за лінійний час
(сортування розрядами)”
Виконав: студент гр. 1КН-16б Клямчук В’ячеслав
Перевірив: викладач Арсенюк Ігор Ростиславович
Вінниця 2016
Мета
Дослідити та проаналізувати алгоритм сортування масиву за лінійний час. У моєму випадку сортування розрядами
Ідея
Ідея полягає в тому, щоб спочатку впорядкувати всі елементи за молодшим розрядом, потім стабільно впорядкувати за другим розрядом, потім за третім і так далі аж до найстаршого. Оскільки, припускається, що кожен розряд приймає значення з невеликого діапазону, то кожен цикл впорядкування можна виконувати швидко і з малими затратами пам'яті. Також є сортування розрядами починаючи з більших розрядів. Але я буду розглядати LSD-сортування (Least Significant Digit radix sort).
Приклад роботи алгоритму
[pic 1]
Псевдокод
function radixSort(int[] A):
for i = 1 to m
for j = 0 to k - 1
C[j] = 0
for j = 0 to n - 1
d = digit(A[j], i)
C[d]++
count = 0
for j = 0 to k - 1
tmp = C[j]
C[j] = count
count += tmp
for j = 0 to n - 1
d = digit(A[j], i)
B[C[d]] = A[j]
C[d]++
A = B
Програмний код алгоритму реалізований на мові C#
class RadixSorting
{
public static void sorting(int[] arr, int range, int length)
{
ArrayList[] lists = new ArrayList[range];
for (int i = 0; i < range; ++i)
lists[i] = new ArrayList();
for (int step = 0; step < length; ++step)
{
//распределение по спискам
for (int i = 0; i < arr.Length; ++i)
{
int temp = (arr[i] % (int)Math.Pow(range, step + 1)) /
...