 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Сортировка массива выбором
|
|
Пример 3. Сначала рассмотрим алгоритм такой сортировки, например, по убыванию. На первом этапе выбираем наибольший элемент всего массива, его номер k и переставляем x[0] c x[k], если k!=0. На втором этапе находим максимальный элемент, начиная со второго элемента x[1], его номер k и переставляем x[1] c x[k], если k!=1. Дальше находим наибольший элемент, начиная с третьего элемента x[2], его номер k и переставляем x[2] c x[k], если k!=2. Так продолжаем до конца массива. То есть на последнем этапе выбираем наибольший из двух последних элементов и, если надо, переставляем их.
Для массива 54, 43. 11. 77, 33, 90, 16 последовательно получим
11, 43. 54. 77, 33, 90, 16
11, 16. 54. 77, 33, 90, 43
11, 16. 33. 77, 54, 90, 43
11, 16, 33, 43, 54, 90, 77
11, 16, 33, 43, 54, 90, 77
11, 16, 33, 43, 54, 77, 90
Подчёркнуты и выделены числа, которые переставлялись на каждом этапе. Заметим, что на пятом этапе x[4] = 54 совпадает с наименьшим из трёх оставшихся чисел (k=4). Поэтому перестановка не выполнялась.
Программа рассмотренного алгоритма:
int MyMin, // минимальный элемент
k; // номер минимального элемента
/* Цикл для многократного поиска минимального элемента и перестановки его с тем, начиная с которого осуществляли поиск. */
for (int start=0; start<size-1; start++)
{ /* Поиск минимального элемента и его номера для части массива x[start], x[start+1], …, x[size-1] */
MyMin=x[start]; k=start;
for (int i=k+1; i<size; i++)
if (x[i]<MyMin) { MyMin=x[i]; k=i; }
/* Перестановка наименьшего элемента с номером k с x[start] */
x[k]=x[start]; x[start]=MyMin; }
Дата публикования: 2015-02-18; Прочитано: 240 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
