Сортировка методом прямого выбора(включения)

Сортировки

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

a[1]≤ a[2]≤ …≤ a[size]

Все методы сортировки можно разделить на 2 группы: прямые и улучшенные.

К прямым относятся:

1. Метод прямого выбора

2. Метод прямого обмена

3. Метод вставкой

Улучшенные методы основаны на тех же принципах, что и прямые, однако используют некоторые методы для улучшения сортировки.

При решении задач сортировки выдвигается требование минимальности использования памяти. Дополнительные массивы не заводят. При оценки быстродействия алгоритма сортировки используют 2 показателя:

1. Количество присваиваний

2. Количество сравнений.

Сортировка методом прямого выбора(включения)

Алгоритм сортировки методом прямого выбора может быть представлен следующим образом:

1. Просматривается массив от первого элемента. Необходимо найти минимальный и поместить его на место первого, а первый на место минимального.

2. Просматривая массив от второго элемента, необходимо найти минимальный и поместить его на место второго элемента, а второй на место минимального. И так далее, до предпоследнего элемента.

Код(C++):

for(i=0; i < ArraySize - 1; i++){

min = i;

for(j = i+1; j < ArraySize; j++)

if (a[j] < a[min]) min = j;

buf = a[i];

a[i] = a[min];

a[min] = buf;

for(k=0; k < ArraySize; k++)

cout < < a[k] < < endl;

}

(size² - size)/2 – количество сравнений, которые необходимо сделать для упорядочивания массива.

Пример:

Вот как изменяется значение массива из пяти элементов (50, 10, 20, 30, 40)

50 10 20 30 40

10 50 20 30 40

10 20 50 30 40

10 20 30 50 40

10 20 30 40 50

Подчеркнута область поиска найменьшего элемента.

Сортировка методом прямого обмена:

Алгоритм:

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

Код(C++):

for (i=1; i < ArraySize – 1; i++){

for (k=0; k < ArraySize - 1; k++)

if (a[k] > a[k+1]){

buf = a[k];

a[k] = a[k+1];

a[k+1] = buf;

}

for(k=0; k < ArraySize; k++)

cout < < a[k] < < endl;

}

Количество операций сравнения -- (size² - size)/2.

Пример:

Дан массив. Отсортировать методом прямого обмена.