Лабораторная работа № 15. Алгоритмы сортировок обменных, выбором, вставками, разделением
Сортировка - это процесс упорядочения набора элементов в возрастающем или убывающем порядке. В рассматриваемых алгоритмах будем считать, что целые положительные и отрицательные числа сортируются по возрастанию.
| Задание
| Краткие теоретические сведения
| | 1. Выполнить программу сортировки пузырьком, записанную в правой части. Опробовать ее работу с различными массивами чисел.
Изменить программу так, чтобы вывод результатов осуществлялся в главной функции main.
Заменить функцию пузырьковой сортировки на шейкерную. Изучить отличия алгоритмов.
| При обменной сортировке пузырьком соседние элементы некоторой последовательности чисел сравниваются между собой. Если первый элемент больше второго, то они меняются местами. Затем сравниваются второй и третий элементы. Процесс продолжается до тех пор, пока все элементы массива не окажутся на своих местах.
| #include < iostream>
using namespace std;
void BubbleSort1(int A[], int N)
{ int i, j, count, key;
for (i = 0; i < N; i++)
{ for (j = 0; j < N - 1; j++)
{ key = j + 1; count = A[key];
if (A[j] > A[key])
{ A[key] = A[j]; A[j] = count; }
}
}
cout< < " Результирующий массив: ";
for (i = 0; i < N; i++) cout< < A[i]< < " ";
}
| void main()
{ setlocale(LC_ALL, " Rus" );
int N; int A[1000];
cout< < " Количество элементов > ";
cin> > N;
for (i = 0; i < N; i++)
{ cout< < i + 1< < " элемент > ";
cin> > A[i];
}
BubbleSort1(A, N);
}
| Перестановка элементов в шейкерной сортировке выполняется аналогично пузырьковой, т. е. два соседних элемента при необходимости меняются местами. При этом не обязательно все просмотры делать в одном направлении. Можно всякий последующий просмотр делать в противоположном направлении и фиксировать нижнюю и верхнюю границу в неупорядоченной части. Просмотр будет выполняться не до конца массива, а до последней перестановки на предыдущем просмотре.
| | 2. В правой части приведены две функции сортировок выбором.
Написать программы с использованием этих функций.
| 
Согласно методу сортировки выбором начиная с первой записи таблицы, осуществляется поиск элемента, имеющего наименьшее значение. После того, как этот элемент найден, он меняется местами с первым элементом.
Затем, начиная со второго элемента массива, осуществляется поиск следующего наименьшего значения ключа. Найденный элемент меняется местами со вторым элементом.
Этот процесс продолжается до тех пор, пока все числа не будут расположены в порядке возрастания.
| | 3. В правой части приведены две функции сортировок вставками.
Написать программы с использованием этих функций и сравнить скорости получения результатов.
| При использовании метода простой вставки весь массив в процессе сортировки делится на две части: упорядо-ченную и неупорядоченную.
Вначале весь массив неупорядочен. На каждом шаге из неупорядоченной части извлекается первый элемент, который вставляется на нужное место упорядоченной части. При этом размер упорядоченной части увеличивается на единицу. В конце весь массив окажется упорядоченным.
Метод Шелла (сортировка вставками с убывающим шагом) состоит в том, что упорядочиваемый массив делится на группы элементов, каждая из которых упорядочивается методом вставки. В процессе сортировки размеры таких групп увеличиваются до тех пор, пока все элементы не войдут в упорядоченную группу.
 Выбор очередной упорядочиваемой группы и ее расположение внутри массива производятся так, чтобы можно было использовать предшествующую упорядоченность.
| | 4. Написать программу, реализующую алгоритм быстрой сортировки Хоара с использованием функций, приведенных в правой части.
Проанализировать алгоритм.
| 
Алгоритм сортировки разделением основан на разбиении массива на две части по некоторому правилу.
Быстрая сортировка была разработана Хоаром и представляет собой рекурсивный алгоритм. Массив делится на две части относительно некоторого значения, называемого медианой. В левой части числа меньше медианы, в правой – больше.
Эти части сортируются независимо, для чего вызывается та же самая функция. Процесс продолжается до тех пор, пока очередная часть массива не станет содержать один элемент.
Функция GetHoarBorder(int A[], int sm, int em); осуществляет разбиение массива.
A[] – исходный массив чисел, sm - индекс первого элемента массива, em - индекс последнего (последний элемент правой части).
| | 5. В правой части приведена программа, в которой определяется количество временных тактов, которые требуются на сортировку по методу пузырька и по методу Шелла.
| #include < ctime>
#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)); //копирование n байтов блока памяти памяти, на который ссылается указатель f, во второй блок памяти, на который ссылается указатель k
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< < endl;
}
return 0;
}
|
6. В соответствии со своим вариантом написать программу для сортировок массивов указанными в таблице методами. Исходные массивы заполняются случайными числами.
Определить зависимость времени выполнения алгоритмов от количества элементов для каждого из алгоритмов. Выполнить моделирование для массивов размером 1000, 2000, 3000, 4000, 5000. Произвести сравнение эффективности алгоритмов (построить график в приложении Excel).
| № варианта
| Методы сортировки массивов
| |
| Сортировка пузырьком, сортировка Шелла, сортировка Хоара
| |
| Шейкерная сортировка, сортировка методом простой вставки, сортировка Хоара
| |
| Сортировка пузырьком, сортировка выбором, сортировка Шелла
| |
| Сортировка Хоара, сортировка Шелла, шейкерная сортировка
| |
| Сортировка разделением, сортировка пузырьком, сортировка Шелла
| |
| Сортировка методом простой вставки, сортировка Хоара, сортировка выбором
| |
| Шейкерная сортировка, сортировка пузырьком, сортировка Хоара
| |
| Сортировка Хоара, сортировка Шелла, шейкерная сортировка
| |
| Сортировка пузырьком, сортировка выбором, сортировка шейкерная
| |
| Сортировка разделением, сортировка выбором, сортировка Шелла
| |
| Сортировка Шелла, сортировка разделением, сортировка пузырьком
| |
| Сортировка Хоара, сортировка выбором, сортировка Шелла
| |
| Сортировка пузырьком, сортировка Шелла, сортировка Хоара
| |
| Шейкерная сортировка, сортировка методом простой вставки, сортировка Хоара
| |
| Сортировка пузырьком, сортировка выбором, сортировка Шелла
| |
| Сортировка методом простой вставки, сортировка Хоара, сортировка пузырьком
|
7. Дополнительное задание. Разработать функцию сортировки квадратичной выборкой и добавить к списку исследуемых сортировок.
Алгоритм квадратичной сортировки. Массив из n элементов делится на группы примерно по Ö n элементов в каждой. В группе выбирается наименьший элемент (его место занимает число, заведомо большее, чем все числа) и пересылается во вспомогательный список. Этот список просматривается, и наименьший его элемент пересылается в окончательный список. Просматриваются попеременно, то вспомогательный список, то группы до тех пор, пока все элементы групп не будут исчерпаны.
В начало практикума
Популярное:
|
