C++.Алгоритмы сортировок

C++.Алгоритмы сортировок

https://t.me/HotCheatSheet

Всех приветствую! Сегодня к вашему вниманию представляю статью по алгоритмам сортировки на C++. Ничего лишнего, только реализация и небольшое описание, а ещё сделал содержание для удобства =)


Реализация алгоритмов сортировки на c++

Содержание

  1. Сортировка пузырьком
  2. Шейкерная сортировка
  3. Сортировка расческой
  4. Сортировка вставками
  5. Сортировка Шелла
  6. Сортировка деревом
  7. Гномья сортировка
  8. Сортировка выбором
  9. Пирамидальная сортировка
  10. Быстрая сортировка
  11. Сортировка слиянием
  12. Сортировка подсчетом
  13. Блочная сортировка
  14. Поразрядная сортировка
  15. Битонная сортировка
  16. 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;
}