Сортировка выбором

Сортировка массивов

Сортировка – это размещение объектов в определенном порядке (по возрастанию или по убыванию).

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

ü количество шагов алгоритма, необходимых для упорядочения;

ü количество сравнений элементов;

ü количество перестановок, выполняемых при сортировке.

Мы рассмотрим только три простейшие схемы сортировки.

Метод "пузырька"

По-видимому, самым простым методом сортировки является так называемый метод "пузырька". Чтобы уяснить его идею, представьте, что массив (таблица) расположен вертикально. Элементы с меньшим значением всплывают вверх наподобие пузырьков. При первом проходе вдоль массива, начиная проход "снизу", берется первый элемент и поочередно сравнивается с последующими. При этом:

§ если встречается более "тяжелый" (с большим значением) элемент, то они меняются местами;

§ при встрече с более "легким" элементом, последний становится "эталоном" для сравнения, и все следующие сравниваются с ним .

В результате наименьший элемент оказывается в самом верху массива.

Расположим массив сверху вниз, от нулевого элемента - к последнему. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом, второй по величине элемент поднимается на правильную позицию...

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

Заметим, что при втором и последующих проходах, нет необходимости рассматривать ранее "всплывшие" элементы, т.к. они заведомо меньше оставшихся. Другими словами, во время i-го прохода не проверяются элементы, стоящие на позициях выше j.

Рассмотрим данный метод на примере.

Метод состоит в том, что выбирается наименьший элемент массива и меняется местами с первым элементом. Затем рассматриваются элементы, начиная со второго, и наименьший из них меняется со вторым элементом и так далее n–1 раз.

Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n-1 последовательных шагов, начиная от 0-го и заканчивая (n-1)-м.

На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i]. Последовательность шагов при n = 5 изображена на рисунке ниже.

Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] (выделена курсивом) является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.

Setw(6) – устанавливает между одним и другим символом 6 пробелов

.