Сравнение простых алгоритмов сортировки
Рассмотренная ранее пузырьковая сортировка является примитивным методом и практически не имеет применения в реальном программном обеспечении, как обладающая довольно высокой квадратичной вычислительной сложностью.
Схожей вычислительной сложностью обладают еще два распространенных алгоритма - сортировка вставками (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-х вариантах - случайные данные, отсортированные данные и данные, отсортированные в противоположном порядке. Разумеется, при выполнении на другом компьютере абсолютные значения времени могут существенно отличаться, однако пропорции между значениями должны сохраниться.
Время сортировки случайного набора данных (средний случай):
Количество данных | Пузырьковая | Вставками | Выбором |
100 000 | 57.500s | 33.781s | 23.156 |
50 000 | 14.360s | 8.406s | 5.796s |
20 000 | 2.296s | 1.359s | 0.921s |
10 000 | 0.578s | 0.343s | 0.234s |
5 000 | 0.141s | 0.093s | 0.062s |
Время сортировки уже отсортированных данных (лучший случай):
Количество данных | Пузырьковая | Вставками | Выбором |
100 000 | 23.156s | < 0.001s | 23.140s |
50 000 | 5.796s | < 0.001s | 5.782s |
20 000 | 0.922s | < 0.001s | 0.938s |
10 000 | 0.218s | < 0.001s | 0.234s |
5 000 | 0.063s | < 0.001s | 0.063s |
Время сортировки данных, отсортированных в обратном порядке (худший случай):
Количество данных | Пузырьковая | Вставками | Выбором |
100 000 | 61.781 | 67.563s | 24.157s |
50 000 | 15.454s | 16.906s | 6.047s |
20 000 | 2.469s | 2.703s | 0.953s |
10 000 | 0.625s | 0.672 s | 0.235s |
5 000 | 0.156s | 0.157s | 0.062s |
Из полученных данных измерений можно сделать интересные выводы:
- Метод сортировки выбором в среднем является наиболее эффективным, кроме того его время выполнения стабильно на любом наборе поданных входных данных. Стабильное время выполнения - это важная характеристика алгоритма, когда о характере подаваемых данных заранее ничего не известно.
- Метод сортировки вставками существенно выигрывает у двух других при подаче уже отсортированного массива (фактически, время выполнения настолько малое, что его не удается замерить), однако заметно проигрывает сортировке выбором в худшем случае.
Дата добавления: 2016-01-29; просмотров: 1039;