Сортировки

Подробное сравнение сортировок на большом числе элементов можно найти тут
https://habr.com/ru/post/335920/

Рекурсия
Рекурсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя.

In [1]:
#include<vector>
#include<iostream>
using namespace std;
setlocale(LC_ALL, "Rus");

Создание массива для сортировки.
По умолчанию, создадим массив из $N$ элементов, размеры которых не превыщают $N-1$.
В данных примерах $N = 10$;

In [2]:
// создадим массив
int n = 10;
    
int *A = new int[n];
cout << "Исходный массив: ";
for (int i = 0; i < 10; i++)
{
    A[i] = rand() % 10;
    cout << A[i] << " ";
}
cout<<endl;
cout<<"-------------------------"<<endl;
Исходный массив: 5 4 2 9 8 6 5 8 7 6 
-------------------------

Вывод
Функция для печати массива

In [3]:
void Print(int *myArr, int n)
{
    for (int i=0; i<n; i++) 
        cout<<myArr[i]<<" "; //вывод массива
}

Быстрая сортировка (Разделяй и Властвуй)

Сортировка заключается в выборе какого-то элемента, из массива(вектора,строки). все элементы, которые меньше, располагаем слева, остальные - справа.  
Потом делим исходный массив пополам и повторяем действия на половинках итд.  

Идея
Алгоритм состоит из трёх шагов:

1. Выбрать элемент из массива. Назовём его опорным(pivot).
2. Разбиение: перераспределение элементов в массиве таким образом, что элементы меньше опорного помещаются перед ним, а больше или равные после.
3. Рекурсивно применить первые два шага к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы.

Сложность алгоритма в лучшем и в среднем случаях $n*log_2(n)$ в худшем случае $O(n^2)$

In [4]:
// мы можем сортировать не весь массив, а только его часть.
int first, last; // начало и конец диапазона сортировки
In [5]:
void quick_sort(int *mas, int first, int last)
{
    int pivot, count;
    int f = first, l = last;
    pivot = mas[(int)((f + l) / 2)]; //вычисление опорного элемента
    do
    {
        while (mas[f] < pivot) f++;
        while (mas[l] > pivot) l--;
        if (f <= l) //перестановка элементов
        {
            count = mas[f];
            mas[f] = mas[l];
            mas[l] = count;
            f++;
            l--;
        }
    } while (f < l);
    if (first < l) 
        quick_sort(mas, first, l);
    if (f < last) 
        quick_sort(mas, f, last);
}

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

Алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.
Идея
В начальный момент отсортированная последовательность пуста. На каждом шаге алгоритма выбирается один из элементов входных данных и помещается на нужную позицию в уже отсортированной последовательности до тех пор, пока набор входных данных не будет исчерпан. В любой момент времени в отсортированной последовательности элементы удовлетворяют требованиям к выходным данным алгоритма.
Данный алгоритм можно ускорить при помощи использования бинарного поиска для нахождения места текущему элементу в отсортированной части. Проблема с долгим сдвигом массива вправо решается при помощи смены указателей.
Сложность алгоритма в худшем и в среднем случаях $O(n^2)$ в лучшем случае $O(n)$

In [6]:
// сортировка вставками
    void insert_sort(int *mas, int n) //сортировка вставками
    {
        for (int i=0; i<n-1; i++)
        {
            int key, temp;
            key=i+1;
            temp=mas[key];
            for (int j=i+1; j>0; j--)
            {
                if (temp<mas[j-1])
                    {
                        mas[j]=mas[j-1];
                        key=j-1;
                    }
            }
            mas[key]=temp;
        }
    
    }

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

Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов.
Идея
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются $N-1$ раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название алгоритма).
Сложность алгоритма: $ O(n^2)$

In [7]:
void BubbleSort(int *mass, int n) //сортировка пузырьком
{
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n-1; j++)
        {
            int key, count;
            key=j+1;
            count=mass[key];
            if (mass[j]>mass[key])
            {
                mass[key]=mass[j];
                mass[j]=count;
            }
        }
    }
}

Сортировка Шейкерная

Сортировка перемешиванием, или Шейкерная сортировка, или двунаправленная (англ. Cocktail sort) — разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки, можно отметить два обстоятельства.
Идея
Если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, её можно исключить из рассмотрения.
При движении от конца массива к началу минимальный элемент «всплывает» на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.
Эти две идеи приводят к следующим модификациям в методе пузырьковой сортировки.
Границы рабочей части массива (то есть части массива, где происходит движение) устанавливаются в месте последнего обмена на каждой итерации. Массив просматривается поочередно справа налево и слева направо.
Сложность
Лучший случай для этой сортировки — отсортированный массив $O(n)$ худший — отсортированный в обратном порядке $O(n^2)$ Наименьшее число сравнений в алгоритме Шейкер-сортировки $C=N-1$ Это соответствует единственному проходу по упорядоченному массиву (лучший случай)

In [8]:
void Swap_elem(int *Mas, int i)
{
    int temp;
    temp = Mas[i];
    Mas[i] = Mas[i-1];
    Mas[i-1] = temp;
}
In [9]:
//функция шейкерной сортировки
void ShakerSort(int *Mas, int start, int n)
{
    int left, right, i;
    left = start;
    right = n-1;
    while (left <= right)
    {
        for (i = right; i >= left; i--)
            if (Mas[i-1] > Mas[i]) 
                Swap_elem(Mas, i);
        left++; // сдвигаем левую границу на следующий элемент
        
        for (i = left; i <= right; i++)
            if (Mas[i-1] > Mas[i]) 
                Swap_elem(Mas, i);
        right--; // сдвигаем правую границу на предыдущий элемент
    }
}

Сортировка Слиянием

Алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке.
Эта сортировка — хороший пример использования принципа «разделяй и властвуй».
Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
Идея
Для решения задачи сортировки эти три этапа выглядят так:

1.Сортируемый массив разбивается на две части примерно одинакового размера;  
2.Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;  
3. Два упорядоченных массива половинного размера соединяются в один.

Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным). Соединение двух упорядоченных массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем два уже отсортированных по возрастанию подмассива. Тогда:
Слияние двух подмассивов в третий результирующий массив.
На каждом шаге мы берём меньший из двух первых элементов подмассивов и записываем его в результирующий массив. Счётчики номеров элементов результирующего массива и подмассива, из которого был взят элемент, увеличиваем на 1.
«Прицепление» остатка: Когда один из подмассивов закончился, мы добавляем все оставшиеся элементы второго подмассива в результирующий массив.
Сложность алгоритма $n*log_2(n)$

In [10]:
void Merge(int *mass, int first, int last)
{
    int middle, start, final, j;
    int *m = new int[100];
    middle = (first+last)/2; //вычисление среднего элемента
    start = first; //начало левой части
    final = middle+1; //начало правой части
    
    for(j = first; j <= last; j++) //выполнять от начала до конца
        if ((start <= middle) && ((final > last) || (mass[start] < mass[final])))
        {
            m[j] = mass[start];
            start++;
        }
        else
        {
            m[j] = mass[final];
            final++;
        }
    
    //возвращение результата в список
    for (j = first; j <= last; j++) 
        mass[j]=m[j];
}
In [11]:
void MergeSort(int *A, int first, int last)
{
    {
        if (first<last)
        {
            MergeSort(A, first, (first+last)/2); //сортировка левой части
            MergeSort(A, (first+last)/2+1, last); //сортировка правой части
            Merge(A, first, last); //слияние двух частей
        }
    }
}

Линейная Сортировка

Идея

сортировка посредством подсчёта — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000.

Предположим, что входной массив состоит из $N$ целых чисел в диапазоне от $0$ до $k-1$ , где $k \in N$ . Далее алгоритм будет обобщён для произвольного целочисленного диапазона.

Существует несколько модификаций сортировки подсчётом, ниже рассмотрены три линейных и одна квадратичная, которая использует другой подход, но имеет то же название.

Алгоритм 1й
Это простейший вариант алгоритма. Создать вспомогательный массив $C[0..k - 1]$, состоящий из нулей, затем последовательно прочитать элементы входного массива $A$, для каждого $A[i]$ увеличить $C[A[i]]$ на единицу Теперь достаточно пройти по массиву $C$, для каждого $ k \in [0,...,k-1]$ в массив $A$ последовательно записать число j $C[j]$ раз.

SimpleCountingSort:
    for i = 0 to k - 1
        C[i] = 0;
    for i = 0 to n - 1
        C[A[i]] = C[A[i]] + 1;
    b = 0;
    for j = 0 to k - 1
        for i = 0 to C[j] - 1
            A[b] = j;
            b = b + 1;

Алгоритм 2й
Этот вариант используется, когда на вход подается массив структур данных,
который следует отсортировать по ключам key.
Нужно создать вспомогательный массив $C[0..k - 1]$,
каждый $C[i]$ в дальнейшем будет содержать список элементов из входного массива.
Затем последовательно прочитать элементы входного массива A, каждый $A[i]$ добавить в список $C[A[i].key]$
В заключении пройти по массиву $C$, для каждого $ j \in [0,...,k-1]$ в массив $A$ последовательно записывать элементы списка $C[j]$. Алгоритм устойчив.

ListCountingSort
    for i = 0 to k - 1
        C[i] = NULL;
    for i = 0 to n - 1
        C[A[i].key].add(A[i]);
    b = 0;
    for j = 0 to k - 1
        p = C[j];
        while p != NULL
            A[b] = p.data;
            p = p.next();
            b = b + 1;

Устойчивый вариант.
В этом варианте помимо входного массива A потребуется два вспомогательных массива — $C[0..k - 1]$ для счётчика и $B[0..n - 1]$ для отсортированного массива.
Сначала следует заполнить массив C нулями, и для каждого $A[i]$ увеличить $C[A[i]]$ на $1$.
Далее подсчитывается количество элементов меньших или равных $k-1$. Для этого каждый $C[j]$, начиная с $C[1]$, увеличивают на $C[j - 1]$. Таким образом в последней ячейке будет находиться количество элементов от $0...k-1$ существующих во входном массиве. На последнем шаге алгоритма читается входной массив с конца, значение $C[A[i]]$ уменьшается на 1 и в каждый $B[C[A[i]]]$ записывается $A[i]$. Алгоритм устойчив.

(Устойчивая (стабильная) сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи.)

StableCountingSort
    for i = 0 to k - 1
        C[i] = 0;
    for i = 0 to n - 1
        C[A[i]] = C[A[i]] + 1;
    for j = 1 to k - 1
        C[j] = C[j] + C[j - 1];
    for i = n - 1 to 0
        C[A[i]] = C[A[i]] - 1;
        B[C[A[i]]] = A[i];

Вывод по линейным сортировкам.
В первых двух алгоритмах первые два цикла работают за $O(n+k)$.
В третьем алгоритме циклы занимают $2* O(n+k)$, что та же линия.

Используемая память в первых двух алгоритмах равна $O(k)$
в третьем - $O(n+k)$

Результаты сортировок

In [12]:
//    QUICK_SORT 
//first = 0; last = A.size()-1;
    quick_sort(A, 0, n-1);
    cout << endl << "Результирующий quck_sort массив: ";
    Print(A,n);
    cout<<endl;
    cout<<"--------------------------------"<<endl;
Результирующий quck_sort массив: 2 4 5 5 6 6 7 8 8 9 
--------------------------------
In [13]:
// INSERT_SORT
// массив и число элементов
insert_sort(A, n);
cout<<endl<<"Результирующий Insert_Sort массив: ";
    Print(A,n);
    cout<< endl;
    cout<<"--------------------------------"<<endl;
Результирующий Insert_Sort массив: 2 4 5 5 6 6 7 8 8 9 
--------------------------------
In [14]:
//BUBBLE_SORT
// массив и число элементов
BubbleSort(A, n);
cout<<endl<<"Результирующий Buble_sort массив: ";
Print(A,n);
cout<< endl;
cout<<"--------------------------------"<<endl;
Результирующий Buble_sort массив: 2 4 5 5 6 6 7 8 8 9 
--------------------------------
In [15]:
// MERGE_SORT
MergeSort(A,0,n-1);
cout<<endl<<"Результирующий Merge_sort массив: ";
Print(A,n);
cout<< endl;
cout<<"--------------------------------"<<endl;
Результирующий Merge_sort массив: 2 4 5 5 6 6 7 8 8 9 
--------------------------------
In [16]:
// SHAKER_SORT
ShakerSort(A,0,n-1);
cout<<endl<<"Результирующий Shaker_sort массив: ";
Print(A,n);
cout<< endl;
cout<<"--------------------------------"<<endl;
Результирующий Shaker_sort массив: 2 4 5 5 6 6 7 8 8 9 
--------------------------------
In [ ]: