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

[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);}