Сравнение простых алгоритмов сортировки

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

Схожей вычислительной сложностью обладают еще два распространенных алгоритма - сортировка вставками (insertion sort) и сортировка выбором (selection sort):

voidinsertionSort ( int* _pData, const int_N )

{

for( inti = 1; i < _N; i++ )

{

intj = i;

while( j && ( _pData[ j ] < _pData[ j - 1 ] ) )

{

inttemp = _pData[ j - 1 ];

_pData[ j - 1 ] = _pData[ j ];

_pData[ j ] = temp;

--j;

}

}

}

voidselectionSort ( int* _pData, const int_N )

{

for( inti = 0; i < _N - 1; i++ )

{

intlowIndex = i;

for( intj = i + 1; j < _N; j++ )

if( _pData[ j ] < _pData[ lowIndex ] )

lowIndex = j;

inttemp = _pData[ lowIndex ];

_pData[ lowIndex ] = _pData[ i ];

_pData[ i ] = temp;

}

}

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

Когда на вход подается уже отсортированный массив, алгоритм сортировки вставками не делает ни одной перестановки данных, осуществляя при этом всего N-1 сравнение. Соответственно, в лучшем случае его вычислительная сложность стремится к линейной. Сортировка выбором таким интересным свойством не обладает, и для получения результата на отсортированном массиве сделает N22сравнений и N-1 перестановку.

Когда же на вход будет подан массив, отсортированный в обратном порядке, алгоритм сортировки вставками сделает по N22перестановок и сравнений, а алгоритм сортировки выбором сохранит свои свойства, осуществив N22сравнений и N-1 перестановку на любом входном наборе данных.

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

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

Время сортировки случайного набора данных (средний случай):

Время сортировки уже отсортированных данных (лучший случай):

Время сортировки данных, отсортированных в обратном порядке (худший случай):

Из полученных данных измерений можно сделать интересные выводы:

• Метод сортировки выбором в среднем является наиболее эффективным, кроме того его время выполнения стабильно на любом наборе поданных входных данных. Стабильное время выполнения - это важная характеристика алгоритма, когда о характере подаваемых данных заранее ничего не известно.
• Метод сортировки вставками существенно выигрывает у двух других при подаче уже отсортированного массива (фактически, время выполнения настолько малое, что его не удается замерить), однако заметно проигрывает сортировке выбором в худшем случае.