Сортировка посредством прямого выбора

 

Пусть в массиве A содержится n элементов. Требуется отсортировать массив по возрастанию. Алгоритм сортировки посредством прямого выбора заключается в последовательных проходах по неотсортированным элементам массива и выбору при каждом проходе очередного минимального элемента из оставшихся. По массиву A необходимо выполнить n–1 проход. В 0-вом проходе выбирается наименьший элемент из A[0]…A[n–1], который меняется местами с A[0]. После этого неупо­рядоченными остаются элементы A[1]…A[n–1]. В следующем проходе просматривается эта неупорядоченная часть элементов массива, выбирается наименьший из них элемент и меняется местами с A[1]. В следующем проходе производится поиск наименьшего элемента в подмассиве A[2]…A[n–1]. Найденное значение меняется местами с A[2]. В результате выполнения n–1 прохода неупорядоченный фрагмент массива сокращается до одного элемента, который и является наибольшим.

В i-том проходе сканируется подмассив A[i]…A[n–1] и переменной minIndex присваивается индекс наименьшего элемента в этом подмассиве. Затем элементы A[i] и A[minIndex] меняются местами.

 

Рассмотрим сортировку по возрастанию посредством выбора на примере массива, содержащего пять целых чисел: 9, 3, 5, 10, 7. Упорядочим массив по возрастанию. Число элементов в массиве n = 5, проходов требуется n–1 = 4.

 

Исходный массив А:

 

0-проход: сканируется фрагмент A[0]…A[4],

minIndex = 1, A[0]↔A[1]

 

 

1-проход: сканируется фрагмент A[1]…A[4],

minIndex = 2, A[1] ↔A[2]

 

 

2-проход: сканируется фрагмент A[2]…A[4],

minIndex = 4, A[2] ↔A[4]

 

3-проход: сканируется фрагмент A[3]…A[4],

minIndex = 4, A[3] ↔A[4]

 

 

Массив A отсортирован по возрастанию.

 

 

Сортировка простыми обменами (пузырьковая)

 

Этот алгоритм основан на сравнении и обмене в случае инверсии пар соседних элементов до их полного упорядочивания.

Для сортировки n-элементного массива A простыми обменами требуется n–1 проход. При каждом проходе сравниваются соседние элементы, и в случае инверсии (при сортировке по возрастанию если правый из них меньше левого), эти элементы меняются местами. К моменту окончания каждого прохода (справа налево) наименьший элемент опускается к началу текущего подмассива. Например, по окончании 0-прохода начало массива (элемент A[0]) отсортировано, а хвостовая часть остаётся неупорядоченной.

При i-том проходе сканируется подмассив A[n–1]…A[i]. Сравниваются соседние элементы: (A[n–2], A[n–1]), …, (A[i], A[i+1]). В каждой паре (A[j], A[j+1]) элементы меняются местами при условии, что A[j] > A[j+1]. В конце прохода наименьшее значение оказывается в элементе A[i].

 

Рассмотрим пузырьковую сортировку на примере массива, содержащего пять целых чисел: 9, 3, 5, 10, 7. Число элементов в массиве n = 5, проходов требуется n – 1 = 4.

 

Исходный массив А:

 

0-проход: сканируются элементы A[4]…A[0], совершаются следующие обмены: A[4]=7↔A[3]=10; A[1]=3↔A[0]=9

 

 

1-проход: сканируются элементы A[4]…A[1], совершаются следующие обмены: A[2]=5 ↔A[1]=9

 

 

2-проход: сканируются элементы A[4]…A[2], совершаются следующие обмены: A[3]=7↔A[2]=9

 

 

3-проход: сканируются элементы A[4]…A[3], обменов нет

 

 

Массив A отсортирован по возрастанию.

 

Примечание. Направление сканирования (справа налево или слева направо) можно задавать любое.

 

В модификации алгоритма, называемой «шейкерной сорти­ровкой», сканирование поочерёдно меняет направление – чётные проходы слева направо, нечётные – справа налево.