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; }