's Алгоритмы сортировки

Из всего этого списка выбрал 3 самых быстрых алгоритма:

Сортировка выбором(почитать):

PHP код:

---

SelectionSort(_array[], size = sizeof _array){
    for(new i = 0, value = 0, j = 0, swap = 0; i != size - 1; i++){
        value = i;
        for(j = i + 1; j != size; j++){
            if(_array[ j ] > _array[ value ])//max to min
                value = j;
        }
        if(value != i){
            swap = _array[ i ];
            _array[ i ] = _array[ value ];
            _array[ value ] = swap;
        }
    }
} 


---

Сортировка пузырьком(почитать):

PHP код:

---

BubbleSort(_array[], size = sizeof _array){
    for(new i = 0, j = 0, swap = 0; i != size; i++) {
        for( j = 0 ; j < i ; j++ ) {
            if(_array[i] > _array[j]){//max to min
                swap = _array[i];
                _array[i] = _array[j];
                _array[j] = swap;
            }
        }
    }
} 


---

Гномья сортировка(почитать):

PHP код:

---

GnomeSort(_array[], size = sizeof _array){
    for( new j = 1, swap; j != size;  ){
        if(_array[ j - 1 ] >= _array[ j ]) ++ j;//max to min
        else{
            swap = _array[ j ];
            _array[ j ] = _array[ j - 1 ];
            _array[ j - 1 ] = swap ;
            -- j;
            
            if( j == 0)
                j = 1;
        }
    }
} 


---

10000 чисел пересортировало с таким результатом:

PHP код:

---

[08:35:42] gnome: 380ms
[08:35:42] bubble: 294ms
[08:35:43] selection: 155ms 


---

На маленьких дистанциях они равны:

PHP код:

---

[08:36:24] gnome: 0ms
[08:36:24] bubble: 0ms
[08:36:24] selection: 0ms 


---

Ссылки на материалы указаны.

ммм.
Спасибо.

вот это, то что надо, часто нужны подобные алгоритмы

Может вопрос тупой, но для чего это все можно использовать?

Цитата:

---

Сообщение от A N D R E Y

Может вопрос тупой, но для чего это все можно использовать?

---

Топ система например

Отлично, но не плохо бы было показать использование цикла.

Цитата:

---

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

Отлично, но не плохо бы было показать использование цикла.

---

PHP код:

---

new values[ 12 ] = { 1,5,7,3,3,6,5,25,46,357,64,2 };
gnomeSort( values ); 


---

Удобная вещь, можно использовать во многих этапах разработки, хоть даже, отсортировать массив победителей какой либо игры, но не важно, каждый сам решает.
Поправочка:

Цитата:

---

На маленьких дистанциях они равны:

PHP код:

---

[08:36:24] gnome: 0ms
[08:36:24] bubble: 0ms
[08:36:24] selection: 0ms 


---

---

Они не равны, просто результат/время находится в дробной части, которой не видно т.к. значение целое.

Глупый вопрос, но зачем _ перед переменной?

Цитата:

---

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

Глупый вопрос, но зачем _ перед переменной?

---

Типо так удобней читать))

Цитата:

---

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

Глупый вопрос, но зачем _ перед переменной?

---

Обычно так обозначают приватную переменную в классе. В Pawn так можно обозначать глобальные static переменные в различных библиотеках. А причина использования здесь не ясна.

Цитата:

---

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

Глупый вопрос, но зачем _ перед переменной?

---

Скорее всего, расчёт на быдлокодеров, которые могут назвать глобальную переменную "array" (чем это чревато см. здесь, пункт 1).
По сути это ни что иное как поощрение плохих практик программирования, поэтому я бы не советовал так называть аргументы функции и локальные переменные. Проблемы нужно решать, а не избегать.

Лично я предпочитаю CombSort :smile:

PHP код:

---

stock CombSort(array[], array_size = sizeof(array))
{
    new gap = array_size;
    new swapper;
    new bool: swap_status = true; 
    while(gap != 1 || swap_status)
    {
        gap = (gap*10)/13;
        if(!gap)
        {
            gap = 1;
        }
        swap_status = false;
        for(new i = 0; i < array_size-gap; i++)
        {
            if(array[i] > array[i+gap])
            {
                swapper = array[i];
                array[i] = array[i+gap];
                array[i+gap] = swapper;
                swap_status = true;
            }
        }
    }
    return 1;
} 


---

10000 чисел пересортировало с таким результатом:

PHP код:

---

CombSort: 119 ms 


---

Цитата:

---

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

Лично я предпочитаю CombSort :smile:

  Открыть/закрыть

PHP код:

---

stock CombSort(array[], array_size = sizeof(array))
{
    new gap = array_size;
    new swapper;
    new bool: swap_status = true; 
    while(gap != 1 || swap_status)
    {
        gap = (gap*10)/13;
        if(!gap)
        {
            gap = 1;
        }
        swap_status = false;
        for(new i = 0; i < array_size-gap; i++)
        {
            if(array[i] > array[i+gap])
            {
                swapper = array[i];
                array[i] = array[i+gap];
                array[i+gap] = swapper;
                swap_status = true;
            }
        }
    }
    return 1;
} 


---

10000 чисел пересортировало с таким результатом:

PHP код:

---

CombSort: 119 ms 


---

---

Принимай во внимание то, что характеристики компьютеров с автором темы у вас разные, соответственно тест скорости отдельно этой функции объективно сравнить с теми, что в шапке темы, нельзя)

Цитата:

---

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

Скорее всего, расчёт на быдлокодеров, которые могут назвать глобальную переменную "array" (чем это чревато см. здесь, пункт 1).

---

Первый пункт в той теме как-то заморочен. Переменные не обязательно называть именно длинными именами, достаточно просто уникальными

Цитата:

---

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

Первый пункт в той теме как-то заморочен. Переменные не обязательно называть именно длинными именами, достаточно просто уникальными

---

Уникальность переменных с короткими именами ограничена размерами английского алфавита. Под короткими именами, как можно заметить в примере, подразумеваются переменные, состоящие из одной-двух букв.

Цитата:

---

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

Принимай во внимание то, что характеристики компьютеров с автором темы у вас разные, соответственно тест скорости отдельно этой функции объективно сравнить с теми, что в шапке темы, нельзя)

---

А где ты увидел сравнение или я написал что при сравнение получился такой результат? Я просто оставил свои результаты теста, даже не стал тестировать функции от автора. Если бы сравнивал, то обязательно бы указал все результаты теста включая функции автора!

  Открыть/закрыть

PHP код:

---

#include <a_samp>

SelectionSort(_array[], size = sizeof _array){
    for(new i = 0, value = 0, j = 0, swap = 0; i != size - 1; i++){
        value = i;
        for(j = i + 1; j != size; j++){
            if(_array[ j ] > _array[ value ])//max to min
                value = j;
        }
        if(value != i){
            swap = _array[ i ];
            _array[ i ] = _array[ value ];
            _array[ value ] = swap;
        }
    }
}

BubbleSort(_array[], size = sizeof _array){
    for(new i = 0, j = 0, swap = 0; i != size; i++) {
        for( j = 0 ; j < i ; j++ ) {
            if(_array[i] > _array[j]){//max to min
                swap = _array[i];
                _array[i] = _array[j];
                _array[j] = swap;
            }
        }
    }
}

GnomeSort(_array[], size = sizeof _array){
    for( new j = 1, swap; j != size;  ){
        if(_array[ j - 1 ] >= _array[ j ]) ++ j;//max to min
        else{
            swap = _array[ j ];
            _array[ j ] = _array[ j - 1 ];
            _array[ j - 1 ] = swap ;
            -- j;

            if( j == 0)
                j = 1;
        }
    }
}

stock CombSort(array[], array_size = sizeof(array))
{
    new gap = array_size;
    new swapper;
    new bool: swap_status = true;
    while(gap != 1 || swap_status)
    {
        gap = (gap*10)/13;
        if(!gap)
        {
            gap = 1;
        }
        swap_status = false;
        for(new i = 0; i < array_size-gap; i++)
        {
            if(array[i] < array[i+gap])
            {
                swapper = array[i];
                array[i] = array[i+gap];
                array[i+gap] = swapper;
                swap_status = true;
            }
        }
    }
    return 1;
}

stock CombSortOpt(array[], array_size = sizeof(array))
{
    static gap, swap_status, i, j, end, val1, val2, addr1;
    gap = array_size;
    swap_status = true;
    while (gap != 1 || swap_status)
    {
        if((gap = (gap * 10) / 13) == 0)
            gap = 1;
        swap_status = false;
        i = 0, j = gap - 1, end = array_size - gap;
        while (i < end)
        {
            if(array[i] < array[++j])
            {
                #emit    load.s.alt    array
                #emit    load.pri    i
                #emit    idxaddr
                #emit    move.alt
                #emit    load.i
                #emit    stor.pri    val1
                #emit    stor.alt    addr1
                #emit    load.pri    gap
                #emit    idxaddr
                #emit    move.alt
                #emit    load.i
                #emit    stor.pri    val2
                #emit    load.pri    val1
                #emit    stor.i
                #emit    load.alt    addr1
                #emit    load.pri    val2
                #emit    stor.i
                swap_status = true;
            }
            ++i;
        }
    }
    return 1;
}

main()
{
    static src_array[10000];
    static numbers[sizeof(src_array)];
    static t;
    for (new i = 0; i < sizeof(src_array); ++i)
        src_array[i] = random(0);
    //
    numbers = src_array;
    t = GetTickCount();
    SelectionSort(numbers);
    t = GetTickCount() - t;
    printf("SelectionSort: %d", t);
    for (new i = 0; i < sizeof(numbers) - 1; ++i)
        if (numbers[i] < numbers[i + 1])
            { printf("SelectionSort: error at position %d", i); break; }
    //
    numbers = src_array;
    t = GetTickCount();
    BubbleSort(numbers);
    t = GetTickCount() - t;
    printf("BubbleSort: %d", t);
    for (new i = 0; i < sizeof(numbers) - 1; ++i)
        if (numbers[i] < numbers[i + 1])
            { printf("BubbleSort: error at position %d", i); break; }
    //
    numbers = src_array;
    t = GetTickCount();
    GnomeSort(numbers);
    t = GetTickCount() - t;
    printf("GnomeSort: %d", t);
    for (new i = 0; i < sizeof(numbers) - 1; ++i)
        if (numbers[i] < numbers[i + 1])
            { printf("GnomeSort: error at position %d", i); break; }
    //
    numbers = src_array;
    t = GetTickCount();
    CombSort(numbers);
    t = GetTickCount() - t;
    printf("CombSort: %d", t);
    for (new i = 0; i < sizeof(numbers) - 1; ++i)
        if (numbers[i] < numbers[i + 1])
            { printf("CombSort: error at position %d", i); break; }

    numbers = src_array;
    t = GetTickCount();
    CombSortOpt(numbers);
    t = GetTickCount() - t;
    printf("CombSortOpt: %d", t);
    for (new i = 0; i < sizeof(numbers) - 1; ++i)
        if (numbers[i] < numbers[i + 1])
            { printf("CombSortOpt: error at position %d", i); break; }
} 


---

Код:

---

SelectionSort: 2521
BubbleSort: 5826
GnomeSort: 6813
CombSort: 55
CombSortOpt: 22

---

Изменил порядок сортировки в CombSort на убывающий, как в 1-м посте, и дополнил своим вариантом CombSortOpt, адаптированным под особенности Pawn.
Хоть я и добавил проверку отсортированных данных, всё равно такое ощущение, будто что-то сделал не так - уж слишком подозрительна разница в результатах.

Наверное, стоит дополнить тему статьей с habrahabr

И коль гоняетесь за скоростью в Pawn, то почему ещё никто не выложил RadixSort на pro-pawn?

Я бы реализовал, но у меня не так много времени.

Цитата:

---

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

Уникальность переменных с короткими именами ограничена размерами английского алфавита. Под короткими именами, как можно заметить в примере, подразумеваются переменные, состоящие из одной-двух букв.

---

Ну так короткие это не обязательно однобуквенные, если по тексту.
Если просто стараться сделать длиннее, то шанс совпадения возрастёт у таких же любителей писать названия длиннее, поэтому важнее присваивать имя, ориентируясь на ситуации в коде, где эта переменная будет использоваться... или просто что-то редко встречающееся.

Вообще шанс совпадений будет всегда, просто главная мысль как обычно не допускать такой банальщины, как называние переменных слишком абстрактными именами, а-ля "data, str, x". А слишком длинные названия очень часто просто неудобно читать, особенно если они часто вызываются.

Цитата:

---

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

А где ты увидел сравнение или я написал что при сравнение получился такой результат? Я просто оставил свои результаты теста, даже не стал тестировать функции от автора. Если бы сравнивал, то обязательно бы указал все результаты теста включая функции автора!

---

Нигде? Я написал про то, что в тестах просто не было необходимости в принципе, ибо они не комплексные

Цитата:

---

Сообщение от $continue$

И коль гоняетесь за скоростью в Pawn, то почему ещё никто не выложил RadixSort на pro-pawn?

---

Год назад я переводил почти все типы сортировок, да RadixSort был быстрее остальных (из тех, которых я перевел), но если память не изменяет там используется рекурсия для сортировки.

Цитата:

---

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

Глупый вопрос, но зачем _ перед переменной?

---

Цитата:

---

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

Обычно так обозначают приватную переменную в классе. В Pawn так можно обозначать глобальные static переменные в различных библиотеках. А причина использования здесь не ясна.

---

Цитата:

---

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

Скорее всего, расчёт на быдлокодеров, которые могут назвать глобальную переменную "array" (чем это чревато см. здесь, пункт 1).
По сути это ни что иное как поощрение плохих практик программирования, поэтому я бы не советовал так называть аргументы функции и локальные переменные. Проблемы нужно решать, а не избегать.

---

На вид явный идиотизм автора данной темы и вообще быдлокодинг тот еще.

И результаты тестов, которые приложил DC:
Без -d3

PHP код:

---

[00:30:53] SelectionSort: 5115
[00:31:03] BubbleSort: 10872
[00:31:18] GnomeSort: 15015
[00:31:19] CombSort: 86
[00:31:19] CombSortOpt: 66 


---

С -d3

PHP код:

---

[00:31:54] SelectionSort: 9157
[00:32:13] BubbleSort: 18253
[00:32:37] GnomeSort: 24045
[00:32:37] CombSort: 127
[00:32:37] CombSortOpt: 92 


---

Цитата:

---

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

Без -d3

PHP код:

---

[00:30:53] SelectionSort: 5115
[00:31:03] BubbleSort: 10872
[00:31:18] GnomeSort: 15015
[00:31:19] CombSort: 86
[00:31:19] CombSortOpt: 66 


---

С -d3

PHP код:

---

[00:31:54] SelectionSort: 9157
[00:32:13] BubbleSort: 18253
[00:32:37] GnomeSort: 24045
[00:32:37] CombSort: 127
[00:32:37] CombSortOpt: 92 


---

---

Флаг -d3 подразумевает под собой отсутствие оптимизации байткода (-O0). ИМХО, для тестов разумно компилировать с оптимизацией 1-го уровня (-O1), т.к. на 2-м используются макроинструкции, которые поддерживаются только в Pawn 3.2 (в SA-MP компилятор от 3.2, хотя в сервере встроен интерпретатор версии 3.0).

Цитата:

---

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

Флаг -d3 подразумевает под собой отсутствие оптимизации байткода (-O0). ИМХО, для тестов разумно компилировать с оптимизацией 1-го уровня (-O1), т.к. на 2-м используются макроинструкции, которые поддерживаются только в Pawn 3.2 (в SA-MP компилятор от 3.2, хотя в сервере встроен интерпретатор версии 3.0).

---

Многие держат сервера, мод которых скомпилирован с флагом -d3, поэтому я добавил результаты тестов именно с ним.

В нормальной реализации RadixSort - рекурсия не нужна.

Цитата:

---

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

Год назад я переводил почти все типы сортировок, да RadixSort был быстрее остальных (из тех, которых я перевел), но если память не изменяет там используется рекурсия для сортировки.

---

Цитата:

---

Сообщение от $continue$

В нормальной реализации RadixSort - рекурсия не нужна.

---

Да, собственно, от любой рекурсии можно избавиться, только код немного усложнится.