оамечание

Во многих случаях вполне достаточно пузырьковой сортировки, дающей в сравнении с другими алгоритмами хорошую или наилучшую производительность для наборов данных до 1000 элементов. Для наборов объемом до 100 элементов пузырьковая сортировка несмотря на простоту по производительности близка к другим. Для выборок объемом до 1000 элементов наилучшую производительность дает сортировка методом выбора (модификация пузырьковой сортировки). Одним из наиболее быстрых методов сортировки больших выборок является быстрая сортировка, работающая по принципу "разделяй и властвуй". Производительность быстрой сортировки зависит от того, насколько выборка близка к случайной; в случае частично отсортированных данных ее производительность падает.

Шаблон пузырьковой сортировки

Метод пузырьковой сортировки состоит в последовательном сравнении и при необходимости перестановке всех соседних значений в сортируемом массиве; таким образом данные, как пузырьки, всплывают вверх. Этот тип сортировки на удивление хорош для малых выборок. Так называемая формула порядка величины для производительности различных алгоритмов дает для пузырьковой сортировки результат 0(п2). Для больших наборов данных время растет экспоненциально, что ведет к очень низкой производительности. Однако для выборок объемом менее 1000 элементов этот тип сортировки работает достаточно быстро.

Интересно отметить, что оценка производительности по порядку величины предполагает вполне конкретную реализацию алгоритма — вложенные циклы for. Однако хватит пока теории. Возьмем для начала целочисленные данные; сортировка массива целых чисел будет выглядеть так:

int а[] = ( 10, 9, 8, 1, б, 5, 4, 3, 2, 1 };

const unsigned int МДХ = sizeof ( а) / sizeof ( а[0]);

for ( int j = 0; j < МДХ - 1; j++)

for ( int k = j +1; k < MAX; k++)

if ( a[j] > a[k]) Swap! a[j], a[k]);

Это коротко, изящно, и, как несложно заметить, просто реализуется (функция Swap, конечно, прилагается). Прикинув, какой из элементов функции разумно сделать параметром, можно превратить целочисленную версию в шаблон. Естественно, это тип данных массива. Здесь есть, однако, еще одна тонкость: операция сравнения operator> может быть определена не для всех типов данных. Решением здесь может быть документирование требований к типу данных. В качестве альтернативы можно предложить поискать другой метод сравнения данных. Во фрагменте кода, приведенном ниже, представлены оба варианта: и документирование требования наличия операции сравнения, и обход этого требования путем введения функции ^IsGreaterO.