Открывается в новой вкладке

Мы всегда на связи

Пишите в любое удобное время:
whatsappvktelegramMAX
Или задайте вопрос через форму:

Мы всегда на связи

Заявка принята!

Мы уже получили заявку и скоро свяжемся. Расскажите немного о ребёнке — так быстрее подберём группу (необязательно).

Спасибо!

Мы свяжемся с вами в ближайшее время.

Учебник по информатике и математике

Структурированные пути обучения: от первых программ до олимпиад и вступительных в топ-школы.
    Темы
    Заниматься с наставником
    прочитали
    3 задачи

    Сортировка выбором

    Оглавление:

    Ты расставляешь учебники на полке по высоте. Скорее всего, ты сделаешь так: найдешь самый низкий и поставишь его первым. Потом среди оставшихся снова найдешь самый низкий и поставишь вторым. И так, пока книги не кончатся.

    Это и есть сортировка выбором: на каждом шаге выбираем наименьший элемент из еще не расставленных и ставим его на следующее место. Алгоритм простой, и в нем нет ничего нового, если ты умеешь искать минимум в массиве.

    Идея алгоритма

    Массив делится на две части: слева — уже отсортированная, справа — еще нет. В начале отсортированная часть пустая. На шаге с номером $i$ (считая с нуля):

    1. Ищем минимум в неотсортированной части — от a[i] до конца массива. Это обычный поиск минимума за один проход.
    2. Меняем найденный минимум местами с a[i].
    3. Отсортированная часть выросла на один элемент.

    После $n - 1$ шагов последний элемент сам оказывается на месте: он больше всех остальных.

    Ключевая идея: Запоминаем не значение минимума, а его индекс. Без индекса не получится поменять минимум местами с a[i].

    Разбор на примере

    Высота книг в сантиметрах: [26, 21, 30, 17, 23].

    Шаг Где ищем минимум Минимум Обмен Массив после шага
    1 [26, 21, 30, 17, 23] 17 26 и 17 [17, 21, 30, 26, 23]
    2 [21, 30, 26, 23] 21 не нужен [17, 21, 30, 26, 23]
    3 [30, 26, 23] 23 30 и 23 [17, 21, 23, 26, 30]
    4 [26, 30] 26 не нужен [17, 21, 23, 26, 30]

    Обрати внимание: после третьего шага массив уже отсортирован, но алгоритм об этом не знает и все равно ищет минимум на четвертом шаге. В отличие от пузырька, сортировка выбором не умеет заканчивать раньше.

    Реализация

    Переменная m хранит индекс минимума. На втором и четвертом шаге примера минимум уже стоит на месте, и код меняет элемент сам с собой — ничего не портится, поэтому отдельную проверку не пишем.

    def selection_sort(a):
        n = len(a)
        for i in range(n - 1):
            m = i                     # индекс минимума в неотсортированной части
            for j in range(i + 1, n):
                if a[j] < a[m]:
                    m = j
            a[i], a[m] = a[m], a[i]   # ставим минимум на место i
    
    
    books = [26, 21, 30, 17, 23]
    selection_sort(books)
    print(books)  # [17, 21, 23, 26, 30]
    

    То же на C++:

    #include <iostream>
    #include <utility>
    #include <vector>
    using namespace std;
    
    void selectionSort(vector<int>& a) {
        int n = a.size();
        for (int i = 0; i < n - 1; i++) {
            int m = i;
            for (int j = i + 1; j < n; j++)
                if (a[j] < a[m]) m = j;
            swap(a[i], a[m]);
        }
    }
    
    int main() {
        vector<int> books = {26, 21, 30, 17, 23};
        selectionSort(books);
        for (int x : books) cout << x << " ";  // 17 21 23 26 30
        cout << "\n";
    }
    

    Сложность

    На первом шаге поиск минимума делает $n - 1$ сравнение, на втором $n - 2$, и так до одного:

    $$(n - 1) + (n - 2) + \ldots + 1 = \frac{n(n - 1)}{2}$$

    Число сравнений не зависит от того, каким был массив, поэтому сложность всегда $O(n^2)$ — даже если массив уже отсортирован. Зато обменов не больше $n - 1$, по одному на шаг. Дополнительная память — $O(1)$.

    Сравним с сортировкой пузырьком:

    Что сравниваем Пузырьком Выбором
    Сравнений до $\frac{n(n - 1)}{2}$ всегда $\frac{n(n - 1)}{2}$
    Обменов до $\frac{n(n - 1)}{2}$ не больше $n - 1$
    Уже отсортированный массив $O(n)$ с ранним выходом $O(n^2)$
    Порядок равных элементов сохраняется может нарушиться

    Последняя строка важна, когда сортируют не числа, а записи. Пусть оценки с именами: [5 Аня, 5 Боря, 3 Вика]. Первый шаг найдет тройку и поменяет местами Аню и Вику: [3 Вика, 5 Боря, 5 Аня]. Теперь Аня стоит после Бори, хотя в начале было наоборот. Пузырек меняет только соседей, которые стоят неправильно, поэтому равные элементы у него никогда не меняются местами.

    Мало обменов — главное достоинство сортировки выбором. Оно пригодится, когда сравнить дешево, а переставить дорого: например, на складе посмотреть на этикетку ящика легко, а передвинуть сам ящик — долго.

    Частая ошибка: Внутренний цикл с 0 вместо i + 1. Тогда минимум каждый раз находится в уже отсортированной части, и алгоритм ломает собственную работу: из [26, 21, 30, 17, 23] получится [21, 30, 26, 17, 23]. Другая ловушка — менять элементы местами сразу, как только нашелся меньший. Массив отсортируется, но обменов станет гораздо больше, и пропадет главное преимущество алгоритма.

    Проверь себя

    1.

    Сколько сравнений сделает сортировка выбором, если массив из 5 элементов уже отсортирован?

    2.

    Массив [6, 3, 8, 1] сортируют выбором. Какое число будет стоять на последнем месте (индекс 3) после первого шага?

    3.

    Соедини характеристику сортировки выбором и ее значение.

    Сравнений при $n = 5$

    10

    Наибольшее число обменов при $n = 5$

    $O(1)$

    Сложность на уже отсортированном массиве

    4

    Дополнительная память

    $O(n^2)$

    Поможем подобрать обучение

    Оставьте телефон. Мы перезвоним, поможем выбрать подходящие занятия и ответим на вопросы

    Поможем подобрать обучение

    Заявка принята.

    Мы свяжемся с вами