59. Сортировка данных в массивах

Широко применяется, например, сортировка перемешиванием и сортировка методом Шелла. Известен также алгоритм Quicksort (быстрая сортировка с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины). Однако самым простым считается алгоритм сортировки пузырьковым методом. Несмотря на то что пузырьковая сортировка не отличается высокой эффективностью (и в самом деле, его производительность неприемлема для сортировки больших массивов), его вполне успешно можно применять для сортировки массивов малого размера. Здесь выполняются повторяющиеся операции сравнения и при необходимости меняются местами смежные элементы. При этом элементы с меньшими значениями постепенно перемещаются к одному концу массива, а элементы с большими значениями — к другому. Пузырьковая сортировка выполняется путем нескольких проходов по массиву, во время которых при необходимости осуществляется перестановка элементов, оказавшихся "не на своем месте". Количество проходов, гарантирующих получение отсортированного массива, равно количеству элементов в массиве, уменьшенному на единицу. В следующей программе реализована сортировка массива (целочисленного типа), содержащего случайные числа. Эта программа заслуживает внимательного разбора.

// Использование метода пузырьковой сортировки

// для упорядочения массива.

#include <iostream>

#include <cstdlib>

Using namespace std;

int main()

{

　Int nums[10];

　Int a, b, t;

　Int size;

　size=10; //Количество элементов, подлежащих сортировке.

　//Помещаем в массив случайные числа.

　for(t=0; t<size; t++) nums[t]=rand();

　// Отображаем исходный массив.

　cout<<"Исходный массив:";

　for(t=0; t<size; t++) cout << nums[t]<< ' ';

　cout << '\n';

　// Реализация метода пузырьковой сортировки.

　for(a=1; a<size; а++) 　　

for(b=size-1; b>=a; b--)

{ 　

　　If (nums[b-1] >nums[b])

{ // Элементы неупорядочены. 　

　　　// Меняем элементы местами. 　

　　　t=nums[b-1]; 　　

　　 nums[b-1] =nums[b]; 　　　

　nums[b] =t; 　　

　} 　

　}

　}

　// Конец пузырьковой сортировки.

　// Отображаем отсортированный массив.

　cout << "Отсортированный массив: ";

　for(t=0; t<size; t++)

　　cout << nums[t] << ' ';

　return 0;

} Хотя алгоритм пузырьковой сортировки пригоден для небольших массивов, для массивов большого размера он становится неэффективным. Более универсальным считается алгоритм Quicksort. В стандартную библиотеку C++ включена функция qsort(), которая реализует одну из версий этого алгоритма.