Основные виды сортировок и примеры их реализации

На собеседованиях будущим стажёрам-разработчикам дают задания на знание структур данных и алгоритмов — в том числе сортировок. Академия Яндекса и соавтор специализации «Искусство разработки на современном C++» Илья Шишков составили список для подготовки с методами сортировки, примерами их реализации и гифками, чтобы лучше понять, как они работают.

Пузырьковая сортировка и её улучшения

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

Сортировка пузырьком — один из самых известных алгоритмов сортировки. Здесь нужно последовательно сравнивать значения соседних элементов и менять числа местами, если предыдущее оказывается больше последующего. Таким образом элементы с большими значениями оказываются в конце списка, а с меньшими остаются в начале.

Этот алгоритм считается учебным и почти не применяется на практике из-за низкой эффективности: он медленно работает на тестах, в которых маленькие элементы (их называют «черепахами») стоят в конце массива. Однако на нём основаны многие другие методы, например, шейкерная сортировка и сортировка расчёской.

1void BubbleSort(vector<int>& values) {
2  for (size_t idx_i = 0; idx_i + 1 < values.size(); ++idx_i) {
3    for (size_t idx_j = 0; idx_j + 1 < values.size() - idx_i; ++idx_j) {
4      if (values[idx_j + 1] < values[idx_j]) {
5        swap(values[idx_j], values[idx_j + 1]);
6      }
7    }
8  }
9}

Сортировка перемешиванием (шейкерная сортировка)

Шейкерная сортировка отличается от пузырьковой тем, что она двунаправленная: алгоритм перемещается не строго слева направо, а сначала слева направо, затем справа налево.

1void ShakerSort(vector<int>& values) {
2  if (values.empty()) {
3    return;
4  }
5  int left = 0;
6  int right = values.size() - 1;
7  while (left <= right) {
8    for (int i = right; i > left; --i) {
9      if (values[i - 1] > values[i]) {
10        swap(values[i - 1], values[i]);
11      }
12    }
13    ++left;
14    for (int i = left; i < right; ++i) {
15      if (values[i] > values[i + 1]) {
16        swap(values[i], values[i + 1]);
17      }
18    }
19    --right;
20  }
21}

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

Сортировка расчёской — улучшение сортировки пузырьком. Её идея состоит в том, чтобы «устранить» элементы с небольшими значения в конце массива, которые замедляют работу алгоритма. Если при пузырьковой и шейкерной сортировках при переборе массива сравниваются соседние элементы, то при «расчёсывании» сначала берётся достаточно большое расстояние между сравниваемыми значениями, а потом оно сужается вплоть до минимального.

Первоначальный разрыв нужно выбирать не случайным образом, а с учётом специальной величины — фактора уменьшения, оптимальное значение которого равно 1,247. Сначала расстояние между элементами будет равняться размеру массива, поделённому на 1,247; на каждом последующем шаге расстояние будет снова делиться на фактор уменьшения — и так до окончания работы алгоритма.

1void CombSort(vector<int>& values) {
2  const double factor = 1.247; // Фактор уменьшения
3  double step = values.size() - 1;
4
5  while (step >= 1) {
6    for (int i = 0; i + step < values.size(); ++i) {
7      if (values[i] > values[i + step]) {
8        swap(values[i], values[i + step]);
9      }
10    }
11    step /= factor;
12  }
13  // сортировка пузырьком
14  for (size_t idx_i = 0; idx_i + 1 < values.size(); ++idx_i) {
15    for (size_t idx_j = 0; idx_j + 1 < values.size() - idx_i; ++idx_j) {
16      if (values[idx_j + 1] < values[idx_j]) {
17        swap(values[idx_j], values[idx_j + 1]);
18      }
19    }
20  }
21}

Простые сортировки

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

При сортировке вставками массив постепенно перебирается слева направо. При этом каждый последующий элемент размещается так, чтобы он оказался между ближайшими элементами с минимальным и максимальным значением.

1void InsertionSort(vector<int>& values) {
2  for (size_t i = 1; i < values.size(); ++i) {
3    int x = values[i];
4    size_t j = i;
5    while (j > 0 && values[j - 1] > x) {
6      values[j] = values[j - 1];
7      --j;
8    }
9    values[j] = x;
10  }
11}

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

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

1void SelectionSort(vector<int>& values) {
2  for (auto i = values.begin(); i != values.end(); ++i) {
3    auto j = std::min_element(i, values.end());
4    swap(*i, *j);
5  }
6}

Эффективные сортировки

Быстрая сортировка

Этот алгоритм состоит из трёх шагов. Сначала из массива нужно выбрать один элемент — его обычно называют опорным. Затем другие элементы в массиве перераспределяют так, чтобы элементы меньше опорного оказались до него, а большие или равные — после. А дальше рекурсивно применяют первые два шага к подмассивам справа и слева от опорного значения.

Быструю сортировку изобрели в 1960 году для машинного перевода: тогда словари хранились на магнитных лентах, а сортировка слов обрабатываемого текста позволяла получить переводы за один прогон ленты, без перемотки назад.

1int Partition(vector<int>& values, int l, int r) {
2  int x = values[r];
3  int less = l;
4
5  for (int i = l; i < r; ++i) {
6    if (values[i] <= x) {
7      swap(values[i], values[less]);
8      ++less;
9    }
10  }
11  swap(values[less], values[r]);
12  return less;
13}
14
15void QuickSortImpl(vector<int>& values, int l, int r) {
16  if (l < r) {
17    int q = Partition(values, l, r);
18    QuickSortImpl(values, l, q - 1);
19    QuickSortImpl(values, q + 1, r);
20  }
21}
22
23void QuickSort(vector<int>& values) {
24  if (!values.empty()) {
25    QuickSortImpl(values, 0, values.size() - 1);
26  }
27}

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

Сортировка слиянием пригодится для таких структур данных, в которых доступ к элементам осуществляется последовательно (например, для потоков). Здесь массив разбивается на две примерно равные части и каждая из них сортируется по отдельности. Затем два отсортированных подмассива сливаются в один.

1void MergeSortImpl(vector<int>& values, vector<int>& buffer, int l, int r) {
2  if (l < r) {
3    int m = (l + r) / 2;
4    MergeSortImpl(values, buffer, l, m);
5    MergeSortImpl(values, buffer, m + 1, r);
6
7    int k = l;
8    for (int i = l, j = m + 1; i <= m || j <= r; ) {
9      if (j > r || (i <= m && values[i] < values[j])) {
10        buffer[k] = values[i];
11        ++i;
12      } else {
13        buffer[k] = values[j];
14        ++j;
15      }
16      ++k;
17    }
18    for (int i = l; i <= r; ++i) {
19      values[i] = buffer[i];
20    }
21  }
22}
23
24void MergeSort(vector<int>& values) {
25  if (!values.empty()) {
26    vector<int> buffer(values.size());
27    MergeSortImpl(values, buffer, 0, values.size() - 1);
28  }
29}

Пирамидальная сортировка

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

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

1void HeapSort(vector<int>& values) {
2std::make_heap(values.begin(), values.end());
3for (auto i = values.end(); i != values.begin(); --i) {
4std::pop_heap(values.begin(), i);
5 }
6}