Pawn.Sort

[Tornamic]

Автор: Tornamic (я)
Текущая версия: 2

Описание:

Алгоритмы сортировки для Pawn


Список алгоритмов:

Сортировка пузырьком (Bubble sort)
Сортировка выбором (Selection sort)
Сортировка вставками (Insertion sort)
Гномья сортировка (Gnome sort)
Шейкерная сортировка (Shaker/Cocktail sort)
Сортировка чет-нечет (Odd-even Sort)
Быстрая сортировка (Quick sort)
Пирамидальная сортировка (Heap sort)
Сортировка шелла (Shell sort)
Случайная сортировка (Bogo sort)


Скорость алгоритмов (меньше - лучше):

Quick sort: 4
Shell sort: 5
Heap sort: 9
Insertion sort: 12
Selection sort: 14
Shaker sort: 25
Gnome sort: 27
OddEven sort: 28
Bubble sort: 44
Bogo sort: Infinity


Установка:

#include <Pawn.Sort>


Пример:

main()
{
new array[100];
Array::FillRandomValues(array);
print("Bubble sort:");
Sort::Bubble(array);
Array::Print(array);
}



Copyright © 2023 Tornamic. All rights reserved.

Author: Tornamic (Kirill Tymoshchenko)
Discord: https://pastebin.com/raw/LMBNfFHE
Github: https://github.com/Tornamic
pawn.wiki https://pawn.wiki/i.php?/user/54232-tornamic/


# Quadratic Sort Functions
Sort::Bubble(array[], const len = sizeof array) https://en.wikipedia.org/wiki/Bubble_sort
Sort::Selection(array[], const len = sizeof array) https://en.wikipedia.org/wiki/Selection_sort
Sort::Insertion(array[], const len = sizeof array) https://en.wikipedia.org/wiki/Insertion_sort
Sort::Gnome(array[], const len = sizeof array) https://en.wikipedia.org/wiki/Gnome_sort
Sort::Shaker(array[], len = sizeof array) https://en.wikipedia.org/wiki/Cocktail_shaker_sort
Sort::OddEven(array[], const len = sizeof array) https://en.wikipedia.org/wiki/Odd%E2%80%93even_sort

# Logarithmic Sort Functions
Sort::Quick(array[], left, right) https://en.wikipedia.org/wiki/Quicksort
Sort::Heap(array[], const len = sizeof array) https://en.wikipedia.org/wiki/Heapsort
Sort::Shell(array[], const len = sizeof array) https://en.wikipedia.org/wiki/Shellsort

# Weird Sort Functions
Sort::Bogo(array[], const len = sizeof array) https://en.wikipedia.org/wiki/Bogosort

# Misc Functions
Var::Swap(&value1, &value2)
Array::FillRandomValues(array[], const len = sizeof array, randmin = -10000, randmax = 10000)
Array::Print(array[], const len = sizeof array)
Array::Shuffle(array[], const len = sizeof array)
Array::IsSorted(const array[], const len = sizeof array)


Скачать:

Github (https://github.com/Tornamic/Pawn.Sort)

[punkochel]

Молодец, хорошая работа, структурированного инклуда по данной теме не встречал.
Желательно изменить название функции Shuffle, ибо она не перемешивает массив, а заполняет его. Правильно было бы назвать эту функцию вроде FillRandomValues, или что-то в этом роде, а название Shuffle использовать для функции, которая бы перемешивала значения которые уже находятся в массиве (это будет весьма полезно для создания карточных игр: дурак / покер).



Скорость алгоритмов (меньше - лучше):

Quick sort: 4
Shell sort: 5
Heap sort: 9
Insertion sort: 12
Selection sort: 14
Shaker sort: 25
Gnome sort: 27
OddEven sort: 28
Bubble sort: 44


Тут стоит указать как проводилось тестирование и откуда такие значения взялись.

Имхо... в Pawn нет необходимости использовать алгоритмы сортировок отличные от сортировки выбором.

[Tornamic]

К совету с перемешиванием прислушаюсь.
Вот код проверки, самый простой, который только есть


new array[100];
new time1 = gettime();
print("Bubble sort:");
for(new i = 0; i < 100000; i++)
{
Array::Shuffle(array);
Sort::Bubble(array);
}
printf("%i", gettime() - time1);

[Tornamic]

Обновил до версии 2

[punkochel]

К совету с перемешиванием прислушаюсь.
Вот код проверки, самый простой, который только есть


new array[100];
new time1 = gettime();
print("Bubble sort:");
for(new i = 0; i < 100000; i++)
{
Array::Shuffle(array);
Sort::Bubble(array);
}
printf("%i", gettime() - time1);


Это не будет давать верные результаты скорости. Array::Shuffle(array) тут заполняет массив рандомными значениями, как я понимаю, и каждый раз эти значения будут отличаться, и каждый раз из-за этого время на сортировку будет разное.
Я тут набросал пример профайлера, если будет время постарайся провести тесты:
#define ARRAY_SIZE 1000

new array[ARRAY_SIZE];
new bool:flag_fill_array;

stock TestSortSpeed(index)
{
if(!flag_fill_array) {
Array::FillRandomValues(array);
flag_fill_array = true;
}
new time_count,
sort_name[32+1],
temp_arr[ARRAY_SIZE];
temp_arr = array;

time_count = GetTickCount();
switch(index) {
case 0: {
sort_name = "Bubble";
Array::Bubble(temp_arr);
}
case 1: {
sort_name = "Selection";
Array::Selection(temp_arr);
}
/*
etc, for each method
*/
}
printf("Sort method: '%s' / Time: %d ms", sort_name, GetTickCount() - time_count);
}