§ 3. Сортировка массива


3.1 Сортировка. Разновидности сортировки

Сортировка – это важнейших процесс упорядочивания данных по определенному признаку. Важность данного процесса заключается в том, что только на упорядоченных (отсортированных) данных можно выполнять другой важный процесс – поиск информации. На упорядоченных данных можно решать и множество других задач наиболее эффективным способом. Существует несколько разновидностей сортировки:

  1. По возрастанию (сортировка от меньшего к большему)
  2. По неубыванию (тоже, но в последовательности встречаются равные по значению элементы)
  3. По убыванию (сортировка от большего к меньшему)
  4. По невозрастанию (тоже, но в последовательности встречаются равные по значению элементы)

Существует большое множество алгоритмов сортировки, которые обладают различной эффективностью. В программировании эффективность алгоритма характеризует “сложность” алгоритма.

3.2 Сложность алгоритма

Вычислительная сложность алгоритма – это функция зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Временная сложность алгоритма обычно выражается с использованием «O»-нотации.
Говорят, что алгоритм является алгоритмом константного времени (обозначается – O(1)), если время его выполнения не зависит от размера входа. Например, получение одного элемента в массиве занимает константное время, поскольку выполняется за одну команду. Если осуществляется нахождение минимального значения в неотсортированном массиве, то такая операция занимает линейное время, (обозначается – O(n)), поскольку мы должны просмотреть каждый элемент массива. Здесь n – размер массива. Алгоритмы сортировок, основанные на сравнениях, имеют квадратичную временную сложность (обозначается – O(n2)). Наиболее эффективные алгоритмы сортировки, такие как “быстрая сортировка”, “сортировка кучей”, “сортировка слиянием”, имеют “линейно-логарифмическую” сложность, обозначается – O(n log(n)). Такие алгоритмы работают значительно эффективнее квадратичных, но более сложны в своей разработке.

3.3 Пузырьковая сортировка

Пузырьковая сортировка – это квадратичная сортировка, которая получила свое название от аналогии поднятия пузырька воздуха в жидкости. Минимальный элемент, как пузырек, вытесняется к началу (или к концу, в зависимости от направления сортировки) массива. Это наиболее простой алгоритм для понимания и реализации. Реализуется алгоритм следующим образом:

  • Организуется структура вложенных циклов. Внешний цикл нужен для ограничения области просмотра вложенного цикла. Он также определяет и количество шагов вложенного цикла.
  • Во вложенном цикле в условной инструкции осуществляется сравнение двух соседних элементов. Если элемент слева больше элемента справа, то они меняются местами.
  • Чтобы изменить направление сортировки необходимо поменять операцию сравнения в условной инструкции.
Программа 9.3.1 Пузырьковая сортировка
#include <iostream>
#include <array>
#include <cstdlib>
#include <ctime>

using namespace std;

int main() {
    srand(time(0));
    const int n = 100;
    array<int , n> ar;
    for (int i = 0; i < n; i++) {
        ar[i] = 10 + rand() % 90;
        cout << ar[i] << " ";
    }
    cout << endl;
//======== Пузырьковая сортировка =========//
    for (int i = 0; i < n - 2; i++)
        for (int j = 0; j < n - i - 1; j++)
            if (ar[j] > ar[j + 1]) {
                int buf = ar[j];
                ar[j] = ar[j + 1];
                ar[j + 1] = buf;
             }
//========================================//
    for (int i = 0; i < n; i++)
        cout << ar[i] << " ";
    return 0;
}

Если в данную программу добавить вывод содержимого массива по каждой итерации то можно получить визуальное представление работы пузырьковой сортировки. Для 10 элементов возможный вывод может выглядеть следующим образом:

Проход 1
11 92 97 34 90 85 88 80 82 26 
11 92 97 34 90 85 88 80 82 26 
11 92 34 97 90 85 88 80 82 26 
11 92 34 90 97 85 88 80 82 26 
11 92 34 90 85 97 88 80 82 26 
11 92 34 90 85 88 97 80 82 26 
11 92 34 90 85 88 80 97 82 26 
11 92 34 90 85 88 80 82 97 26 
11 92 34 90 85 88 80 82 26 97 

Проход 2
11 92 34 90 85 88 80 82 26 97 
11 34 92 90 85 88 80 82 26 97 
11 34 90 92 85 88 80 82 26 97 
11 34 90 85 92 88 80 82 26 97 
11 34 90 85 88 92 80 82 26 97 
11 34 90 85 88 80 92 82 26 97 
11 34 90 85 88 80 82 92 26 97 
11 34 90 85 88 80 82 26 92 97 

Проход 3
11 34 90 85 88 80 82 26 92 97 
11 34 90 85 88 80 82 26 92 97 
11 34 85 90 88 80 82 26 92 97 
11 34 85 88 90 80 82 26 92 97 
11 34 85 88 80 90 82 26 92 97 
11 34 85 88 80 82 90 26 92 97 
11 34 85 88 80 82 26 90 92 97 

Проход 4
11 34 85 88 80 82 26 90 92 97 
11 34 85 88 80 82 26 90 92 97 
11 34 85 88 80 82 26 90 92 97 
11 34 85 80 88 82 26 90 92 97 
11 34 85 80 82 88 26 90 92 97 
11 34 85 80 82 26 88 90 92 97 

Проход 5
11 34 85 80 82 26 88 90 92 97 
11 34 85 80 82 26 88 90 92 97 
11 34 80 85 82 26 88 90 92 97 
11 34 80 82 85 26 88 90 92 97 
11 34 80 82 26 85 88 90 92 97 

Проход 6
11 34 80 82 26 85 88 90 92 97 
11 34 80 82 26 85 88 90 92 97 
11 34 80 82 26 85 88 90 92 97 
11 34 80 26 82 85 88 90 92 97 

Проход 7
11 34 80 26 82 85 88 90 92 97 
11 34 80 26 82 85 88 90 92 97 
11 34 26 80 82 85 88 90 92 97 

Проход 8
11 34 26 80 82 85 88 90 92 97 
11 26 34 80 82 85 88 90 92 97 

Количество сравнений в данном алгоритме равно: \frac{n(n-1)}{2}. Отсюда, временная сложность алгоритма будет оцениваться как O(n2)

Далее следует материал для углубленного изучения. На базовом уровне может быть пропущен.

3.4 Функция sort()

Алгоритм пузырьковой сортировки приведен выше только для обучающих целей. В реальных проектах использовать его нельзя, так как он не является эффективным. Особенно это становится заметным на количестве элементов более 1000. Стандартная библиотека C++ содержит эффективный алгоритм сортировки sort(), который будет доступен, если включить заголовочный файл algorithm. Аргументами функции sort() являются итераторы. Чтобы упорядочить только какую-то часть массива можно сместить итератор начала на определенную позицию вправо (или итератор конца – влево). В программе ниже, с помощью функции sort(), сортируется только вторая половина массива.

Программа 9.3.2
#include <iostream>
#include <array>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

int main() {
    srand(time(0));
    const int n = 20;
    array<int , n> ar;
    for (int i = 0; i < n; i++) {
        ar[i] = 10 + rand() % 90;
        cout << ar[i] << " ";
     }
     auto first = begin(ar);
     auto last  = end(ar);
     sort(first + n / 2, last);
     cout << endl;
     for (int i = 0; i < n; i++)
         cout << ar[i] << " ";
    return 0;
}

Возможный вывод

78 72 47 31 86 63 68 48 31 60 44 13 13 55 31 57 87 44 10 63 
78 72 47 31 86 63 68 48 31 60 10 13 13 31 44 44 55 57 63 87
Примеры решения задач
Вопросы
Темы сообщений
Задания А
Задания Б
Задания С
Ссылки
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (1 оценок, среднее: 5,00 из 5)
Загрузка...

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.


Обсуждение закрыто.