Сортировка массива: основы
💻 Информатика · 8 класс
Что такое сортировка
Сортировка массива — это перестановка его элементов в определённом порядке: по возрастанию или по убыванию. Отсортированные данные легче просматривать, в них быстрее искать нужное значение, проще находить наибольший и наименьший элементы. Сортировка — одна из базовых задач обработки массивов, и с неё начинается знакомство с целым разделом информатики, посвящённым алгоритмам упорядочивания.
Зачем сортировать
- чтобы быстро найти наибольшее или наименьшее значение — после сортировки оно окажется с краю массива;
- чтобы упорядочить список для человека (фамилии по алфавиту, оценки по возрастанию, товары по цене);
- чтобы ускорить дальнейший поиск элементов — в упорядоченном массиве искать гораздо легче.
Сортировка обменом
Самый простой для понимания способ — сортировка обменом, которую ещё называют «пузырьковой». Идея такая: соседние элементы сравнивают попарно, и если они стоят в неправильном порядке, их меняют местами. За один проход по всему массиву наибольший элемент постепенно «всплывает» в конец, словно пузырёк воздуха в воде. Затем проходы повторяют до тех пор, пока массив не станет полностью упорядоченным.
Разбор примера
Отсортируем по возрастанию массив из трёх чисел 5 3 4. Покажем один проход по соседним парам.
| Сравниваем | Было | Меняем? | Стало |
|---|---|---|---|
| 5 и 3 | 5 3 4 | да | 3 5 4 |
| 5 и 4 | 3 5 4 | да | 3 4 5 |
После этого прохода наибольший элемент 5 оказался в конце, и массив стал упорядоченным. В более длинных массивах одного прохода не хватает, и их повторяют несколько раз.
Обмен значениями
Чтобы поменять два элемента местами, используют вспомогательную переменную — иначе одно из значений будет затёрто и потеряется:
t = a[i]
a[i] = a[i+1]
a[i+1] = t
Сначала значение прячут в t, затем на его место переносят соседа, и только потом из t восстанавливают значение во второй ячейке.
По возрастанию и по убыванию
Чтобы изменить направление сортировки, достаточно поменять знак сравнения. Если при сортировке по возрастанию мы меняем элементы местами, когда левый больше правого, то для сортировки по убыванию обмен делают, когда левый меньше правого. Сам алгоритм при этом остаётся прежним — меняется только условие обмена. Кроме сортировки обменом существуют и другие методы: сортировка выбором и сортировка вставками, но именно обменная сортировка самая наглядная для первого знакомства.
Частые ошибки. При обмене обязательно используйте третью переменную: без неё одно из значений теряется. Следите за границами индексов — нельзя сравнивать последний элемент с несуществующим соседом за концом массива. И помните, что одного прохода обычно недостаточно: проходы повторяют до полной упорядоченности массива.
Кратко о главном
- Сортировка — это упорядочивание элементов массива.
- Сортировать можно по возрастанию или по убыванию.
- Сортировка обменом сравнивает и переставляет соседние элементы.
- За проход крайний элемент встаёт на своё место.
- Обмен значений выполняют через вспомогательную переменную.
- Проходы повторяют, пока массив не упорядочится полностью.