Курсовая. Исследование улучшенных методов сортировки (быстрая и пирамидальная сортировки)
 Скачать 0.79 Mb.
|
Insert(void);
PyramidSort(void);
QuickSort(void);
Sort() O ( |
Введение
Теоретическая часть
Проектная часть
Заключение
Список, использованных источников
Структура основной программы. Описание основной программы.
Структура модуля работы с файлами, функции содержащиеся в модуле (описание блок-схемы и текста подпрограммы)
Листинг программы
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ...............................................................................5
Алгоритмы сортировки данных, методы сортировки данных….......5
Быстрая сортировка................................................................................8
Пирамидальная сортировка .................................................................11
ПРАКТИЧЕСКАЯ ЧАСТЬ...............................................................................15
Постановка задачи.................................................................................15
Программирование задачи....................................................................16
Результаты исследования......................................................................20
), а O (n*log n), т.е. наиболее быстрая для сортировки.Суть метода:
Вначале имеем исходную, неотсортированную последовательность. Из нее строится структура данных – пирамида. Пирамида обладает тем свойством, что в ее вершине находится максимальный элемент. Кроме того, вершина – это элемент структуре пирамиды с начальным индексом. Поэтому чтобы выбрать из пирамиды максимальный элемент – не нужно делать вообще ничего – нужно просто взять этот начальный элемент структуры пирамиды.
Основные итерации:
- вынимаем вершину пирамиды;
- на ее место встает последний в пирамиде элемент;
- «просеиваем» этот элемент сквозь пирамиду;
- восстанавливаем пирамиду.
И так до последней итерации, на которой из всей пирамиды останется только вершина, которую мы и вставим в конец нашей полученной, отсортированной последовательности. После того как вставлен последний элемент на вершину – пирамида теряет свои свойства, становится «разбалансированной». Поэтому дальше нужно этот элемент поставить в соответствующее ему место, а на вершину восстановить максимальный элемент.
Имеются две особенности алгоритма:
- Алгоритм относительно медленно работает, когда число сортируемых элементов менее 100. Для малого количества элементов желательно использовать сортировочные сети.
- Когда количество сортируемых данных начинает превышать размер кэша, скорость сортировки падает. Это вызвано тем, что алгоритм обращается к элементам массива довольно случайным образом. По мере того, как все меньшая часть данных уменьшается в кэше, скоростью работы оперативной памяти, а не скоростью работы кэша.
Реализация пирамидальной сортировки на Си:
#include
#include
//Функция "просеивания" через кучу - формирование кучи
void siftDown(int *numders, int root, int bottom)
{
int maxChild; //индекс максимального потомка
int done = 0; //флаг того, что куча сформирована
//пока не дошли до последнего ряда
while ((root * 2 <= bottom) && (!done))
{
if (root * 2 == bottom) //если мы в последнем ряду
maxChild = root * 2 //запоминаем левый поток
//иначе запоминаем большой потомок из двух
else if (numbers[root * 2] > numbers[root * 2 +1])
maxChild = root * 2;
else
maxChild = root * 2 + 1
//если элемент вершины меньше максимального потомка
if (numbers[root] < numers[maxChild])
{
int temp = numers[root]; //меняем их местами
numbers[root] =n numbers[maxChild] = temp;
riit = maxChild;
}
else
done = 1; //пирамида сформирована
}
}
//функция сортировки на куче
void heapSort(int *numbers, int array_size)
{
//формируем нижний ряд пирамиды
for (int i = (array_size / 2); i >= 0; i--)
siftDown(numbers, i, array_size - 1);
//просеиваем через пирамиду остальные элементы
for (int i = array_size - 1; i >= 1; i--)
{
int temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
siftDown(numbers, i - 1);
}
}
int main()
{
int f[10];
// заполнение массива случайными числами
for (int i = 0; i<10; i++)
a[i] = rand() % 20 - 10;
//вывод элементов массива до сортировки
for (int i = 0; i<10; i++)
printf("%d ", a[i]);
printf("\n");
headSort(a, 10); //вызов функции сортировки
//вывод элементов массива после сортировки
for (int i = 0; i<10; i++)
printf("%d ", a[i]);
printf("\n");
getchar();
return 0;
}
2.ПРАКТИЧЕСКАЯ ЧАСТЬ
2.1. Постановка задачи
1.Осуществить исследование улучшенных методов сортировки:
- быстрая сортировка
- пирамидальная сортировка
2.Исследование осуществить, используя массивы упорядоченных по возрастанию, убыванию и неупорядоченных чисел по 10,100,1000 и 10000 элементов.
3.Сравнить количество перестановок и сравнений. Результаты оформить в виде таблиц, графиков.
4.Реализовать исследование с помощью любого языка программирования (для реализации поставленной задачи мы используем язык программирования С++).
5.Результаты исследования вывести на экран.
2.2. Программирование задачи
Для реализации поставленной задачи необходимо, чтобы программа выполняла следующие функции:
Вводился размер массива.
Производилась сортировка согласно заданным условиям (по возрастанию, по убыванию).
Подсчитывала количество сравнений, перестановок.
Выводила результаты на экран.
Для этого пропишем условия исполнения к каждому методу сортировки (реализация показана на примере быстрой сортировки).
- Сортировка по возрастанию:
void QuickSort::Launch(int* x, int size) {
long i = 0, j = size ; // начальные значения
int temp, p;
p = x[ size>>1 ];
do {
while (x[i] < p){
i++;
this->CountEquals();
}
while (x[j] > p){
j--;
this->CountEquals();
}
- Сортировка по убыванию:
oid QuickSort::Launch1(int* x, int size) {
long i = 0, j = size ; // начальные значения
int temp, p;
p = x[ size>>1 ];
do {
while (x[i] > p){
i++;
this->CountEquals();
}
while (x[j] < p){
j--;
this->CountEquals();
}
- счетчик перестановок, сравнений: if (i <= j) {
temp = x[i]; x[i] = x[j]; x[j] = temp;
this->CountSwap();
i++; j--;
}
Отдельно прописываются все функции и для пирамидальной сортировки. После описания всех условий исследования, переходим к тестированию.
В начале выполнения программы в окне консоли выходит сообщение: “Vvtdite razmer massiva”, где пользователь вводит размер массива, исходя из полученной задачи.
Рис.1
После введения размера массива, на экране появляются данные по сортировке массива (элементы сортируются согласно прописанным условиям), а также имеются данные по количеству перестановок и сравнений.
Рис.2
2.3.Результаты исследования.
Исследование заключается в следующем: берут три массива с одинаковым количеством элементов, но один из них упорядоченный по возрастанию, второй - по убыванию, а третий - случайный. Осуществляется сортировка данных массивов и сравнивается количество перемещений элементов при сортировке первого, второго и третьего массивов, а также сравнивается количество сравнений при сортировке. Вышеописанный способ применяется для массивов, состоящих из 10, 100, 1000 и 10000 упорядоченных и неупорядоченных элементов для всех методов сортировки.
Сортировка на 10 элементов:
| | | Быстрая | Пирамидальная |
| в неупорядоченном списке | перестановки | 11 | 50 |
| сравнения | 16 | 58 | |
| в упорядоченном по возрастанию | перестановки | 6 | 52 |
| сравнения | 19 | 58 | |
| в упорядоченном по убыванию | перестановки | 6 | 52 |
| сравнения | 19 | 58 |
Сортировка на 100 элементов:
| | | Быстрая | Пирамидальная |
| в неупорядоченном списке | перестановки | 194 | 827 |
| сравнения | 359 | 1238 | |
| в упорядоченном по возрастанию | перестановки | 83 | 800 |
| сравнения | 485 | 1286 | |
| в упорядоченном по убыванию | перестановки | 83 | 884 |
| сравнения | 486 | 1288 |
Сортировка на 1000 элементов:
| | | Быстрая | Пирамидальная |
| в неупорядоченном списке | перестановки | 46093 | 148181 |
| сравнения | 57793 | 254112 | |
| в упорядоченном по возрастанию | перестановки | 30560 | 139808 |
| сравнения | 70886 | 236426 | |
| в упорядоченном по убыванию | перестановки | 30560 | 139850 |
| сравнения | 70886 | 236712 |
Контрольный пример:
Дан массив из 25 случайно заполненных элементов. Необходимо отсортировать данный массив, посчитать количество перестановок, сравнений в массиве, отсортированном по возрастанию, убыванию.
Получаем:
Вывод: Результаты исследования показали, что алгоритм быстрой сортировки является более эффективным, т.к. он дает наименьшее количество сравнений и перестановок по сравнению с пирамидальной сортировкой.
ЗАКЛЮЧЕНИЕ
Решая конкретные задачи, необходимо выбирать множество данных, представляющих реальную ситуацию. Затем надлежит выбрать способ представления этой информации. Однако очень важную роль играют и свойства самих данных, операций, которые должны выполняться над ними. Современные средства программирования позволяют оперировать с множествами, массивами, записями, файлами и т.д.
Можно сделать вывод, что не существует одного единственного самого оптимального алгоритма сортировки. Найти оптимальный алгоритм, не привязываясь при его выборе к условию задачи невозможно.
СПИСОК ЛИТЕРАТУРЫ:
1.Бабенко М.А., Левин М.В. Введение в теорию алгоритмов и структур данных. – М.:МЦНМО. 2020
2.Круз Р.Л. Структуры данных и проектирование программ – М.: Бином. Лаборатория знаний. 2014
3.Кнут Д. Искусство программирования для ЭВМ Том 1 Основные алгоритмы (3-е изд.: Уч.пос.-М.:Издательский дом «Вильямс», 2000)
4.Бабенко М.А. Введение в теорию алгоритмов и структур данных. 2016
ПРИЛОЖЕНИЕ
Листинг программы
Main.cpp
#include
#include
#include "Insert.h"
#include "QuickSort.h"
#include "PyramidSort.h"
#include "Sort.h"
using namespace std;
int main(void)
{
int n = 0;
cout << "Vvtdite razmer massiva: ";
cin >> n;
cout << endl;
if(n > 0){
QuickSort* q = new QuickSort(n, new int[n]);
QuickSort* q1 = new QuickSort(n, new int[n]);
PyramidSort* p = new PyramidSort(n, new int[n]);
PyramidSort* p1 = new PyramidSort(n, new int[n]);
q->RandomFill(0,100);
memcpy(p->getArr(), q->getArr(), n*sizeof(int));
memcpy(q1->getArr(), q->getArr(), n*sizeof(int));
memcpy(p1->getArr(), q->getArr(), n*sizeof(int));
cout << q->getName() << ": " << endl << "Ishodnye dannie: ";
q->Print();
q->Run(false);
cout << "Rez sortirovki: ";
q->Print();
cout << "Ne uporyadochennyi Kol-vo perestanovok: " << q->getSwapNum() << endl;
cout << "Ne uporyadochennyi Kol-vo sravneniy: " << q->getCountEquals() << endl;
q->setArr(q->getArr());
q->Run(false);
cout << "Uporyadochennyi Kol-vo perestanovok: " << q->getSwapNum() << endl;
cout << "Uporyadochennyi Kol-vo sravneniy: " << q->getCountEquals() << endl << endl;
cout << q1->getName() << ": " << endl << "Ishodnye dannie: ";
q1->Print();
q1->Run(true);
cout << "Rez sortirovki: ";
q1->Print();
q1->setArr(q1->getArr());
q1->Run(true);
cout << "Uporyadochennyi Kol-vo perestanovok: " << q1->getSwapNum() << endl;
cout << "Uporyadochennyi Kol-vo sravneniy: " << q1->getCountEquals() << endl << endl;
cout << p->getName() << ": " << endl << "Ishodnye dannie: ";
p->Print();
p->Run(true);
cout << "Rez sortirovki: ";
p->Print();
cout << "Ne uporyadochennyi Kol-vo perestanovok: " << p->getSwapNum() << endl;
cout << "Ne uporyadochennyi Kol-vo sravneniy: " << p->getCountEquals() << endl;
p->setArr(p->getArr());
p->Run(true);
cout << "Uporyadochennyi Kol-vo perestanovok: " << p->getSwapNum() << endl;
cout << "Uporyadochennyi Kol-vo sravneniy: " << p->getCountEquals() << endl << endl;
cout << p1->getName() << ": " << endl << "Ishodnye dannie: ";
p1->Print();
p1->Run(false);
cout << "Rez sortirovki: ";
p1->Print();
p1->setArr(p1->getArr());
p1->Run(false);
cout << "Uporyadochennyi Kol-vo perestanovok: " << p1->getSwapNum() << endl;
cout << "Uporyadochennyi Kol-vo sravneniy: " << p1->getCountEquals() << endl << endl;
}
return 0;
}
Sort.h
#pragma once
#include
#include
#include
using namespace std;
class Sort
{
protected:
int n;
int* x;
int swapNum;
int countEquals;
char* algName;
public:
Sort(int, int*);
Sort();
virtual void Run(void);
int* getArr(void);
void setArr(int*);
int getSize(void);
void setSize(int);
int getSwapNum(void);
int getCountEquals(void);
void DisableSwapCount(void);
void CountSwap(void);
void CountEquals(void);
void Print(void);
void Print2(int*, int);
void RandomFill(int, int);
char* getName(void);
void Swap(int, int);
void CopyTo(int*);
{
delete[] this->x;
}
QuickSort.cpp
#include "QuickSort.h"
QuickSort::QuickSort(int n, int* x) : Sort(n, x) {
this->algName = (char*)"Quick Sort [Center]";
}
void QuickSort::Run(bool m)
{
if(m)
this->Launch1(this->x, this->n-1);
else
this->Launch(this->x, this->n-1);
}
void QuickSort::Launch(int* x, int size) {
long i = 0, j = size ; // начальные значения
int temp, p;
p = x[ size>>1 ];
do {
while (x[i] < p){
i++;
this->CountEquals();
}
while (x[j] > p){
j--;
this->CountEquals();
}
if (i <= j) {
temp = x[i]; x[i] = x[j]; x[j] = temp;
this->CountSwap();
i++; j--;
}
} while (i <= j);
if ( j > 0 ) this->Launch(x, j);
if ( size > i ) this->Launch(x+i, size-i);
}
void QuickSort::Launch1(int* x, int size) {
long i = 0, j = size ; // начальные значения
int temp, p;
p = x[ size>>1 ];
do {
while (x[i] > p){
i++;
this->CountEquals();
}
while (x[j] < p){
j--;
this->CountEquals();
}
if (i <= j) {
temp = x[i]; x[i] = x[j]; x[j] = temp;
this->CountSwap();
i++; j--;
}
} while (i <= j);
if ( j > 0 ) this->Launch1(x, j);
if ( size > i ) this->Launch1(x+i, size-i);
}
QuickSort::
};
PyramidSort.cpp
#include "PyramidSort.h"
PyramidSort::PyramidSort(int n, int* x) : Sort(n, x) {
this->algName = (char*)"Pyramid Sort";
}
void PyramidSort::Screening(int k, int end) {
/* Это чтобы при k=0 и n=0 не делалось лишней
перестановки*/
if (0 == end) return;
int tmp;
int childPos;
tmp = this->x[k];
while (k <= end/2) {
childPos = 2*k; // Левый ребенок элемента k
/* выбираем большего ребенка элемента k
из 2-х: либо левый, либо правый
*/
this->CountEquals();
if (childPos < end && this->x[childPos] < this->x[childPos + 1]) {
childPos++;
}
/* Если родитель x[k] больше всех своих детей,
то ничего не делаем, он стоит на правильном месте */
this->CountEquals();
if(tmp >= this->x[childPos]) break;
// иначе - меняем x[k] с наибольшим ребенком
this->x[k] = this->x[childPos];
k = childPos;
this->CountSwap();
}
this->x[k] = tmp; this->CountSwap();
}
void PyramidSort::Screening1(int k, int end) {
/* Это чтобы при k=0 и n=0 не делалось лишней
перестановки*/
if (0 == end) return;
int tmp;
int childPos;
tmp = this->x[k];
while (k <= end/2) {
childPos = 2*k; // Левый ребенок элемента k
/* выбираем большего ребенка элемента k
из 2-х: либо левый, либо правый
*/
this->CountEquals();
if (childPos < end && this->x[childPos] > this->x[childPos + 1]) {
childPos++;
}
/* Если родитель x[k] больше всех своих детей,
то ничего не делаем, он стоит на правильном месте */
this->CountEquals();
if(tmp <= this->x[childPos]) break;
// иначе - меняем x[k] с наибольшим ребенком
this->x[k] = this->x[childPos];
k = childPos;
this->CountSwap();
}
this->x[k] = tmp; this->CountSwap();
}
void PyramidSort::Run(bool m) {
int i;
int tmp;
// Построение пирамиды
for (i = this->n/2; i >= 0; i--) {
if(m)
this->Screening(i, (this->n - 1));
else
this->Screening1(i, (this->n - 1));
}
/* Формирование конечной отсортированной
последовательности + "балансирование"
пирамиды */
for (i = this->n - 1; i > 0; i--) {
// меняем первый с последним
this->Swap(0, i);
/* Восстановление баланса
для пирамиды x[0..i-1] */
if(m)
this->Screening(0, i-1);
else
this->Screening1(0, i-1);
}
}
PyramidSort::
};
Insert.cpp
#include "Insert.h"
Insert::Insert(int n, int* x) : Sort(n, x)
{
this->algName = (char*)"Insert Sort";
}
Insert::Insert()
{
this->algName = (char*)"Insert Sort";
}
void Insert::Run() {
int t;
int i, j;
for (i = 1; i < this->n; i++) {
t = this->x[i];
for (j = i; j > 0 && this->x[j-1] > t; j--) {
this->x[j] = this->x[j-1];
this->CountSwap();
}
this->x[j] = t;
}
}
Insert::