Дослідження алгоритму сортування за лінійний час

Міністерство освіти і науки України

Вінницький національний технічний університет

Факультет інформаційних технологій та комп’ютерної інженерії

Кафедра комп’ютерних наук

Лабораторна робота №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)) /