Лабораторная работа № 6. Алгоритмы сортировок обменных, выбором, вставками, разделением

Сортировка - это процесс упорядочения набора элементов в возрастающем или убывающем порядке. В рассматриваемых алгоритмах будем считать, что целые положительные и отрицательные числа сортируются по возрастанию.

Задание	Краткие теоретические сведения
1. Выполнить программу, записанную в правой части. Опробовать ее работу с различными массивами чисел. Изменить программу так, чтобы вывод результатов осуществлялся в главной функции main. Заменить функцию пузырьковой сортировки на шейкерную. Изучить отличия алгоритмов.	При обменной сортировке пузырьком соседние элементы некоторой последовательности чисел сравниваются между собой. Если первый элемент больше второго, то они меняются местами. Затем сравниваются второй и третий элементы. Процесс продолжается до тех пор, пока все элементы массива не окажутся на своих местах. Ниже представлена функция шейкерной сортировки: void ShakerSrt(int B[], int n) { int bf, fs = 0, m = 1, ls = n; for(; fs<ls; m>0?++fs:ls) { for (int i = m > 0? fs: ls; m > 0? (i < ls): i > fs); m > 0? ++i: --i) { if ((B[i]>B[i+1])&&(m > 0)) { bf=B[i]; B[i]=B[i-1]; B[i-1]=bf; } if ((B[i]<B[i-1])&&(m < 0)) { bf=B[i]; B[i]=B[i-1]; B[i-1]=bf; } } m = -m; } }
2. В правой части приведены две функции сортировок выбором. Написать программы с использованием этих функций.	Согласно методу сортировки выбором начиная с первой записи таблицы, осуществляется поиск элемента, имеющего наименьшее значение. После того, как этот элемент найден, он меняется местами с первым элементом. Затем, начиная со второго элемента массива, осуществляется поиск следующего наименьшего значения ключа. Найденный элемент меняется местами со вторым элементом. Этот процесс продолжается до тех пор, пока все числа не будут расположены в порядке возрастания.
3. В правой части приведены две функции сортировок вставками. Написать программы с использованием этих функций и сравнить скорости получения результатов.	При использовании метода простой вставки весь массив в процессе сортировки делится на две части: упорядоченную и неупорядоченную. Вначале весь массив неупорядочен. На каждом шаге из неупорядоченной части извлекается первый элемент, который вставляется на нужное место упорядоченной части. При этом размер упорядоченной части увеличивается на единицу. В конце весь массив окажется упорядоченным. Метод Шелла (сортировка вставками с убывающим шагом) превосходит метод простой вставки. Он состоит в том, что упорядочиваемый массив делится на группы элементов, каждая из которых упорядочивается методом вставки. В процессе сортировки размеры таких групп увеличиваются до тех пор, пока все элементы не войдут в упорядоченную группу. Выбор очередной упорядочиваемой группы и ее расположение внутри массива производятся так, чтобы можно было использовать предшествующую упорядоченность.
4. Написать программу, реализующую алгоритм быстрой сортировки Хоара с использованием функций, приведенных в правой части. Проанализировать алгоритм.	Алгоритм сортировки разделением основан на разбиении массива на два по некоторому правилу. Быстрая сортировка была разработана Хоаром и представляет собой рекурсивный алгоритм. Массив делится на две части относительно некоторого значения, называемого медианой (в левой части числа меньше медианы, в правой – больше). Эти части сортируются независимо, для чего вызывается та же самая функция. Процесс продолжается до тех пор, пока очередная часть массива не станет содержать один элемент. Функция GetHoarBorder(int m[], int sm, int em);осуществляет разбиение массива. m[] – исходный массив чисел, sm - индекс первого элемента массива, em - индекс последнего элементов массива (последний элемент правой части).
5. В правой части приведена программа, в которой определяется количество временных тактов, которые требуются на сортировку по методу пузырька и по методу Шелла. В этой программе функция memcpy копирует n байтов блока памяти, на который ссылается указатель f, во второй блок памяти, на который ссылается указатель k. Функция clock(); возвращает количество временных тактов, прошедших с начала запуска программы. Написать краткие комментарии к операторам в главной функции.	#include <ctime> // для clock() #include <stdlib.h> #include <iostream> using namespace std; int* SortBuble(int m[], int lm) { int buf; for(int i = 0; i < lm; i++) for (int j = 0; j < lm-i-1; j++) if (m[j] > m[j+1]) { buf = m[j]; m[j] = m[j+1]; m[j+1] = buf; } return m; }; int* SortShell(int m[], int lm) { int buf; bool sort; for (int g = lm/2; g > 0; g/=2) do {sort = false; for (int i = 0, j = g; j < lm; i++,j++) if (m[i] > m[j]){sort = true; buf = m[i]; m[i] = m[j]; m[j] = buf;} } while (sort); return m; } int GetRandKey(int reg = 0)// генерация случайных ключей { if (reg > 0) srand((unsigned)time(NULL)); int rmin = 0; int rmax = 100000; return (int)(((double) rand()/(double) RAND_MAX) * (rmax-rmin) + rmin); } int main() { setlocale (LC_CTYPE, "Russian"); const int N=50000; int k[N], f[N]; clock_t t1, t2; GetRandKey (1); for (int i=0; i<N; i++) f[i]=GetRandKey(0); for (int n = 10000; n<=N; n+=10000) { cout <<"n = " <<n <<endl; cout << "SortPuzirek "; memcpy(k, f, n*sizeof(int)); t1 = clock(); SortBuble(k, n); t2 = clock(); cout <<"Прошло "<<t2-t1 <<" тактов времени"<<endl; cout << "SortShell "; memcpy(k, f, n*sizeof(int)); t1 = clock(); SortShell(k, n); t2 = clock(); cout <<"Прошло "<<t2-t1 <<" тактов времени"<<endl; } return 0; }

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

Определить зависимость времени выполнения алгоритмов от количества элементов для каждого из алгоритмов. Выполнить моделирование для массивов размером 1000, 2000, 3000, 4000, 5000. Произвести сравнение эффективности алгоритмов (построить график в приложении Excel).

В начало практикума

Лабораторная работа № 7. Алгоритмы сортировок подсчетом, пирамидальных, слиянием,