C++.Алгоритмы сортировок
https://t.me/HotCheatSheet
Всех приветствую! Сегодня к вашему вниманию представляю статью по алгоритмам сортировки на C++. Ничего лишнего, только реализация и небольшое описание, а ещё сделал содержание для удобства =)
Реализация алгоритмов сортировки на c++
Содержание
- Сортировка пузырьком
- Шейкерная сортировка
- Сортировка расческой
- Сортировка вставками
- Сортировка Шелла
- Сортировка деревом
- Гномья сортировка
- Сортировка выбором
- Пирамидальная сортировка
- Быстрая сортировка
- Сортировка слиянием
- Сортировка подсчетом
- Блочная сортировка
- Поразрядная сортировка
- Битонная сортировка
- Timsort
Сортировка пузырьком
(Bubble sort)
Простой алгоритм сортировки. Для понимания и реализации этот алгоритм - простейший, но эффективен он лишь для небольших массивов.
Для каждой пары индексов производится обмен, если элементы расположены не по порядку.
void bubblesort(int* l, int* r) {
int sz = r - l;
if (sz <= 1) return;
bool b = true;
while (b) {
b = false;
for (int* i = l; i + 1 < r; i++) {
if (*i > *(i + 1)) {
swap(*i, *(i + 1));
b = true;
}
}
r--;
}
}
Шейкерная сортировка
(Shaker sort)
Разновидность пузырьковой сортировки.
void shakersort(int* l, int* r) {
int sz = r - l;
if (sz <= 1) return;
bool b = true;
int* beg = l - 1;
int* end = r - 1;
while (b) {
b = false;
beg++;
for (int* i = beg; i < end; i++) {
if (*i > *(i + 1)) {
swap(*i, *(i + 1));
b = true;
}
}
if (!b) break;
end--;
for (int* i = end; i > beg; i--) {
if (*i < *(i - 1)) {
swap(*i, *(i - 1));
b = true;
}
}
}
}
Сортировка расческой
(Comb sort)
Это довольно упрощённый алгоритм сортировки, изначально спроектированный Влодзимежом Добосевичем в 1980 г. Сортировка расчёской улучшает сортировку пузырьком, и конкурирует с алгоритмами, подобными быстрой сортировке.
Улучшение сортировки пузырьком.
void combsort(int* l, int* r) {
int sz = r - l;
if (sz <= 1) return;
double k = 1.2473309;
int step = sz - 1;
while (step > 1) {
for (int* i = l; i + step < r; i++) {
if (*i > *(i + step))
swap(*i, *(i + step));
}
step /= k;
}
bool b = true;
while (b) {
b = false;
for (int* i = l; i + 1 < r; i++) {
if (*i > *(i + 1)) {
swap(*i, *(i + 1));
b = true;
}
}
}
}
Сортировка вставками
(Insertion sort)
Алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.
Определяем, где текущий элемент должен находиться в упорядоченном списке, и вставляем его туда.
void insertionsort(int* l, int* r) {
for (int *i = l + 1; i < r; i++) {
int* j = i;
while (j > l && *(j - 1) > *j) {
swap(*(j - 1), *j);
j--;
}
}
}
Сортировка Шелла
(Shellsort)
Алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками.
int increment(long inc[], long size)
{
int p1, p2, p3, s;
p1 = p2 = p3 = 1;
s = -1;
do
{
if (++s % 2)
{
inc[s] = 8*p1 - 6*p2 + 1;
}
else
{
inc[s] = 9*p1 - 9*p3 + 1;
p2 *= 2;
p3 *= 2;
}
p1 *= 2;
}
while(3*inc[s] < size);
return s > 0 ? --s : 0;
}
template< class T >
void shellSort(T a[], long size)
{
long inc, i, j, seq[40];
int s;
s = increment(seq, size);
while (s >= 0)
{
inc = seq[s--];
for (i = inc; i < size; ++i)
{
T temp = a[i];
for (j = i; (j >= inc) && (temp < a[j-inc]); j -= inc) {
a[j] = a[j - inc];
}
a[j] = temp;
}
}
}
Сортировка деревом
(Tree sort)
Универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей.
void treesort(int* l, int* r) {
multiset<int> m;
for (int *i = l; i < r; i++)
m.insert(*i);
for (int q : m)
*l = q, l++;
}
Гномья сортировка
(Gnome sort)
Алгоритм сортировки, похожий на сортировку вставками, но в отличие от последней перед вставкой на нужное место происходит серия обменов, как в сортировке пузырьком.
void gnomesort(int* l, int* r) {
int *i = l;
while (i < r) {
if (i == l || *(i - 1) <= *i) i++;
else swap(*(i - 1), *i), i--;
}
}
Сортировка выбором
(Selection sort)
Алгоритм сортировки.
Поиск наименьшего или наибольшего элемента и помещение его в начало или конец упорядоченного списка.
void selectionsort(int* l, int* r) {
for (int *i = l; i < r; i++) {
int minz = *i, *ind = i;
for (int *j = i + 1; j < r; j++) {
if (*j < minz) minz = *j, ind = j;
}
swap(*i, *ind);
}
}
Пирамидальная сортировка
(Heapsort)
Алгоритм сортировки.
Превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка.
template <class T>
class heap {
public:
int size() {
return n;
}
int top() {
return h[0];
}
bool empty() {
return n == 0;
}
void push(T a) {
h.push_back(a);
SiftUp(n);
n++;
}
void pop() {
n--;
swap(h[n], h[0]);
h.pop_back();
SiftDown(0);
}
void clear() {
h.clear();
n = 0;
}
T operator [] (int a) {
return h[a];
}
private:
vector<T> h;
int n = 0;
void SiftUp(int a) {
while (a) {
int p = (a - 1) / 2;
if (h[p] > h[a]) swap(h[p], h[a]);
else break;
a--; a /= 2;
}
}
void SiftDown(int a) {
while (2 * a + 1 < n) {
int l = 2 * a + 1, r = 2 * a + 2;
if (r == n) {
if (h[l] < h[a]) swap(h[l], h[a]);
break;
}
else if (h[l] <= h[r]) {
if (h[l] < h[a]) {
swap(h[l], h[a]);
a = l;
}
else break;
}
else if (h[r] < h[a]) {
swap(h[r], h[a]);
a = r;
}
else break;
}
}
};
void heapsort(int* l, int* r) {
heap<int> h;
for (int *i = l; i < r; i++) h.push(*i);
for (int *i = l; i < r; i++) {
*i = h.top();
h.pop();
}
}
Быстрая сортировка
(Quicksort)
Широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.
Широко известен как быстрейший из известных для упорядочения больших случайных списков, с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины, затем алгоритм применяется рекурсивно к каждой половине.
void quicksort(int* l, int* r) {
if (r - l <= 1) return;
int z = *(l + (r - l) / 2);
int* ll = l, *rr = r - 1;
while (ll <= rr) {
while (*ll < z) ll++;
while (*rr > z) rr--;
if (ll <= rr) {
swap(*ll, *rr);
ll++;
rr--;
}
}
if (l < rr) quicksort(l, rr + 1);
if (ll < r) quicksort(ll, r);
}
void quickinssort(int* l, int* r) {
if (r - l <= 32) {
insertionsort(l, r);
return;
}
int z = *(l + (r - l) / 2);
int* ll = l, *rr = r - 1;
while (ll <= rr) {
while (*ll < z) ll++;
while (*rr > z) rr--;
if (ll <= rr) {
swap(*ll, *rr);
ll++;
rr--;
}
}
if (l < rr) quickinssort(l, rr + 1);
if (ll < r) quickinssort(ll, r);
}
Сортировка слиянием
(Merge sort)
Алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке.
Выстраиваем первую и вторую половину списка отдельно, а затем объединяем упорядоченные списки.
void merge(int* l, int* m, int* r, int* temp) {
int *cl = l, *cr = m, cur = 0;
while (cl < m && cr < r) {
if (*cl < *cr) temp[cur++] = *cl, cl++;
else temp[cur++] = *cr, cr++;
}
while (cl < m) temp[cur++] = *cl, cl++;
while (cr < r) temp[cur++] = *cr, cr++;
cur = 0;
for (int* i = l; i < r; i++)
*i = temp[cur++];
}
void _mergesort(int* l, int* r, int* temp) {
if (r - l <= 1) return;
int *m = l + (r - l) / 2;
_mergesort(l, m, temp);
_mergesort(m, r, temp);
merge(l, m, r, temp);
}
void mergesort(int* l, int* r) {
int* temp = new int[r - l];
_mergesort(l, r, temp);
delete temp;
}
void _mergeinssort(int* l, int* r, int* temp) {
if (r - l <= 32) {
insertionsort(l, r);
return;
}
int *m = l + (r - l) / 2;
_mergeinssort(l, m, temp);
_mergeinssort(m, r, temp);
merge(l, m, r, temp);
}
void mergeinssort(int* l, int* r) {
int* temp = new int[r - l];
_mergeinssort(l, r, temp);
delete temp;
}
Сортировка подсчетом
(Counting sort)
Алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов.
void counting_sort (int *vec, int len, int min, int max) {
int *cnt = new int[max-min+1];
for(int i = min; i <= max; ++i) cnt[i - min] = 0;
for(int i = 0; i < len; ++i) ++cnt[vec[i] - min];
for(int i = min; i <= max; ++i)
for(int j = cnt[i - min]; j--;)
*vec++ = i;
}
Блочная сортировка
(Bucket sort)
Алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим.
void _newbucketsort(int* l, int* r, int* temp) {
if (r - l <= 64) {
insertionsort(l, r);
return;
}
int minz = *l, maxz = *l;
bool is_sorted = true;
for (int *i = l + 1; i < r; i++) {
minz = min(minz, *i);
maxz = max(maxz, *i);
if (*i < *(i - 1)) is_sorted = false;
}
if (is_sorted) return;
int diff = maxz - minz + 1;
int numbuckets;
if (r - l <= 1e7) numbuckets = 1500;
else numbuckets = 3000;
int range = (diff + numbuckets - 1) / numbuckets;
int* cnt = new int[numbuckets + 1];
for (int i = 0; i <= numbuckets; i++)
cnt[i] = 0;
int cur = 0;
for (int* i = l; i < r; i++) {
temp[cur++] = *i;
int ind = (*i - minz) / range;
cnt[ind + 1]++;
}
int sz = 0;
for (int i = 1; i <= numbuckets; i++)
if (cnt[i]) sz++;
int* run = new int[sz];
cur = 0;
for (int i = 1; i <= numbuckets; i++)
if (cnt[i]) run[cur++] = i - 1;
for (int i = 1; i <= numbuckets; i++)
cnt[i] += cnt[i - 1];
cur = 0;
for (int *i = l; i < r; i++) {
int ind = (temp[cur] - minz) / range;
*(l + cnt[ind]) = temp[cur];
cur++;
cnt[ind]++;
}
for (int i = 0; i < sz; i++) {
int r = run[i];
if (r != 0) _newbucketsort(l + cnt[r - 1], l + cnt[r], temp);
else _newbucketsort(l, l + cnt[r], temp);
}
delete run;
delete cnt;
}
void newbucketsort(int* l, int* r) {
int *temp = new int[r - l];
_newbucketsort(l, r, temp);
delete temp;
}
Поразрядная сортировка
(Radix sort)
Это не сравнительный целочисленный алгоритм сортировки, который сортирует данные с помощью целых ключей, группируя ключи по отдельным цифрам, которые имеют одинаковую значимую позицию и значение.
Есть 2 вида подразрядной сортировки:
LSD (least significant digit)
int digit(int n, int k, int N, int M) {
return (n >> (N * k) & (M - 1));
}
void _radixsort(int* l, int* r, int N) {
int k = (32 + N - 1) / N;
int M = 1 << N;
int sz = r - l;
int* b = new int[sz];
int* c = new int[M];
for (int i = 0; i < k; i++) {
for (int j = 0; j < M; j++)
c[j] = 0;
for (int* j = l; j < r; j++)
c[digit(*j, i, N, M)]++;
for (int j = 1; j < M; j++)
c[j] += c[j - 1];
for (int* j = r - 1; j >= l; j--)
b[--c[digit(*j, i, N, M)]] = *j;
int cur = 0;
for (int* j = l; j < r; j++)
*j = b[cur++];
}
delete b;
delete c;
}
void radixsort(int* l, int* r) {
_radixsort(l, r, 8);
}
MSD (most significant digit)
void _radixsortmsd(int* l, int* r, int N, int d, int* temp) {
if (d == -1) return;
if (r - l <= 32) {
insertionsort(l, r);
return;
}
int M = 1 << N;
int* cnt = new int[M + 1];
for (int i = 0; i <= M; i++)
cnt[i] = 0;
int cur = 0;
for (int* i = l; i < r; i++) {
temp[cur++] = *i;
cnt[digit(*i, d, N, M) + 1]++;
}
int sz = 0;
for (int i = 1; i <= M; i++)
if (cnt[i]) sz++;
int* run = new int[sz];
cur = 0;
for (int i = 1; i <= M; i++)
if (cnt[i]) run[cur++] = i - 1;
for (int i = 1; i <= M; i++)
cnt[i] += cnt[i - 1];
cur = 0;
for (int *i = l; i < r; i++) {
int ind = digit(temp[cur], d, N, M);
*(l + cnt[ind]) = temp[cur];
cur++;
cnt[ind]++;
}
for (int i = 0; i < sz; i++) {
int r = run[i];
if (r != 0) _radixsortmsd(l + cnt[r - 1], l + cnt[r], N, d - 1, temp);
else _radixsortmsd(l, l + cnt[r], N, d - 1, temp);
}
delete run;
delete cnt;
}
void radixsortmsd(int* l, int* r) {
int* temp = new int[r - l];
_radixsortmsd(l, r, 8, 3, temp);
delete temp;
}
Битонная сортировка
(Bitonic sort)
Параллельный алгоритм сортировки данных, метод для создания сортировочной сети.
void bitseqsort(int* l, int* r, bool inv) {
if (r - l <= 1) return;
int *m = l + (r - l) / 2;
for (int *i = l, *j = m; i < m && j < r; i++, j++) {
if (inv ^ (*i > *j)) swap(*i, *j);
}
bitseqsort(l, m, inv);
bitseqsort(m, r, inv);
}
void makebitonic(int* l, int* r) {
if (r - l <= 1) return;
int *m = l + (r - l) / 2;
makebitonic(l, m);
bitseqsort(l, m, 0);
makebitonic(m, r);
bitseqsort(m, r, 1);
}
void bitonicsort(int* l, int* r) {
int n = 1;
int inf = *max_element(l, r) + 1;
while (n < r - l) n *= 2;
int* a = new int[n];
int cur = 0;
for (int *i = l; i < r; i++)
a[cur++] = *i;
while (cur < n) a[cur++] = inf;
makebitonic(a, a + n);
bitseqsort(a, a + n, 0);
cur = 0;
for (int *i = l; i < r; i++)
*i = a[cur++];
delete a;
}
Timsort
Гибридный алгоритм сортировки, сочетающий сортировку вставками и сортировку слиянием, опубликованный в 2002 году Тимом Петерсом.
void _timsort(int* l, int* r, int* temp) {
int sz = r - l;
if (sz <= 64) {
insertionsort(l, r);
return;
}
int minrun = sz, f = 0;
while (minrun >= 64) {
f |= minrun & 1;
minrun >>= 1;
}
minrun += f;
int* cur = l;
stack<pair<int, int*>> s;
while (cur < r) {
int* c1 = cur;
while (c1 < r - 1 && *c1 <= *(c1 + 1)) c1++;
int* c2 = cur;
while (c2 < r - 1 && *c2 >= *(c2 + 1)) c2++;
if (c1 >= c2) {
c1 = max(c1, cur + minrun - 1);
c1 = min(c1, r - 1);
insertionsort(cur, c1 + 1);
s.push({ c1 - cur + 1, cur });
cur = c1 + 1;
}
else {
c2 = max(c2, cur + minrun - 1);
c2 = min(c2, r - 1);
reverse(cur, c2 + 1);
insertionsort(cur, c2 + 1);
s.push({ c2 - cur + 1, cur });
cur = c2 + 1;
}
while (s.size() >= 3) {
pair<int, int*> x = s.top();
s.pop();
pair<int, int*> y = s.top();
s.pop();
pair<int, int*> z = s.top();
s.pop();
if (z.first >= x.first + y.first && y.first >= x.first) {
s.push(z);
s.push(y);
s.push(x);
break;
}
else if (z.first >= x.first + y.first) {
merge(y.second, x.second, x.second + x.first, temp);
s.push(z);
s.push({ x.first + y.first, y.second });
}
else {
merge(z.second, y.second, y.second + y.first, temp);
s.push({ z.first + y.first, z.second });
s.push(x);
}
}
}
while (s.size() != 1) {
pair<int, int*> x = s.top();
s.pop();
pair<int, int*> y = s.top();
s.pop();
if (x.second < y.second) swap(x, y);
merge(y.second, x.second, x.second + x.first, temp);
s.push({ y.first + x.first, y.second });
}
}
void timsort(int* l, int* r) {
int* temp = new int[r - l];
_timsort(l, r, temp);
delete temp;
}