Главная
>>
Каталог задач
>>
Сортировка
>>
Сравнение алгоритмов сортировки массива
Aвтор:
this
Дата:
21.03.2003
Просмотров: 185785
реализации(C++: 17шт...)
+добавить
Зададимся целью исследовать как же поведут себя в реальных задачах сортировки элементарных массивов такие алгоритмы, как: быстрая, пирамидальная, пузырьковая, выбором, вставками, Шелла, Шейкер-сортировка.
Оценивать будем время выполнения, и количество перестановок элементов.
На вход каждой сортировки будем подавать целочисленные массивы с разным количеством элементов: от 10 до 20000.
В 2-х режимах:
- Массивы со случайно сгенерированными числами
- Частично упорядоченные массивы
Помимо этого логично будет проводить 2 вида сравнения:
- На массивах малой размерности(10 - 300 элементов)
- Больших размерностей: 1000 - 20000 элементов
Время будем рассчитывать с точностью до микросекунды. При сравнении на малых размерностях в целях повышения точности время будет отображаться в долях миллисекунды, при больших же размерностях - в долях секунды.
Рассмотрим далее все эти комбинации, погнали!
Малые размерности случайных массивов
Как видим по скорости лидирует быстрая сортировка. Самые медленные - это пузырьковая и Шейкера.
По количеству перестановок - меньше всего их делает как это ни странно сортировка выбором, затем конечно же быстрая сортировка. Больше всего перестановок делают опять же пузырьковая, Шейкера и Выбором.
Т.о. можно констатировать тот факт, что такие похожие по принципу сортировки алгоритмы как Выбором и Вставками, показывающие почти что одинаковую скорость, радикально отличаются по количеству перестановок: первая(выбором) - делает их меньше чем любой из представленных алгоритмов, вторая(вставками) - наоборот, больше всего.
Малые размерности частично отсортированных массивов
По сравнению с полностью случайными массивами в случае частичной отсортированности на малых размерностях констатируем следующие факты:
- Сортировка вставками начинает опережать сортировку выбором
- Сортировка Шелла начинает опережать пирамидальную и по производительности и по количеству перестановок
- Пузырьковая сортировка делает меньше перестановок чем Вставками и Шейкер
Большие размерности случайных массивов
Не видно Быструю, Пирамидальную и сортировку Шелла, поэтому:
По сравнению со случайными массивами на малых размерностях в случае больших размерностей констатируем следующие факты:
- Шейкер сортировка гарантированно опережает пузырьковую по производительности
- Пирамидальная сортировка примерно после 10 000 -ой размерности начинает опережать Шелла по производительности
- Быстрая сортировка по прежнему остается самой быстрой по производительности и с ростом N только увеличивает это превосходство.
По сравнению с количеством перестановок на малых размерностях - значительных изменений не наблюдается.
Большие размерности частично отсортированных массивов
Смотрим что происходит с Пирамидальной, Быстрой и Шелла:
По сравнению с частичной отсортированностью на малых размерностях делаем следующие выводы:
- Шейкер сортировка гарантированно начинает опережать пузырьковую
- Сортировка выбором перестает лидировать над вставками, они начинают показывать примерно одинаковую производительность
- Пирамидальная сортировка теперь уже опережает Шелла на всех значениях
В отличие от перестановок на малых размерностях - здесь пирамидальная сортировка обходит Шелла, делая swap-ов значительно меньше. Лидирует как обычно - сортировка выбором.
Выводы
Быстрая сортировка лидирует по производительности во всех тестах. По количеству перестановок она уступает лишь сортировке Выбором.
Сортировка выбором по производительности в общем случае мало отличается от Вставками, но вот по количеству перестановок - лидирует во всех тестах.
Пирамидальная сортировка и сортировка Шелла: на размерностях ~ больше 10000 пирамидальная быстрей во всех случаях. И лишь на меньших размерностях + в случае случайных значений - сортировка Шелла превосходит пирамидальную.
Шейкер и пузырьковая: первая конечно быстрей, но по количеству перестановок при частичной отсортированности - пузырьковая выигрывает, т.е. делает их меньше.
Реализации:
C++(17)
+добавить
1)
Анализ сортировок: быстрой, пирамидальной, Шелла, Выбором, Вставками, Шейкера, пузырьковой на C++, code #30[автор:this]
#include "Insert.h";
#include "Select.h";
#include "ShellSortSedj1.h";
#include "QuickSort.h";
#include "BubbleSort.h";
#include "ShakerSort.h";
#include "PyramidSort.h";
#include "Timer.h";
#include "RandomGenerator.h";
int main()
{
srand( (unsigned)time(NULL));
// Начальный массив, нужен лишь для инициализации
int* _x;
// Количество размерностей массивов
const int sizeNum = 13;
int sizes[sizeNum] =
{10, 50, 100, 400, 800, 1000, 4000, 8000, 10000, 12000, 15000, 18000, 20000};
// Количество видов сортировок
const int sortTypeNum = 7;
// Инициируем требуемые виды сортировок
QuickSort quickSortObj(0, _x);
PyramidSort pyramidSortObj(0, _x);
ShellSortSedj1 shellSortSedj1Obj(10000, _x, 100);
ShakerSort shakerSortObj(0, _x);
Insert insertObj(0, _x);
Select selectObj(0, _x);
BubbleSort bubbleSortObj(0, _x);
// Им будем подсчитывать время
Timer timerObj(sortTypeNum);
Sort* sorts[sortTypeNum];
sorts[0] =& quickSortObj;
sorts[1] =& pyramidSortObj;
sorts[2] =& shellSortSedj1Obj;
sorts[3] =& shakerSortObj;
sorts[4] =& insertObj;
sorts[5] =& selectObj;
sorts[6] =& bubbleSortObj;
// Цикл по 2 режимам состава массивов:
// случайные / частично-отсортированные числа
for (int k = 0; k < 2; k++) {
if (0 == k
) cout <<
"I. Random Numbers";
else cout <<
"II. PARTLY Random Numbers";
// Цикл по размерам массива
for (int i = 0; i < sizeNum; i++) {
cout <<
" " << i +
1 <<
") Array Size(N): " << sizes
[i
] <<
"\n";
// ... по видам сортировок
for (int j = 0; j < sortTypeNum; j++) {
int N = sizes[i];
int* x = new int[N];
RandomGenerator genObj(N);
// В зависимости от режима - заполняем исходный массив
if (0 == k) x = genObj.GetRandom(0, 100);
else x = genObj.GetPartSorted(N/10, N/5);
// Уточняем размер и передаем исходный сформированный массив
sorts[j]->setSize(N);
sorts[j]->setArr(x);
// Засекаем время
timerObj.Start(0);
sorts[j]->Run(); // Прогоняем сортировку текущего вида
float exTime = timerObj.Get(0, 1); // Фиксируем время
// Выводим время выполнения и количество перестановок
cout.
setf(ios::
fixed | ios::
showpoint);
cout <<
" " << exTime <<
" sec.:: ";
cout << sorts
[j
]->getSwapNum
() <<
" swaps :: " << sorts
[j
]->getName
() <<
"\n";
delete [] x;
}
}
}
return 0;
}
2)
Sort.h на C++, code #35[автор:this]
#pragma once
#include <iostream>
#include <iomanip>
#include <time.h>
using namespace std;
class Sort
{
protected:
int n;
int* x;
int swapNum;
int memEval;
bool countSwaps;
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);
void DisableSwapCount(void);
void CountSwap(void);
void Print(void);
void Print2(int*, int);
void RandomFill(int, int);
char* getName(void);
void Swap(int, int);
void CopyTo(int*);
public:
~Sort(void);
};
3)
Sort.cpp на C++, code #36[автор:this]
#include "Sort.h"
Sort::Sort()
{
this->setSize(0);
this->swapNum = 0;
this->memEval = 0;
}
Sort::Sort(int n, int* x)
{
this->setArr(x);
this->setSize(n);
this->swapNum = 0;
this->memEval = 0;
this->countSwaps = true;
this->algName = "Default Sort";
}
void Sort::Run(void) {
}
int* Sort::getArr(void) {
return this->x;
}
void Sort::setArr(int* x) {
this->swapNum = 0;
this->x = x;
}
int Sort::getSize(void) {
return this->n;
}
void Sort::setSize(int n) {
this->n = n;
}
char* Sort::getName(void) {
return this->algName;
}
int Sort::getSwapNum(void) {
return this->swapNum;
}
void Sort::DisableSwapCount() {
this->countSwaps = false;
}
void Sort::CountSwap() {
if (this->countSwaps) {
this->swapNum++;
}
}
void Sort::Print(void) {
for (int i = 0; i < this->n; i++) {
cout << this->x
[i
] <<
' ';
}
}
void Sort::RandomFill(int left = 0, int right = 100) {
srand( (unsigned)time(NULL));
for (int i = 0; i < this->n; i++) {
this->x[i] = left + rand() % (right - left);
}
}
void Sort::Swap(int i, int j) {
int tmp;
tmp = this->x[i]; this->x[i] = this->x[j]; this->x[j] = tmp;
this->CountSwap();
}
void Sort::CopyTo(int* dest) {
for (int i = 0; i < this->n; i++) {
dest[i] = this->x[i];
}
}
void Sort::Print2(int* arr, int n) {
for (int i = 0; i < n; i++) {
}
}
Sort::~Sort(void)
{
delete [] x;
}
4)
QuickSort.h на C++, code #31[автор:this]
#pragma once
#include "sort.h"
#include "Insert.h"
class QuickSort :
public Sort
{
protected:
// Сортировка вставкой, будет им использоваться
// на конечном этапе
Insert simpleSortObj;
public:
QuickSort(int, int*);
void Run(void);
void Launch(int*, int);
public:
~QuickSort(void);
};
5)
QuickSort.cpp на C++, code #32[автор:this]
#include "QuickSort.h"
QuickSort::QuickSort(int n, int* x) : Sort(n, x) {
this->algName = "Quick Sort [Center]";
}
void QuickSort::Run(void)
{
this->Launch(this->x, this->n);
}
void QuickSort::Launch(int* x, int size) {
long i = 0, j = size - 1; // начальные значения
int temp, p;
p = x[ size>>1 ]; // выбираем середину
// процедура разделения
do {
while (x[i] < p) i++;
while (x[j] > p) j--;
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);
}
QuickSort::~QuickSort(void)
{
}
6)
PyramidSort.h на C++, code #33[автор:this]
#pragma once
#include "sort.h"
class PyramidSort :
public Sort
{
public:
PyramidSort(int, int*);
void Run(void);
void Screening(int, int);
public:
~PyramidSort(void);
};
7)
PyramidSort.cpp на C++, code #34[автор:this]
#include "PyramidSort.h"
PyramidSort::PyramidSort(int n, int* x) : Sort(n, x) {
this->algName = "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-х: либо левый, либо правый
*/
if (childPos < end && this->x[childPos] < this->x[childPos + 1]) {
childPos++;
}
/* Если родитель x[k] больше всех своих детей,
то ничего не делаем, он стоит на правильном месте */
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(void) {
int i;
int tmp;
// Построение пирамиды
for (i = this->n/2; i >= 0; i--) {
this->Screening(i, (this->n - 1));
}
/* Формирование конечной отсортированной
последовательности + "балансирование"
пирамиды */
for (i = this->n - 1; i > 0; i--) {
// меняем первый с последним
this->Swap(0, i);
/* Восстановление баланса
для пирамиды x[0..i-1] */
this->Screening(0, i-1);
}
}
PyramidSort::~PyramidSort(void)
{
}
8)
ShellSortSedj1.h на C++, code #37[автор:this]
#pragma once
#include "shellsort.h"
class ShellSortSedj1 :
public ShellSort
{
protected:
int* dseq;
int di;
public:
ShellSortSedj1(int, int*, int = 10, bool = true);
int GetIncrements(void);
void Run(void);
int GetInc(int);
public:
~ShellSortSedj1(void);
};
9)
ShellSortSedj1.cpp на C++, code #38[автор:this]
10)
ShakerSort.h на C++, code #39[автор:this]
11)
ShakerSort.cpp на C++, code #40[автор:this]
12)
Insert.h на C++, code #41[автор:this]
13)
Insert.cpp на C++, code #42[автор:this]
14)
Select.h на C++, code #43[автор:this]
15)
Select.cpp на C++, code #44[автор:this]
16)
BubbleSort.h на C++, code #45[автор:this]
17)
BubbleSort.cpp на C++, code #46[автор:this]