Сортировка

Сортировка

Что значит «отсортирован»; сортировка выбором вручную и её цена; sort для вектора, массива, части и по убыванию; сортировка строк и символов; сортировка пар, чтобы помнить исходные позиции; что упрощает отсортированный вектор.

Теория

Урок 3 из 12

10 мин чтения

Вопросов: 5

Список оценок, список цен, дети класса по росту: очень многие задачи начинаются со слов «расположите по порядку», а очень многие другие становятся простыми, как только данные уже упорядочены. Этот урок о сортировке — сначала один раз вручную, чтобы увидеть, чего она стоит, а потом силами C++.

Что значит «отсортирован»

Вектор отсортирован по возрастанию, когда каждый элемент не меньше предыдущего: a[i - 1] <= a[i] для каждого i. Равные значения могут стоять рядом, так что 1 3 3 7 отсортирован. Сортировка переставляет значения и больше ничего: те же числа, столько же копий каждого, в новом порядке.

Даны n оценок. Выведите их от самой низкой к самой высокой, а затем три самые высокие.

Сортировка вручную: сортировка выбором

Вот как это сделал бы человек с рядом карт. Найти самую маленькую карту и обменять её с первой. Затем найти самую маленькую среди остальных и обменять её со второй. И так далее; каждый ход окончательно закрепляет ещё одну позицию. Это сортировка выбором: каждый ход выбирает наименьшее из того, что осталось:

Сортировка выбором: наименьшее из остатка переходит вперёд

C++

1#include <bits/stdc++.h>

2using namespace std;

4int main() {

5 ios_base::sync_with_stdio(false);

6 cin.tie(NULL);

8 vector<int> a = {7, 3, 9, 1};

9 int n = 4;

10 for (int i = 0; i < n - 1; i++) {

11 int best = i;

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

13 if (a[j] < a[best]) {

14 best = j;

15 }

16 }

17 swap(a[i], a[best]);

18 }

19 for (int x : a) {

20 cout << x << " ";

21 }

22 cout << "\n";

23 return 0;

24}

Четыре числа

строка 8

Сортировка выбором: найти наименьшее и поставить первым; затем наименьшее из остальных — вторым; и так далее.

a4 ячеек

n—i—best—j—x—

1 / 40

Практика: Сортировка

Тринадцать задач на sort: по возрастанию и убыванию, буквы, медианы и k-е значения, подстроки и пары, которые помнят свой индекс или сортируются по выбранной половине.

Вопрос	После сортировки
наименьшее и наибольшее	`a[0]` и `a[n - 1]`
k-е наименьшее (k от 1)	`a[k - 1]`
медиана n значений	средний элемент, `a[(n - 1) / 2]`; при чётном n средних два, и это меньший из них — нижняя медиана
есть ли два равных значения?	сравнить каждое `a[i]` с `a[i - 1]`
два самых близких значения	наименьшая разность `a[i] - a[i - 1]`: близкие значения теперь соседи

Что значит «отсортирован»

Сортировка вручную: сортировка выбором

Практика: Сортировка

sort: пусть сортирует библиотека

Строки и символы

Сортировка пар: помним, откуда что взялось

Что открывает сортировка

Проверьте себя