Дослідження алгоритму швидкого сортування

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

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

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

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

Лабораторна робота №5

З дисципліни: “Теорія алгоритмів”

Тема: “ Дослідження алгоритму швидкого сортування ”

Виконав студент групи 1КН-17Б:

 Шептяков І.О.

Перевірив:

Арсенюк І.Р.

Вінниця 2017

Мета: «Дослідити та проаналізувати алгоритм швидкого сортування»

Ідея

    Ідея алгоритму ґрунтується на принципі «розділяй і володарюй».  Масив ділиться на ділянки, у яких обирається «опорний елемент». Потім порівнюються члени ділянки: елементи, що менші опорного, розташовуються зліва від нього, а ті, що більші, - справа. Потім ця ділянка рекурсивно розділяється на 2 менші і виконуються ті самі дії, доки ділянка не стане одиничною.

Приклад роботи алгоритму

Дано масив А[10]. [pic 1]

Далі будуть наведені кроки сортування масиву.

Опорний елемент «6»:

Змінені 0 та 7        [pic 2]

Змінені 1 та 6        [pic 3]

Опорний елемент «0»:

Змінені 0 та 2        [pic 4]

Опорний елемент «5»:

Змінені 4 та 5         [pic 5]

Опорний елемент «2»:

Змінені 1 та 3        [pic 6]

Змінені 3 та 4        [pic 7]

Опорний елемент «8»:

Змінені 8 та 9        [pic 8]

Опорний елемент «6»:

Змінені 7 та 8        [pic 9]

Масив А відсортовано.

Псевдокод

Quicksort(_array,_min,_max)

i = _min

j = _max

ref=_array[(i+j)/2]

while i<=j do

        while _array[i]do i++

        while _array[j]>ref do j--

        if i<=j do

                Поміняти місцями _array[i] та _array[j]

                i++

                j--

        end if

end while

if i<_max do Quicksort(_array,i,_max)

if j>_min do Quicksort(_array,_min,j)

Програмний код алгоритму реалізований на мові C#

namespace Quicksort

{

    public class Program

    {

        static void Quicksort(int[] _array, int _min, int _max)

        {

            int i = _min;

            int j = _max;

            int temp;

            int reference = _array[(_min + _max) / 2];

            while (i <= j)

            {

                while (_array[i] < reference) i++;

                while (_array[j] > reference) j--;

                if (i <= j)

                {

                    temp = _array[i]; _array[i] = _array[j]; _array[j] = temp;

                    i++;

                    j--;

                }

            }

            if (j > _min) Quicksort(_array, _min, j);

            if (i < _max) Quicksort(_array, i, _max);

            return;

        }

        static void Main(string[] args)

        {

            int[] array_sizes = new int[5] { 10000000, 20000000, 50000000, 100000000, 150000000 };

            Console.WriteLine("Random array");

            for (int i = 0; i < array_sizes.Length; i++)

            {

                int[] array = new int[array_sizes[i]];

                Random rand = new Random();

                for (int j = 0; j < array.Length; j++)

                {

                    array[j] = rand.Next();

                }

                Stopwatch timer = new Stopwatch();

                timer.Start();

                Quicksort(array, 0, array.Length - 1);

                timer.Stop();