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

[alex_bas]

Ради интереса сегодня проверил на скорость алгоритмы сортировки массивов.
Вот что получилось:
Язык: C#
Число элементов массива 100000:
Сортировка методом Array.Sort() 0,025 секунд
Сортировка методом фон Неймана (Слияний) 0,05 секунд
Сортировка методом пузырька 61,3 секунд
Сортировка методом выборки 53,9 секунд
Сортировка методом бинарных вставок 0,029 секунд
Сортировка методом простых вставок 57,49 секунд
Сортировка методом Шелла 0,023 секунд
Сортировка методом Флойда 0,101 секунд


метод который производил подсчет времени:

public class PerfCounter
{
private Int64 _start;

public void Start()
{
_start = 0;
QueryPerformanceCounter(ref _start);
}

public float Finish()
{
Int64 finish = 0;
QueryPerformanceCounter(ref finish);

Int64 freq = 0;
QueryPerformanceFrequency(ref freq);
return (((float)(finish - _start) / (float)freq));
}

[DllImport("Kernel32.dll")]
private static extern bool QueryPerformanceCounter(ref Int64 performanceCount);

[DllImport("Kernel32.dll")]
private static extern bool QueryPerformanceFrequency(ref Int64 frequency);
}

реализация алгоритмов приведена здесь: http://alglib.sources.ru/sorting/ поэтому её повторять не буду. Кому надо посмотрит.

Может кому пригодиться......

[X0R]

На каком массиве производилось сравнение? Обычно при сравнении алгоритмов сортировки приведят 3 результата: для упорядоченного массива, для масива упорядоченного в обратном поряде и для неупорядоченного массива.

[alex_bas]

Сравнение производилось для неупорядоченного массива заполненного случайными числами

[X0R]

Если не трудно - произведи исследования для двух других указанных мною массивов...

[alex_bas]

Абсолютно не трудно, наоборот даже интересно

Это для массива длинной 10 000

********Сортировка неупорядоченного массива********
Сортировка массива встроенным методом 0,00233661
Сортировка массива методом фон Неймана (слияний) 0,004402794
Сортировка массива методом пузырька 0,596808
Сортировка массива методом выборки 0,5233509
Сортировка массива методом бинарных вставок 0,003131124
Сортировка массива методом простых вставок 0,5525088
Сортировка массива методом Шелла 0,002537473
Сортировка массива методом Флойда 0,007440331

********Сортировка упорядоченного массива********
Сортировка массива встроенным методом 0,0006665651
Сортировка массива методом фон Неймана (слияний) 0,003235327
Сортировка массива методом пузырька 0,6009364
Сортировка массива методом выборки 0,5105451
Сортировка массива методом бинарных вставок 0,002499759
Сортировка массива методом простых вставок 0,563573
Сортировка массива методом Шелла 0,002034057
Сортировка массива методом Флойда 0,006385728

********Сортировка массива упорядоченного в обратном поряде********
Сортировка массива встроенным методом 0,0009372699
Сортировка массива методом фон Неймана (слияний) 0,003067429
Сортировка массива методом пузырька 0,5943149
Сортировка массива методом выборки 0,510635
Сортировка массива методом бинарных вставок 0,003719467
Сортировка массива методом простых вставок 0,5690944
Сортировка массива методом Шелла 0,001935162
Сортировка массива методом Флойда 0,006626261

[alex_bas]

Это для массива длинной 100 000
********Сортировка неупорядоченного массива********
Сортировка массива встроенным методом 0,01926586
Сортировка массива методом фон Неймана (слияний) 0,0475309
Сортировка массива методом пузырька 63,1443
Сортировка массива методом выборки 55,35486
Сортировка массива методом бинарных вставок 0,03108663
Сортировка массива методом простых вставок 59,57388
Сортировка массива методом Шелла 0,02835444
Сортировка массива методом Флойда 0,07461591
********Сортировка упорядоченного массива********
Сортировка массива встроенным методом 0,00986103
Сортировка массива методом фон Неймана (слияний) 0,04424221
Сортировка массива методом пузырька 63,06662
Сортировка массива методом выборки 55,34121
Сортировка массива методом бинарных вставок 0,03050974
Сортировка массива методом простых вставок 59,57836
Сортировка массива методом Шелла 0,02780074
Сортировка массива методом Флойда 0,07067519
********Сортировка массива упорядоченного в обратном поряде********
Сортировка массива встроенным методом 0,01108521
Сортировка массива методом фон Неймана (слияний) 0,0441341
Сортировка массива методом пузырька 63,06378
Сортировка массива методом выборки 56,10776
Сортировка массива методом бинарных вставок 0,02986609
Сортировка массива методом простых вставок 61,31496
Сортировка массива методом Шелла 0,0282508
Сортировка массива методом Флойда 0,07921538

В приложении программа которая расчитывала данные времена

[X0R]

Свел результаты в таблицу.

[xuser]

А где же метод Хоара (так называемая быстрая сортировка)?

[Hopkroft]

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

А где же метод Хоара (так называемая быстрая сортировка)?

IMHO быстрая и есть методом Хоара. т.е. встроенная вроде как и реализована с помощью быстрой сортировки