Дослідження алгоритму швидкого сортування
Автор: optimist2001 • Февраль 21, 2019 • Лабораторная работа • 2,114 Слов (9 Страниц) • 390 Просмотры
Міністерство освіти і науки України
Вінницький національний технічний університет
Факультет інформаційних технологій та комп’ютерної інженерії
Кафедра комп’ютерних наук
Лабораторна робота №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();
...