Квадратичные сортировки

3 minute read

Алгоритмы квадратичной сортировки, примеры реализаци и оценка временной сложности.

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

Пожалуй самый очевидный способ сортировки массива — сортировка выбором. Он интуитивно понятен и часто встречается в реальной жизни: находим минимальный элемент, “перекладывем” его в начало, продолжаем, пока массив не будет отсортирован.

Более точно идею сортировки объясняет следующий

Пример

Пусть задан массив

Минимальный элемент в нём: 1, поменяем её с первым элментом массива местами, получаем

Теперь наёдём минимальный элемент в подмассиве , это будет число 3. Поменяем его со вторым элементом массива местами, получаем

Продолжая так далее получим

Оценка сложности

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

Примеры реализации

Пример реализации на языке Python:

A = [6, 5, 3, 7, 8, 1, 9]
for i in range(len(A)-1):
    m = i # Обратите внимание, что мы храним не сам минимум, а индекс минимума
    for j in range(i+1, len(A)):
        if A[j] < A[m]:
            m = j 
    A[i], A[m] = A[m], A[i]
print(A) # [1, 3, 5, 6, 7, 8, 9]

Пример реализации на языке C++:

// Требуется 11 стандарт для такого способа задания вектора
vector<int> A = {6, 5, 3, 7, 8, 1, 9};
for (int i = 0; i < A.size()-1; ++i) {
    int m = i; // Обратите внимание, что мы храним не сам минимум, а индекс минимума
    for (int j = i+1; j < A.size(); ++j)
        if (A[j] < A[m])
            m = j; 
    swap(A[i], A[m]);
}
// Требуется 11 стандарт для такого способа обхода вектора
for (auto &i : A)
    cout << i << " "; // 1 3 5 6 7 8 9 

Сортировка методом простого обмена aka “Пузырёк”

Заметим, что в отсортированном массиве все пары соседних элементов упорядочены. На этой идее основана сортировка методом простого обмена. Будем сравнивать пары соседних элеметов, если в какой-то момент упорядоченность будет нарушена — просто поменяем элементы местами.

Пример

Пусть задан массив

Сравниваем 6 и 5, 6 больше 5, следовательно порядок нарушается — меняем элементы местами

Переходим к следующей паре 6 и 3. Порядок снова нарушен — переставляем

В следующей паре 6 и 7 элементы упорядочены, просто переходим дальше, не изменяя массив

Пара 7 и 8 упорядочена — идём дальше

В паре 8 и 1 порядок снова нарушен — меняем местами

Легко заметить, что после прохода по массиву максимальный элемент занимает своё место. Поэтому эту сортировку также называют “метод пузырька” — максимальные элементы “всплывают” к верху массива, как пузырьки в воде.

Оценка сложности

Легко заметить, что для того, чтобы упорядочить весь массив нам потребуется ровно шаг. На первом шаге производится проверка, на втором шаге проверки, итд. Очевидно, что количество действий будет равно , т.е. снова получается квадратичная зависимость времени работы алгоритма от объема входных данных.

Примеры реализации

Пример реализации на языке Python:

A = [6, 5, 3, 7, 8, 1]
for i in range(len(A)-1):
    for j in range(len(A) - i - 1):
        if A[j] > A[j+1]:
            A[j], A[j+1] = A[j+1], A[j]
print(A) # [1, 3, 5, 6, 7, 8]

Пример реализации на языке C++:

// Требуется 11 стандарт для такого способа задания вектора
vector<int> A = {6, 5, 3, 7, 8, 1};
for (int i = 0; i < A.size()-1; ++i) {
    for (int j = 0; j < A.size() - i - 1; ++j)
        if (A[j] > A[j+1])
            swap(A[j], A[j+1]);
}
// Требуется 11 стандарт для такого способа обхода вектора
for (auto &i : A)
    cout << i << " "; // 1 3 5 6 7 8

Leave a Comment

Your email address will not be published. Required fields are marked *

Loading...