1. Основные понятия алгоритмизации и программирования

-14^*	22	13	28	6	41	-5	18	0	35	6
-15
2-й шаг:	-14	13^*	22	28	6	41	-5	18	0	35	6	-15
3-й шаг:	-14	13	22	28^*	6	41	-5	18	0	35	6	-15
4-й шаг:	-14	6^*	13	22	28	41	-5	18	0	35	6	-15
5-й шаг:	-14	6	13	22	28	41^*	-5	18	0	35	6	-15
6-й шаг:	-14	-5^*	6	13	22	28	41	18	0	35	6	-15
7-й шаг:	-14	-5	6	13	18^*	22	28	41	0	35	6	-15
8-й шаг:	-14	-5	0^*	6	13	18	22	28	41	35	6	-15
9-й шаг:	-14	-5	0	6	13	18	22	28	35^*	41	6	-15
10-й шаг:	-14	-5	0	6	6^*	13	18	22	28	35	41	-15
11-й шаг:	-15^*	-14	-5	0	6	6	13	18	22	28	35	41

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

• 
  найден первый слева элемент a[j] ≥ a[i], что говорит о необходимости вставки a[i] между a[j] и a[j-1], в частности, если j=1, то a[i] помещается в первую позицию, что влечет за собой необходимость увеличения диапазона индекса массива на единицу;
  
• 
  достигнут правый конец отсортированной части массива (правый барьер), следовательно, элемент a[i] нужно оставить на прежнем месте.
  

Заметим, что сравнение и перемещение элемента a[i] в отсортированной части массива можно проводить и справа налево, начиная с (i-1)-го элемента.

9.8. Сортировка с помощью прямого выбора

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

1. 
   Выбирается элемент данного массива с минимальным (максимальным) значением (или ключом).
   
2. 
   Выбранный элемент и первый элемент меняются местами.
   
3. 
   Этот процесс повторяется с оставшимися n - 1 элементами, затем с n - 2 элементами и т.д. до тех пор, пока не останется один, самый большой/меньший элемент.
   

Всего потребуется n - 1 раз выполнить указанную последовательность действий. В процессе сортировки будет увеличиваться отсортированная часть массива, а неотсортированная соответственно уменьшаться.
В отличие от сортировки вставками, когда а каждом шаге рассматривается только один очередной элемент исходного массива и все элементы отсортированной части, среди которых ищется место для вставки, при прямом выборе для поиска одного элемента с наименьшим (наибольшим) ключом просматриваются все элементы исходного массива и найденный элемент помещается как очередной в отсортированную часть массива.
Напомним, что во всех рассматриваемых методах сортировки мы не используем промежуточных массивов.
Схему сортировки методом прямого выбора проиллюстрируем на примере массива, рассмотренного в предыдущем пункте. Элементы, которые меняются местами на очередном шаге, выделены полужирны шрифтом, а минимальные элементы неотсортированной части, кроме того, отмечены звездочкой. Отсортированная часть подчеркнута.

Исходный массив:	22	-14	13	28	6	41	-5	18	0	35	6	-15^*
1-й шаг	-15	-14^*	13	28	6	41	-5	18	0	35	6	22
2-й шаг:	-15	-14	13	28	6	41	-5^*	18	0	35	6	22
3-й шаг:	-15	-14	-5	28	6	41	13	18	0^*	35	6	22
4-й шаг:	-15	-14	-5	0	6^*	41	13	18	28	35	6	22
5-й шаг:	-15	-14	-5	0	6	41	13	18	28	35	6^*	22
6-й шаг:	-15	-14	-5	0	6	6	13^*	18	28	35	41	22
7-й шаг:	-15	-14	-5	0	6	6	13	18^*	28	35	41	22
8-й шаг:	-15	-14	-5	0	6	6	13	18	28	35	41	22^*
9-й шаг:	-15	-14	-5	0	6	6	13	18	22	35	41	28^*
10-й шаг:	-15	-14	-5	0	6	6	13	18	22	28	41	35
11-й шаг:	-15	-14	-5	0	6	6	13	18	22	28	35	41

9.9. Сортировка с помощью прямого обмена

Алгоритм данного метода сортировки заключается в последовательных просмотрах массива от начала к концу и обмене местами соседних элементов, если они образуют инверсию. Опишем алгоритм сортировки по неубыванию подробнее.
Пусть задан массив a размером n. Начинаем просмотр массива с первой пары элементов a[1] и a[2]. Если первый элемент этой пары больше второго, то меняем их местами, иначе оставляем их без изменения и сравниваем вторую пару элементов а[2] и а[3]. Если а|2] > а[3], то меняем их местами и т.д. На первом шаге будут просмотрены все пары элементов массива: а[i] и а[i+1] для i от 1 до n -1. В результате такого просмотра и необходимых обменов максимальный элемент переместится в конец массива и будет являться отсортированной частью. На втором шаге аналогичная процедура проводится с первого до (n - 1)-гo элемента. Тем самым второй по величине элемент массива переместится на предпоследнее место. Отсортированная часть будет содержать два элемента. Эти действия продолжаются до тех пор, пока количество элементов в неотсортированной части массива не уменьшится до двух. Нa последнем шаге выполняется упорядочение оставшихся двух элементов. После (n - 1) шагов массив окажется отсортированным по неубыванию. Для иллюстрации отсортируем массив по неубыванию методом простого обмена. Отсортированная часть выделена полужирным шрифтом.

Исходный массив:	22	-14	13	28	6	41	-5	18	0	35	6	-15
1-й шаг	-14	13	22	6	28	-5	18	0	35	6	-15	41
2-й шаг:	-14	13	6	22	-5	18	0	28	6	-15