Файл: Сортировка слиянием.pdf

Нужна и хорошая аппаратная поддержка; нельзя считать ее само собой разумеющимся фактом. В некоторых машинах имеются эффективные способы доступа к малым порциям данных, но некоторые другие типы машин существенно снижают быстродействие на этих операциях. Поскольку алгоритмы поразрядной сортировки достаточно просто выражаются через операции извлечения разряда числа, задача достижения максимальной производительности алгоритма поразрядной сортировки может оказаться увлекательным введением в аппаратное и программное обеспечение [10, С. 405].

3. Программа сортировки данных

Программа написана на языке С++ (код программы представлен в приложении). В программе реализованы все рассматриваемые в работе алгоритмы сортировки для сортировки массива целых чисел, а именно: сортировка выбором, сортировка вставками, пузырьковая сортировка, сортировка Шелла, быстрая сортировка, сортировка слиянием, пирамидальная сортировка, поразрядная сортировка.

Первая часть программы демонстрирует работоспособность наших функций сортировки для сортировки массива из 10 элементов.

Вторая часть программы измеряет и выводит на экран время работы наших функций сначала при сортировке массива из 1000000 случайных элементов, затем (через запятую) время при сортировке уже отсортированного массива из 1000000 элементов.

Результат работы программы выглядит следующим образом

Эти данные позволяют оценить быстродействие алгоритмов в сравнении друг с другом, а так же естественность этих алгоритмов. Очевидно, что элементарные методы сортировки (выбором, вставками, пузырьком) сильно проигрывают по скорости более современным методам при сортировке случайной последовательности. Однако сортировки вставками и пузырьком, имея минимальное время выполнения при обработке уже отсортированных данных, ведут себя наиболее естественно. Из-за чего им вполне может быть отдано предпочтение при выборе для решения некоторых задач. Но для решения большинства простых задач закономерным выбором будет быстрая сортировка. Именно этот алгоритм и его модификация, например, использованы в стандартных библиотечных функциях C/C++ qsort и std::sort.

ЗАКЛЮЧЕНИЕ

Наверно, никакая другая проблема не породила такого количества разнообразнейших решений, как задача сортировки. Существует ли некий «абсолютный» алгоритм? Скорей всего, нет. Выбор алгоритма очень сильно зависит от условия задачи, которую необходимо решить. Однако, имея приблизительные характеристики исходных данных, можно подобрать метод, работающий оптимальным образом.

Методы сортировки являются критическими компонентами многих прикладных систем. Довольно часто предпринимаются специальные меры, чтобы сортировка работала максимально быстро или могла обрабатывать очень большие файлы. Нередко появляются усовершенствования вычислительных систем, или специальные аппаратные средства, повышающие производительность сортировки, или просто новые компьютерные системы, основанные на новых архитектурных решениях. В таких случаях представления об относительной стоимости операций, выполняемых над сортируемыми данными, могут оказаться неверными.

Проблема поддержки эффективных методов сортировки рано или поздно встает перед любой новой компьютерной архитектурой. В самом деле, исторически сложилось так, что сортировка служит своеобразным испытательным полигоном при разработке новой архитектуры, поскольку она и практически важна, и легка для понимания. Хочется знать не только то, какой из известных алгоритмов и в силу каких причин выполняется на новой машине лучше других, но также и то, можно ли при разработке нового алгоритма воспользоваться конструктивными особенностями конкретной машины.

Сортировка является одной из фундаментальных алгоритмических задач программирования. Практически каждый алгоритм сортировки можно разбить на 3 части: сравнение, определяющее упорядоченность пары элементов; перестановку, меняющую местами пару элементов; собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены.

Для оценки трудоемкости алгоритмов сортировки используются параметры: время сортировки, дополнительная память, устойчивость и естественность поведения

По сфере применения алгоритмы сортировок классифицируются на алгоритмы внутренних и внешних сортировок.

Таким образом, в первой главе курсовой работы был рассмотрен исторический аспект методов сортировки данных с конца XIX века по настоящее время, приведены ключевые фигуры, сыгравшие роль в развитии алгоритмов сортировки.

Во второй главе были рассмотрены несколько методов сортировки данных. Более подробно – элементарные методы сортировки – сортировка выбором, сортировка вставками, пузырьковая сортировка, сортировка методом Шелла, быстрая сортировка. Также в курсовой работе были затронуты метод сортировки слиянием и пирамидальная сортировка.

В третий главе описана программа, в которой реализованы все рассматриваемые в работе алгоритмы сортировки для сортировки массива целых чисел.

Сортировка играет исключительно важную роль во многих практических приложениях, и разработка эффективных методов сортировки часто является одной из первых задач, решаемых на новых компьютерных архитектурах и в новых средах программирования. Учитывая то, что новые разработки строятся на старом опыте, важно иметь представление о наборе технических средств, рассмотренных в курсовой работе.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Алгоритмы. Построение и анализ/ Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. – М.: Вильямс, 2012. – 1296 с.
2. Ахо А. В., Хопкрофт Д. Э., Ульман Д. Д. Структуры данных и алгоритмы / Под ред. А. А. Минько. — М.: Вильямс, 2000. — С. 231
3. Заславская О.Ю., Кравец, О.Я., Говорский А.Э. Архитектура компьютера и вычислительных систем (лекции, лабораторные работы, контрольные задания): Учебник/О.Ю. Заславская, О.Я. Кравец, А.Э. 4. Говорский; под ред. чл.-корр.РАО, д-ра техн. наук профессора С.Г. Григорьева. – Воронеж: «Научная книга», 2011. – 300 с.
4. Зубов В.С., Фальк В.Н. Новый алгоритм быстрой сортировки выбором //Вестник МЭИ. 2006. №6. С. 62-68.
5. Зубов В.С., Шевченко И.В. О статусе пирамидальной сортировки // Вестник МЭИ. 2005. №3. С.89.
6. Кнут Д. Искусство программирования. Том 3. Сортировка и поиск. – М.: Вильямс, 2014. – 824 с.
7. Левитин А. В. Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 144–146. — 576 с.
8. Макконнелл Дж. Основы современных алгоритмов / Под ред. С. К. Ландо. — М.: Техносфера, 2004. — С. 72-76.
9. Полунов Ю. АВТОРА!!! // PCWeek/RE. - 2006. – №20.
10. Седжвик Р. Алгоритмы на C++. - М.: Вильямс, 2011 - 1056 с.
11. Частиков А. Архитекторы компьютерного мира. – СПб.: БХВ-Петербург, 2002 – 384 с.

Приложение 1

Программа сортировки данных

#include <iostream>

#include <time.h>

using std::cout;

using std::cin;

//функция swap меняет местами значения элементов

//используется в большинстве наших функций сортировки

void swap(int& a, int& b)

{

int temp;

temp = a;

a = b;

b = temp;

}

//сортировка выбором

void selection_sort(int *arr, int size)

{

for (int i = 0; i < size - 1; i++)

{

int min_index = i; // индекс минимального элемента

//ищем минимальный из всех элементов правее i

for (int j = i + 1; j < size; j++)

{

if (arr[j] < arr[min_index])

{

min_index = j; //запоминаем индекс

}

}

if (min_index != i)

{

//перестановка текущего элемента с минимальным

swap(arr[i], arr[min_index]);

}

}

}

// сортировка вставками

void insertion_sort(int *arr, int size)

{

int temp; // временная переменная для хранения значения элемента сортируемого массива

for (int i = 1; i < size; i++)

{

temp = arr[i]; // запоминаем значение текущего элемента массива

int j = i - 1; // запоминаем индекс предыдущего элемента массива

while (j >= 0 && arr[j] > temp) // пока индекс не равен 0 и предыдущий элемент массива больше текущего

{

// перестановка элементов массива

arr[j + 1] = arr[j];

arr[j] = temp;

j--;

}

}

}

// пузырьковая сортировка

void bubble_sort(int *arr, int size)

{

bool exit = false; // булевая переменная для выхода из цикла, если массив отсортирован

while (!exit) // пока массив не отсортирован

{

exit = true;

for (int i = 0; i < (size - 1); i++) // внутренний цикл

{

if (arr[i] > arr[i + 1]) // сравниваем два соседних элемента

{

// выполняем перестановку элементов массива

swap(arr[i], arr[i + 1]);

exit = false; // на очередной итерации была произведена перестановка элементов

}

}

}

}

//сортировка Шелла

void shells_sort(int *arr, int size)

{

for (int step = size / 2; step > 0; step = step / 2)

{

for (int i = 0; i < (size - step); i++)

{

//будем идти начиная с i-го элемента

for (int j = i; j >= 0 && arr[j] > arr[j + step]; j--)

//пока не пришли к началу массива

//и пока рассматриваемый элемент больше

//чем элемент находящийся на расстоянии шага

{

//меняем их местами

swap(arr[j], arr[j + step]);

}

}

}

}

//рекурсивная быстрая сортировка

// left - левая граница массива (индекс первого элемента)

// right - правая граница массива (индекс последнего элемента)

void quick_sort(int *arr, int left, int right)

{

// middle - центральный опорный элемент

int middle = arr[left + (right - left) / 2];

int i = left;

int j = right;

// цикл продолжается, пока индексы i и j не сойдутся

while (i <= j)

{

while (arr[i] < middle) i++; // пока i-ый элемент не превысит опорный

while (arr[j] > middle) j--; // пока j-ый элемент не окажется меньше опорного

if (i <= j)

{

swap(arr[i++], arr[j--]);

}

}

// рекурсивные вызовы, если есть, что сортировать

if (i < right)

quick_sort(arr, i, right);

if (left < j)

quick_sort(arr, left, j);

}

// рекурсивная сортировка слиянием

// up - массив, который нужно сортировать

// down - массив с таким же размером как у 'up', используется как буфер

// left - левая граница массива (индекс первого элемента)

// right - правая граница массива (индекс последнего элемента)

// возвращает указатель на отсортированный массив

// (из-за особенностей работы данной реализации отсортированная версия массива может оказаться либо в 'up', либо в 'down').

int* merge_sort(int *up, int *down, int left, int right)

{

if (left == right)

{

down[left] = up[left];

return down;

}

// middle - индекс центрального опорного элемента

int middle = left + (right - left) / 2;

// разделяй и сортируй

int *l_buff = merge_sort(up, down, left, middle);

int *r_buff = merge_sort(up, down, middle + 1, right);

// слияние двух отсортированных половин

int *target = l_buff == up ? down : up;

int width = right - left, l_cur = left, r_cur = middle + 1;

for (int i = left; i <= right; i++)

{

if (l_cur <= middle && r_cur <= right)

{

if (l_buff[l_cur] < r_buff[r_cur])

{

target[i] = l_buff[l_cur];

l_cur++;

}

else

{

target[i] = r_buff[r_cur];

r_cur++;

}

}

else if (l_cur <= middle)

{

target[i] = l_buff[l_cur];

l_cur++;

}

else

{

target[i] = r_buff[r_cur];

r_cur++;

}

}

return target;

}

// подфункция для heap_sort

// функция "просеивания" через кучу - формирование кучи

void sift(int *arr, int root, int bottom)

{

int max_сhild; // индекс максимального потомка

bool done = false; // флаг того, что куча сформирована

// Пока не дошли до последнего ряда

while ((root * 2 <= bottom) && (!done))

{

if (root * 2 == bottom) // если в последнем ряду,

max_сhild = root * 2; // запоминаем левый потомок

// иначе запоминаем больший потомок из двух

else if (arr[root * 2] > arr[root * 2 + 1])

max_сhild = root * 2;

else

max_сhild = root * 2 + 1;

// если элемент вершины меньше максимального потомка

if (arr[root] < arr[max_сhild])

{

// меняем их местами

swap(arr[root], arr[max_сhild]);

root = max_сhild;

}

else // иначе

done = true; // пирамида сформирована

}

}

// пирамидальная сортировка (сортировка кучей)

void heap_sort(int *arr, int size)

{

// Формируем нижний ряд пирамиды

for (int i = (size / 2) - 1; i >= 0; i--)

sift(arr, i, size - 1);

// Просеиваем через пирамиду остальные элементы

for (int i = size - 1; i >= 1; i--)

{

swap(arr[0], arr[i]);

sift(arr, 0, i - 1);

}

}

// поразрядная рекурсивная MSD сортировка

// bit - маска двоичного разряда

void radix_sort(int *arr, int size, unsigned bit = 0x80000000)

{

if (!bit) // если маска разяряда равна 0, ничего не делаем

return;

if (size < 2) // если массив из менее чем двух элементов, ничего не делаем

return;

int last = 0;

if (bit == 0x80000000) // старший бит в int определяет знак числа, поэтому

{

// сортируем так, чтобы все элементы со знаком -,

// оказались перед элементами со значком +

for (int i = 0; i < size; i++)

{

if ((arr[i] & bit))

swap(arr[last++], arr[i]);

}

}

else //для остальных разрядов

{

// сортируем так, чтобы все элементы со значением двоичного разряда,

//определенного маской bit, равным 0 оказались перед элементами со значением этого разряда равным 1

for (int i = 0; i < size; i++)

{

if ((arr[i] & bit) == 0)

swap(arr[last++], arr[i]);

}

}

// повторяем для каждой из получившихся частей со следующим разрядом

radix_sort(arr, last, bit >> 1);