Сортировка элементов массива

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

Алгоритмы сортировки элементов массива по возрастанию или убыванию полностью идентичны и отличаются только проверяемым во внутреннем цикле условием. Поэтому в качестве примера рассмотрим алгоритм сортировки элементов массива по возрастанию их значений (рис. 5.3).

Внешний цикл «Для» на основе блока модификации (блок 1) по параметру i будет перебирать все элементы массива Х, начиная с первого и заканчивая предпоследним (N -1 -ым) элементом. Для каждого выбранного во внешнем цикле «главного» элемента X_i организовывается внутренний цикл «Для» на основе блока модификации (блок 2), который будет перебирать элементы того же самого массива Х, только по параметру j. При этом перебираться будут элементы со следующего (i +1) после текущего «главного» элемента и заканчивая последним (N -ым) элементом. Таким образом, выбранный i -й элемент во внутреннем цикле (блок 3) поочередно будет сравниваться со всеми стоящими после него в массиве элементами (элементами с индексом j). Если «главный» i -й элемент оказывается больше, чем последующий j -й элемент, то их значения меняются местами (блок 4). Обмен значений двух элементов массива выполняется за 3 шага, с использованием дополнительной переменной a.

В процессе этих обменов в i -ю позицию будут выставляться все меньшие и меньшие значения. После завершения работы внутреннего цикла в i -м элементе массива будет находиться наименьшее, среди находящихся после «главного» элемента, значение. Затем во внешнем цикле выбирается следующий «главный» элемент, для которого выполняются те же самые действия и т.д. В итоге весь массив будет отсортирован в порядке возрастания значений его элементов.

Пусть массив Х состоит из четырех элементов {5; 7; 3; 2}. Пошаговое выполнение внутреннего цикла, при выбранном в качестве «главного» 1-го, а затем 2-го элементов массива, приведено ниже:

№ шага	X 1	X 2	X 3	X 4		№ шага	X 1	X 2	X 3	X 4
								7
	↑ i =1	↑ j= 2						↑ i =2	↑ j= 3
	5							5
	↑ i =1		↑ j= 3					↑ i =2		↑ j= 4
	3					Итог
	↑ i =1			↑ j= 4
Итог

В итоге вначале в 1-й элемент массива занесено наименьшее значение. Затем во 2-й элемент массива занесено наименьшее среди оставшихся значение и т.д.

Для того чтобы этот алгоритм выполнял сортировку по убыванию достаточно в блоке 3 поменять знак больше на знак меньше.