Теория:
Под сортировкой (упорядочением) массива понимают перераспределение значений его элементов в некотором определённом порядке.
Порядок, при котором в массиве первый элемент имеет самое маленькое значение, а значение каждого следующего элемента не меньше значения предыдущего элемента, называют возрастающим.
Порядок, при котором в массиве первый элемент имеет самое большое значение, а значение каждого следующего элемента не больше значения предыдущего элемента, называют убывающим.
Цель сортировки — облегчить последующий поиск элементов: искать нужный элемент в упорядоченном массиве легче.
Вы уже встречались с сортировкой при работе с базами данных. Сейчас мы рассмотрим один из возможных вариантов реализации механизма этой операции — сортировку выбором.
Сортировка выбором (например, по убыванию) осуществляется следующим образом:
- В массиве выбирается максимальный элемент;
- Максимальный и первый элементы меняются местами (первый элемент считается отсортированным);
- В неотсортированной части массива снова выбирается максимальный элемент; он меняется местами с первым неотсортированным элементом массива;
- Действия, описанные в пункте \(3\), повторяются с неотсортированными элементами массива до тех пор, пока не останется один неотсортированный элемент (его значение будет минимальным).
Рассмотрим процесс сортировки выбором на примере массива .
В этом массиве из восьми элементов операцию выбора максимального элемента мы проводили \(7\) раз. В массиве из \(n\) элементов такая операция будет проводиться \(n-1\) раз.
Источники:
Босова Л. Л., Босова А. Ю., Информатика: учебник для 9 класса. М. : БИНОМ. Лаборатория знаний, 219 с.