Просмотр полной версии : [Function] 's Алгоритмы сортировки
Seregamil
09.02.2014, 06:44
Из всего этого списка выбрал 3 самых быстрых алгоритма (http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D1.8B_.D1.83.D1.81.D1.82.D0.BE.D0.B9.D1.87.D0.B8.D0.B2.D0.BE.D0.B9_.D1.81.D0.BE.D1.80.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.BA.D0.B8):
Сортировка выбором(почитать) (http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC):
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;
}
}
}
Сортировка пузырьком(почитать) (http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BF%D1%83%D0%B7%D1%8B%D1%80%D1%8C%D0%BA%D0%BE%D0%BC):
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;
}
}
}
}
Гномья сортировка(почитать) (http://ru.wikipedia.org/wiki/%D0%93%D0%BD%D0%BE%D0%BC%D1%8C%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0):
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 чисел пересортировало с таким результатом:
[08:35:42] gnome: 380ms
[08:35:42] bubble: 294ms
[08:35:43] selection: 155ms
На маленьких дистанциях они равны:
[08:36:24] gnome: 0ms
[08:36:24] bubble: 0ms
[08:36:24] selection: 0ms
Ссылки на материалы указаны.
Salvacore
09.02.2014, 08:51
ммм.
Спасибо.
V[a]mPiR
02.03.2014, 15:57
вот это, то что надо, часто нужны подобные алгоритмы
A N D R E Y
06.03.2014, 17:45
Может вопрос тупой, но для чего это все можно использовать?
Seregamil
06.03.2014, 19:45
Может вопрос тупой, но для чего это все можно использовать?
Топ система например
$continue$
16.11.2014, 14:45
Отлично, но не плохо бы было показать использование цикла.
Seregamil
16.11.2014, 16:28
Отлично, но не плохо бы было показать использование цикла.
new values[ 12 ] = { 1,5,7,3,3,6,5,25,46,357,64,2 };
gnomeSort( values );
NewGreen
16.01.2015, 14:12
Удобная вещь, можно использовать во многих этапах разработки, хоть даже, отсортировать массив победителей какой либо игры, но не важно, каждый сам решает.
Поправочка:
На маленьких дистанциях они равны:
[08:36:24] gnome: 0ms
[08:36:24] bubble: 0ms
[08:36:24] selection: 0ms
Они не равны, просто результат/время находится в дробной части, которой не видно т.к. значение целое.
Глупый вопрос, но зачем _ перед переменной?
vovandolg
16.01.2017, 08:53
Глупый вопрос, но зачем _ перед переменной?
Типо так удобней читать))
Глупый вопрос, но зачем _ перед переменной?
Обычно так обозначают приватную переменную в классе. В Pawn так можно обозначать глобальные static переменные в различных библиотеках. А причина использования здесь не ясна.
Daniel_Cortez
16.01.2017, 11:44
Глупый вопрос, но зачем _ перед переменной?
Скорее всего, расчёт на быдлокодеров, которые могут назвать глобальную переменную "array" (чем это чревато см. здесь (http://pro-pawn.ru/showthread.php?8347), пункт 1).
По сути это ни что иное как поощрение плохих практик программирования, поэтому я бы не советовал так называть аргументы функции и локальные переменные. Проблемы нужно решать, а не избегать.
Лично я предпочитаю CombSort :smile:
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 чисел пересортировало с таким результатом:
CombSort: 119 ms
Nexius_Tailer
16.01.2017, 15:28
Лично я предпочитаю CombSort :smile:
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 чисел пересортировало с таким результатом:
CombSort: 119 ms
Принимай во внимание то, что характеристики компьютеров с автором темы у вас разные, соответственно тест скорости отдельно этой функции объективно сравнить с теми, что в шапке темы, нельзя)
Скорее всего, расчёт на быдлокодеров, которые могут назвать глобальную переменную "array" (чем это чревато см. здесь (http://pro-pawn.ru/showthread.php?8347), пункт 1).
Первый пункт в той теме как-то заморочен. Переменные не обязательно называть именно длинными именами, достаточно просто уникальными
Первый пункт в той теме как-то заморочен. Переменные не обязательно называть именно длинными именами, достаточно просто уникальными
Уникальность переменных с короткими именами ограничена размерами английского алфавита. Под короткими именами, как можно заметить в примере, подразумеваются переменные, состоящие из одной-двух букв.
Принимай во внимание то, что характеристики компьютеров с автором темы у вас разные, соответственно тест скорости отдельно этой функции объективно сравнить с теми, что в шапке темы, нельзя)
А где ты увидел сравнение или я написал что при сравнение получился такой результат? Я просто оставил свои результаты теста, даже не стал тестировать функции от автора. Если бы сравнивал, то обязательно бы указал все результаты теста включая функции автора!
Daniel_Cortez
16.01.2017, 16:51
#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.
Хоть я и добавил проверку отсортированных данных, всё равно такое ощущение, будто что-то сделал не так - уж слишком подозрительна разница в результатах.
$continue$
16.01.2017, 17:16
Наверное, стоит дополнить тему статьей с habrahabr (https://habrahabr.ru/post/188010/)
И коль гоняетесь за скоростью в Pawn, то почему ещё никто не выложил RadixSort (https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%80%D0%B0%D0%B7%D1%80%D1%8F%D0%B4%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0) на pro-pawn?
Я бы реализовал, но у меня не так много времени.
Nexius_Tailer
16.01.2017, 17:50
Уникальность переменных с короткими именами ограничена размерами английского алфавита. Под короткими именами, как можно заметить в примере, подразумеваются переменные, состоящие из одной-двух букв.
Ну так короткие это не обязательно однобуквенные, если по тексту.
Если просто стараться сделать длиннее, то шанс совпадения возрастёт у таких же любителей писать названия длиннее, поэтому важнее присваивать имя, ориентируясь на ситуации в коде, где эта переменная будет использоваться... или просто что-то редко встречающееся.
Вообще шанс совпадений будет всегда, просто главная мысль как обычно не допускать такой банальщины, как называние переменных слишком абстрактными именами, а-ля "data, str, x". А слишком длинные названия очень часто просто неудобно читать, особенно если они часто вызываются.
А где ты увидел сравнение или я написал что при сравнение получился такой результат? Я просто оставил свои результаты теста, даже не стал тестировать функции от автора. Если бы сравнивал, то обязательно бы указал все результаты теста включая функции автора!
Нигде? Я написал про то, что в тестах просто не было необходимости в принципе, ибо они не комплексные
И коль гоняетесь за скоростью в Pawn, то почему ещё никто не выложил RadixSort (https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%80%D0%B0%D0%B7%D1%80%D1%8F%D0%B4%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0) на pro-pawn?
Год назад я переводил почти все типы сортировок, да RadixSort был быстрее остальных (из тех, которых я перевел), но если память не изменяет там используется рекурсия для сортировки.
Seregamil
16.01.2017, 21:37
Глупый вопрос, но зачем _ перед переменной?
Обычно так обозначают приватную переменную в классе. В Pawn так можно обозначать глобальные static переменные в различных библиотеках. А причина использования здесь не ясна.
Скорее всего, расчёт на быдлокодеров, которые могут назвать глобальную переменную "array" (чем это чревато см. здесь (http://pro-pawn.ru/showthread.php?8347), пункт 1).
По сути это ни что иное как поощрение плохих практик программирования, поэтому я бы не советовал так называть аргументы функции и локальные переменные. Проблемы нужно решать, а не избегать.
На вид явный идиотизм автора данной темы и вообще быдлокодинг тот еще.
И результаты тестов, которые приложил DC:
Без -d3
[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
[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
Daniel_Cortez
16.01.2017, 21:56
Без -d3
[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
[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).
Seregamil
16.01.2017, 22:00
Флаг -d3 подразумевает под собой отсутствие оптимизации байткода (-O0). ИМХО, для тестов разумно компилировать с оптимизацией 1-го уровня (-O1), т.к. на 2-м используются макроинструкции, которые поддерживаются только в Pawn 3.2 (в SA-MP компилятор от 3.2, хотя в сервере встроен интерпретатор версии 3.0).
Многие держат сервера, мод которых скомпилирован с флагом -d3, поэтому я добавил результаты тестов именно с ним.
$continue$
17.01.2017, 16:21
В нормальной реализации RadixSort - рекурсия не нужна.
Год назад я переводил почти все типы сортировок, да RadixSort был быстрее остальных (из тех, которых я перевел), но если память не изменяет там используется рекурсия для сортировки.
В нормальной реализации RadixSort - рекурсия не нужна.
Да, собственно, от любой рекурсии можно избавиться, только код немного усложнится.
Powered by vBulletin® Version 4.2.0 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved. Перевод: zCarot