Задача сортировки массива

Многие знакомы с задачей сортировки, и, вроде бы, всем понятно, что сортировать массивы нужно, однако на вопрос «Зачем это делать?» даст ответ не каждый. Подумайте, зачем сортировать массивы или списки. Представьте себе, если бы слова в словаре располагались бы не в алфавитном порядке, а в разброс; или товары в магазине не были бы разложены по типам, и разные марки колбасы находились бы по всему магазину.

Отсутствие порядка существенно затрудняет поиск. А как можно достичь порядка? Сортировкой. Именно облегчение последующего поиска является главной причиной, по которой производится сортировка. Существует масса методов, сортирующих массивы. Мы рассмотрим три наиболее простых для понимания и реализации метода: метод прямого выбора, метод пузырьковой сортировки и сортировку вставками. Метод прямого выбора – это наиболее очевидный для понимания способ сортировки массива, а пузырьковая сортировка – наиболее проста в реализации. Сортировка вставками довольно часто используется нами в жизни.

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

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

for (int i=0; i<size; i++) {

//Поиск минимального элемента

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

//i, i+1, i+2,..., size

int j_min = i;

for (int j=i+1; j<size; j++) {

if (numbers[j_min] > numbers[j]) {

j_min = j;

}

//Перестановка элементов

//с индексами i и j_max

int temp = numbers[i];