ζ༼Ɵ͆ل͜Ɵ͆༽ᶘ

Сортировка массивов

0 комментов
24.05.2020
5 мин чтения

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


Сортировка пузырьком

Сортировка пузырьком – это самая простая сортировка массива. Каким же образом она выполняться? Возьмем массив из 5 чисел, например, 58193. Пойдем от самого первого элемента до предпоследнего. В коде это переменная i в цикле for. Мы идем до предпоследней ячейки, чтобы не возникло ошибки, когда мы будем сравнивать 4 элемент (предпоследний), с 5 (последним). Пойдем от самой первой ячейки. Программа сравнивает «5» и «8». Пять больше восьми – нет, значит идем дальше. Сравниваем теперь «8» и «3». Восемь больше трех – да, тогда меняем их местами. После первого цикла for, в котором инкремеруется переменная i, получаем следующий массив: 51839. Он еще не отсортирован, но самый «тяжелый» элемент – девятка, как бы «всплыла наверх». Теперь нам нет смысла сравнивать последний элемент массива, и считываем теперь только до 3 элемента. В итоге у нас получиться отсортированный массив – 13589.

#include <iostream>
using namespace std;

int main()
{
    setlocale(LC_ALL, "Russian");
    int n, tmp;
    int arr[100];
    cout << "Введите размерность массива ";
    cin >> n;
    cout << "Введите элементы массива ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    for (int i = 0; i < n - 1; i++) { //перебираем элементы массива
        for (int j = 0; j < n - (i + 1); j++) {
            if (arr[j] > arr[j + 1]) { //если текущий элемент больше следуещего, то меняем местами
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
    cout << "Отсортированный массив ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    return 1;
}

Улучшенная сортировка пузырьком

Можно заметить, что алгоритм обычного метода пузырька, может заново прогонять и проверять уже отсортированный массив. Например, последовательность чисел 28356 отсортируется всего за один цикл. Так зачем же нам еще раз его поверять. С этой целью поставим флажок, который будет об этом сигнализировать.

#include <iostream>
using namespace std;

int main()
{
    setlocale(LC_ALL, "Russian");
    int n, tmp;
    int arr[100];
    cout << "Введите размерность массива ";
    cin >> n;
    cout << "Введите элементы массива ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int up = n;
    bool f = true; //флажок
    while (f == true) { //если флажок равен 0, то массив отсортирован, и останавливаем цикл
        f = false;
        for (int i = 0; i < up - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                f = true;
                tmp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tmp;
            }
        }
        up = up - 1;
    }
    cout << "Отсортированный массив ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    return 1;
}

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

Тут уже более сложный алгоритм. Этот метод находит минимальный элемент и выстраивает его по порядку. Рассмотрим пример. Нам дан массив 58193. Сначала обозначим за минимальный элемент самый первый – пятерку, и запишем индекс этого элемента. Сравним этот элемент со следующим. Если следующий элемент меньше минимума (мы записали число 5, как минимальное), то перезаписываем переменную min и imin. После того как программа нашла минимальный элемент, мы сравниваем его индекс с текущем значением переменной i (в начале цикла эти два значения совпадали). Если они не совпали, то меняем местами. После первого цикла, массив примет следующий вид: 18593.

#include <iostream>
using namespace std;

int main()
{
    setlocale(LC_ALL, "Russian");
    int n, tmp, min, imin;
    int arr[100];
    cout << "Введите размерность массива ";
    cin >> n;
    cout << "Введите элементы массива ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    for (int i = 0; i < n - 1; i++) {
        min = arr[i];
        imin = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < min) {
                min = arr[j];
                imin = j;
            }
        }
        if (i != imin) { //если не сошлось меняем местами
            tmp = arr[i];
            arr[i] = arr[imin];
            arr[imin] = tmp;
        }
    }
    cout << "Отсортированный массив ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    return 1;
}

Сортировка вставкой

Этот способ самый рациональный. Он вставляет число СРАЗУ в нужное место. Рассмотрим опять на примере массива с числами 58193. Счетчик i берем на одну единицу больше, чтобы затем можно было сравнить с соседним числом. Первые 2 цикла можно пропустить, так как числа «5» и «8» стоят уже в правильном порядке. Мы будем «переставлять» число до тех пор, пока оно не будет нарушать условия цикла while: переменная j будет больше 1 (в коде с нуля, т.к. отсчет массива с нуля, но для простоты возьмем единицу), и пока ячейка в массиве и индексом j будет больше текущего значение с индексом i. Массив будет меняться следующим образом: 58193 58893 55893 15893. И так единица «пришла» в свою точку. Дальше точно так же до последнего элемента. Этот способ сортировки самый сложный для понимания, но зато самый рациональный.

#include <iostream>
using namespace std;

int main()
{
    setlocale(LC_ALL, "Russian");
    int n, j, tmp;
    int arr[100];
    cout << "Введите размерность массива ";
    cin >> n;
    cout << "Введите элементы массива ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    for (int i = 1; i < n; i++) {
        tmp = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > tmp) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        if (j + 1 != i) {
            arr[j + 1] = tmp;
        }
    }
    cout << "Отсортированный массив ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
    return 1;
}

Сравнение алгоритмов

В каждый алгоритм я вставил по два счетчика. Первый считает количество перестановок (выполнение операции if), второй – количество циклов for или while.

На каждом алгоритме я проверил 4 последовательности чисел, которые представлены ниже

На 10 элементов: 11 6 9 7 14 8 2 13 16 0

На 25 элементов: 8 34 10 29 23 20 38 31 36 13 25 13 19 19 1 21 12 25 16 9 12 16 28 6 36

На 50 элементов: 48 1 34 7 27 34 19 54 24 6 52 25 52 11 9 31 7 3 42 8 19 4 39 41 51 32 11 10 1 57 39 33 6 29 53 3 18 31 24 4 38 39 18 46 0 34 29 40 21 0

На 100 элементов: 9 20 72 13 52 29 31 58 111 78 85 20 64 96 64 94 100 38 91 0 51 63 14 5 17 18 71 88 8 45 53 86 84 44 97 64 28 38 79 71 46 25 25 33 58 76 81 36 11 107 107 69 78 88 92 66 6 66 115 33 77 62 49 65 25 118 55 20 119 0 65 62 79 20 73 25 37 100 67 61 57 35 76 21 58 104 7 116 71 30 57 81 42 46 113 104 96 79 8 59

Все результаты я внес в таблицу Excel и получил следующие результаты:

Из полученных данных можно сделать следующие выводы:

+Алгоритм методом Пузырька самый легкий, но он дольше всех работает. +Улучшенный алгоритм пузырька немного получше своего родителя, но не самый оптимальный +Сортировка методом выбора уже более рационален, чем предыдущие. В нем гораздо меньше используется перестановок в массиве. +И победителем стал алгоритм сортировки методом вставки. В нем меньше всего и циклов, и операций перестановки.


Заключение

Самым простым и невыгодным оказалась сортировка Пузырьком, а самым рациональным – сортировка Вставкой.

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

3
Сегодня
День улёта