Pawn.Sort

Автор: 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

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

Цитата:

---

Сообщение от Tornamic

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

• 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 нет необходимости использовать алгоритмы сортировок отличные от сортировки выбором.

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

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

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

Цитата:

---

Сообщение от 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);

---

Это не будет давать верные результаты скорости. 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);
}