Алгоритм сортировки слиянием

Algorithm

merge(array, left, middle, right)


Input − The data set array, left, middle and right index

Output − The merged list

Begin
   nLeft := m - left+1
   nRight := right – m
   define arrays leftArr and rightArr of size nLeft and nRight respectively

   for i := 0 to nLeft do
      leftArr := array
   done

   for j := 0 to nRight do
      rightArr := array
   done

   i := 0, j := 0, k := left
   while i < nLeft AND j < nRight do
      if leftArr <= rightArr then
         array = leftArr
         i := i+1
      else
         array = rightArr
         j := j+1
      k := k+1
   done

   while i < nLeft do
      array := leftArr
      i := i+1
      k := k+1
   done

   while j < nRight do
      array := rightArr
      j := j+1
      k := k+1
   done
End

mergeSort(array, left, right)

Input − An array of data, and lower and upper bound of the array

Output − The sorted Array

Begin
   if lower < right then
      mid := left + (right - left) /2
      mergeSort(array, left, mid)
      mergeSort (array, mid+1, right)
      merge(array, left, mid, right)
End

Достоинства и недостатки

Достоинства:

  • Работает даже на структурах данных последовательного доступа.
  • Хорошо сочетается с подкачкой и кэшированием памяти.
  • Неплохо работает в параллельном варианте: легко разбить задачи между процессорами поровну, но трудно сделать так, чтобы другие процессоры взяли на себя работу, в случае если один процессор задержится.
  • Не имеет «трудных» входных данных.
  • Устойчивая — сохраняет порядок равных элементов (принадлежащих одному классу эквивалентности по сравнению).

Недостатки:

  • На «почти отсортированных» массивах работает столь же долго, как на хаотичных. Существует вариант сортировки слиянием, который работает быстрее на частично отсортированных данных, но он требует дополнительной памяти, в дополнении ко временному буферу, который используется непосредственно для сортировки.
  • Требует дополнительной памяти по размеру исходного массива.

Python 2.7 (функциональная реализация)

def merge(right, left, result):
    result.append((left if left < right else right).pop(0))
    return merge(right=right, left=left, result=result) if left and right else result+left+right
 
merge_sort = (lambda arr: arr if len(arr) == 1 else merge(merge_sort(arr[len(arr)/2:]),
                                                          merge_sort(arr[:len(arr)/2]), []))

 Недостатком сортировки слиянием является использование дополнительной памяти. Но когда работать приходиться с файлами или списками, доступ к которым осуществляется только последовательно, то очень удобно применять именно этот метод. Также, к достоинствам алгоритма стоит отнести его устойчивость и неплохую скорость работы O(n*logn).

При написании статьи были использованы открытые источники сети интернет :

Youtube 

Алгоритм двухпутевого слияния

Исходная последовательность разбивается на две подпоследовательности: Эти две подпоследовательности объединяются в одну, содержащую упорядоченные пары. Полученная последовательность снова разбивается на две, и пары объединяются в упорядоченные четверки: Полученная последовательность снова разбивается на две и собирается в упорядоченные восьмерки. Данная операция повторяется до тех пор, пока полученная упорядоченная последовательность не будет иметь такой же размер, как у сортируемой. Основной операцией является слияние. При слиянии требуется дополнительная память для размещения файла, образующегося при слиянии. Операция линейно зависит от количества элементов в объединяемых массивах.Реализация метода двухпутевого слияния на Си

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970

#include <stdio.h>#include <stdlib.h>// Функция сортировки двухпутевым слияниемvoid merge(int *a, int n){  int mid = n / 2; // находим середину сортируемой последовательности  if (n % 2 == 1)    mid++;  int h = 1; // шаг  // выделяем память под формируемую последовательность  int *c = (int*)malloc(n * sizeof(int));  int step;  while (h < n)   {    step = h;    int i = 0;   // индекс первого пути    int j = mid; // индекс второго пути    int k = 0;   // индекс элемента в результирующей последовательности    while (step <= mid)     {      while ((i < step) && (j < n) && (j < (mid + step)))       { // пока не дошли до конца пути        // заполняем следующий элемент формируемой последовательности        // меньшим из двух просматриваемых        if (a < a)          {          c = a;          i++; k++;        }        else {          c = a;          j++; k++;        }      }      while (i < step)       { // переписываем оставшиеся элементы первого пути (если второй кончился раньше)        c = a;        i++; k++;      }      while ((j < (mid + step)) && (j<n))       {  // переписываем оставшиеся элементы второго пути (если первый кончился раньше)        c = a;        j++; k++;      }      step = step + h; // переходим к следующему этапу    }    h = h * 2;    // Переносим упорядоченную последовательность (промежуточный вариант) в исходный массив    for (i = 0; i<n; i++)      a = c;  }}int main() {  int a;  // Заполнение массива случайными числами  for (int i = 0; i<8; i++)    a = rand() % 20 — 10;  // Вывод элементов массива до сортировки  for (int i = 0; i<8; i++)    printf(«%d «, a);  printf(«\n»);  merge(a, 8); // вызов функции сортировки  // Вывод элементов массива после сортировки  for (int i = 0; i<8; i++)    printf(«%d «, a);  printf(«\n»);  getchar();  return 0;}

Как работает Быстрая сортировка

Быстрая сортировка чаще всего не сможет разделить массив на равные части. Это потому, что весь процесс зависит от того, как мы выбираем опорный элемент. Нам нужно выбрать опору так, чтобы она была примерно больше половины элементов и, следовательно, примерно меньше, чем другая половина элементов. Каким бы интуитивным ни казался этот процесс, это очень сложно сделать.

Подумайте об этом на мгновение — как бы вы выбрали адекватную опору для вашего массива? В истории быстрой сортировки было представлено много идей о том, как выбрать центральную точку — случайный выбор элемента, который не работает из-за того, что «дорогой» выбор случайного элемента не гарантирует хорошего выбора центральной точки; выбор элемента из середины; выбор медианы первого, среднего и последнего элемента; и еще более сложные рекурсивные формулы.

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

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

Теперь, когда мы выбрали опорный элемент — что нам с ним делать? Опять же, есть несколько способов сделать само разбиение. У нас будет «указатель» на нашу опору, указатель на «меньшие» элементы и указатель на «более крупные» элементы.

Цель состоит в том, чтобы переместить элементы так, чтобы все элементы, меньшие, чем опора, находились слева от него, а все более крупные элементы были справа от него. Меньшие и большие элементы не обязательно будут отсортированы, мы просто хотим, чтобы они находились на правильной стороне оси. Затем мы рекурсивно проходим левую и правую сторону оси.

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

19, 89,27,41,66,28,44,76,58,88,83,97,12,21,43

Выберем первый элемент как опору 19), а указатель на меньшие элементы (называемый «low») будет следующим элементом, указатель на более крупные элементы (называемый «high») станем последний элемент в списке.


19 | 89 (low), 27,41,66,28,44,76,58,88,83,97,12,21,43 (high)

Мы двигаемся в сторону high то есть влево, пока не найдем значение, которое ниже нашего опорного элемента.

19 | 89 (low),27,41,66,28,44,76,58,88,83,97,12,21 (high),43

  • Теперь, когда наш элемент high указывает на элемент 21, то есть на значение меньше чем опорное значение, мы хотим найти значение в начале массива, с которым мы можем поменять его местами. Нет смысла менять местами значение, которое меньше, чем опорное значение, поэтому, если low указывает на меньший элемент, мы пытаемся найти тот, который будет больше.
  • Мы перемещаем переменную low вправо, пока не найдем элемент больше, чем опорное значение. К счастью, low уже имеет значение 89.
  • Мы меняем местами low и high:

19 | 21 (low),27,41,66,28,44,76,58,88,83,97,12,89 (high),43

  • Сразу после этого мы перемещает high влево и low вправо (поскольку 21 и 89 теперь на своих местах)
  • Опять же, мы двигаемся high влево, пока не достигнем значения, меньшего, чем опорное значение, и мы сразу находим — 12
  • Теперь мы ищем значение больше, чем опорное значение, двигая low вправо, и находим такое значение 41

Этот процесс продолжается до тех пор, пока указатели low и high наконец не встретятся в одном элементе:

19 | 21,27,12,28 (low/high),44,66,76,58,88,83,97,12,89,43

Мы больше не используем это опорное значение, поэтому остается только поменять опорную точку и high, и мы закончили с этим рекурсивным шагом:

28,21,27,12,19,44,66,76,58,88,83,97,12,89,43

Как видите, мы достигли того, что все значения, меньшие 29, теперь слева от 29, а все значения больше 29 справа.

Затем алгоритм делает то же самое для коллекции 28,21,27,12,19 (левая сторона) и 66,76,58,88,83,97,12,89,43 (правая сторона). И так далее.

Writing the Code for Merge Algorithm

A noticeable difference between the merging step we described above and the one we use for merge sort is that we only perform the merge function on consecutive sub-arrays.

This is why we only need the array, the first position, the last index of the first subarray(we can calculate the first index of the second subarray) and the last index of the second subarray.

Our task is to merge two subarrays A and A to create a sorted array A. So the inputs to the function are A, p, q and r

The merge function works as follows:

  1. Create copies of the subarrays and M ← A.
  2. Create three pointers i, j and k
    1. i maintains current index of L, starting at 1
    2. j maintains current index of M, starting at 1
    3. k maintains the current index of A, starting at p.
  3. Until we reach the end of either L or M, pick the larger among the elements from L and M and place them in the correct position at A
  4. When we run out of elements in either L or M, pick up the remaining elements and put in A

In code, this would look like:

Алгоритм[править]

У нас есть массив, который состоит из двух отсортированных частей:

Разобьем наш массив на подряд идущих блоков длиной . Остаток трогать не будем.

Найдем блок, содержащий конец первой отсортированной части. Поменяем его с последним блоком. В дальнейшем будем использовать его как буфер обмена.

Отсортируем блоки по возрастанию по первому элементу (если первые элементы равны, тогда по последнему).

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

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

Пользуясь буфером обмена, последовательно сольем пары соседних блоков и потом и и т.д..

Попытаемся слить первый и второй блок. Поменяем местами первый блок с буфером обмена. И, как в обычном слиянии, пользуясь двумя указателями, сливаем второй блок и только что измененный буфер. Результат начинаем записывать с начала первого блока. Чтобы не потерять данные, вместо записи используем обмен элементов. Так как блоки имеют одинаковую длину и между указателем на второй блок и указателем на запись расстояние равно длине блока, то слияние произойдет корректно (пример использования буфера обмена приведен ниже).

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

— размер остатка вместе с буфером. Используя квадратичную или более быструю сортировку, которая требует дополнительной памяти, отсортируем подмассив длиной , который находится в конце.

Так как , то сортировка пройдет за .


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

В результате мы получили отсортированный исходный массив.

Сравнение скоростей сортировок

Для сравнения сгенерируем массив из 5000 чисел от 0 до 1000. Затем определим время, необходимое для завершения каждого алгоритма. Повторим каждый метод 10 раз, чтобы можно было более точно установить, насколько каждый из них производителен.

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

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

Лучше понять эти алгоритмы вам поможет их визуализация.

Сортировка деревом

Сортировка деревом за счёт дополнительной памяти быстро решает вопрос с добавлением очередного элемента в отсортированную часть массива. Причём в роли отсортированной части массива выступает бинарное дерево. Дерево формируется буквально на лету при переборе элементов.

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

Основная загвоздка сортировок вставками (затраты на вставку элемента на своё место в отсортированной части массива) здесь решена, построение происходит вполне оперативно. Во всяком случае для освобождения точки вставки не нужно медленно передвигать караваны элементов как в предыдущих алгоритмах. Казалось бы, вот она, наилучшая из сортировок вставками. Но есть проблема.

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

Рандомный массив со значениями от 1 до 10. Элементы в таком порядке генерируют несбалансированное двоичное дерево:

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

Значения элементов те же, но порядок другой. Генерируется сбалансированное двоичное дерево:На прекрасной сакуре Не хватает лепестка: Бинарное дерево из десятки.

Проблему несбалансированных деревьев решает сортировка выворачиванием, которая использует особую разновидность бинарного дерева поиска — splay tree. Это замечательное древо-трансформер, которое после каждой операции перестраивается в сбалансированное состояние. Про это будет отдельная статья. К тому времени подготовлю и реализации на Python как для Tree Sort, так и для Splay sort.

Ну чтож, мы кратенько прошлись по самым популярным сортировкам вставками. Простые вставки, Шелл и двоичное дерево мы все знаем ещё со школы. А теперь рассмотрим других представителей этого класса, не столь широко известных.

Вики / Wiki

Вставки / Insertion,Шелл / Shell,Дерево / Tree

Статьи серии:

Кто пользуется AlgoLab — рекомендую обновить файл. Я добавил в это приложение простые вставки с бинарным поиском и па́рные вставки. Также полностью переписал визуализацию для Шелла (в предыдущей версии там было не пойми что) и добавил подсветку родительской ветки при вставке элемента в бинарное дерево.

Остаточный правильный вариант алгоритма:

Сигнатура такая же как и в предыдущем варианте

Но следует заметить, что данный вариант предполагает первым параметром указатель, на котором можно вызвать операцию delete[] (почему — мы увидим далее). То-есть когда мы выделяли память, мы именно для этого указателя присваивали адрес начала массива.

Предварительная подготовка

В данном примере так называемый «коэффициент навёрстывания» (catch up coefficient) — это просто константа со значением 8. Она показывает сколько максимум элементов мы попытаемся пройти, чтобы вставить новый «недо-максимум» или «недо-минимум» на своё место.

Теперь, самое главное — правильная выборка элементов из исходного массива

Цикл начинается с localCatchUp (потому что предыдущие элементы уже попали в нашу выборку как значения от которых мы будем отталкиваться). И проходит до конца. Так что после в конце концов все элементы распределятся либо в массив выборки либо в один из массивов недо-выборки.

Для проверки, можем ли мы вставить элемент в выборку, мы просто будем проверять больше (или равен) ли он элементу на 8 позиций левее (right − localCatchUp). Если это так, то мы просто одним проходом по этим элементам вставляем его на нужную позицию. Это было для правой стороны, то-есть для максимальных элементов. Таким же образом делаем с обратной стороны для минимальных. Если не удалось вставить его ни в одну сторону выборки значит кидаем его в один из rest-массивов.

Цикл будет выглядеть примерно так:


Опять же, что здесь происходит? Сначала пытаемся пихнуть элемент в максимумы. Не получается? — Если возможно, кидаем его в минимумы. При невозможности и это сделать — кладём его в restFirst или restSecond.

Самое сложное уже позади. Теперь после цикла у нас есть отсортированный массив с выборкой (элементы начинаются с индекса и оканчиваются в ), а также массивы restFirst и restSecond длиной restFirstLen и restSecondLen соответственно.

Теперь запускаем нашу функцию сортировки рекурсивно для массивов restFirst и restSecond

Для понимания того как оно всё отработает, сначала нужно посмотреть код до конца. Пока что нужно просто поверить что после рекурсивных вызовов массивы restFirst и restSecond будут отсортированными.

И, наконец, нам нужно слить 3 массива в результирующий и назначить его указателю arr.

Можно было бы сначала слить restFirst + restSecond в какой-нибудь массив restFull, а потом уже производить слияние selection + restFull. Но данный алгоритм обладает таким свойством, что скорее всего массив selection будет содержать намного меньше элементов, чем любой из rest-массивов. Припустим в selection содержится 100 элементов, в restFirst — 990, а в restSecond — 1010. Тогда для создания restFull массива нужно произвести 990 + 1010 = 2000 операций копирования. После чего для слияния с selection — ещё 2000 + 100 копирований. Итого при таком подходе всего копирований будет 2000 + 2100 = 4100.

Давайте применим здесь оптимизацию. Сначала сливаем selection и restFirst в массив selection. Операций копирования: 100 + 990 = 1090. Далее сливаем массивы selection и restSecond на что потратим ещё 1090 + 1010 = 2100 копирований. Суммарно выйдет 2100 + 1090 = 3190, что почти на четверть меньше, нежели при предыдущем подходе.

Выводы

Как видим, алгоритм работает, и работает хорошо. По крайней мере всё чего мы хотели, было достигнуто. На счёт стабильности, не уверен, не проверял. Можете сами проверить. Но по-идее она должна достигаться очень легко. Просто в некоторых местах вместо знака > поставить ≥ или что-то того.

C++

 

               /**
                * @brief         Сортировка элементов от l до r массива buf
                * @param[in/out] buf - сортируемый массив
                * @param     l - левая граница. При первой итерации l = 0
                * @param     r - правая граница. При первой итерации r = buf.size() - 1
                *
                * В результате сортируются все элементы массива buf от l до r включительно.
                */
               template<typename Type>
void MergeSort(vector<Type>& buf, size_t l, size_t r)
{
    //! Условие выхода из рекурсии
    if(l >= r) return;
 
    size_t m = (l + r) / 2;
 
    //! Рекурсивная сортировка полученных массивов
    MergeSort(buf, l, m);
    MergeSort(buf, m+1, r);
    merge(buf, l, r, m);
}
 
/**
 * @brief Слияние элементов.
 * @param[in/out] buf - массив
 * @param     l - левая граница. При певой итерации l = 0
 * @param     r - правая граница. При первой итерации r = buf.size() - 1
 * @param     m - граница подмассивов.
 *
 * Массив buf содержит два отсортированных подмассива:
 * -  - первый отсортированный подмассив.
 * -  - второй отсортированный подмассив.
 * В результате получаем отсортированный массив, полученный из двух подмассивов,
 * который сохраняется в buf.
 */
template<typename Type>
static void merge(vector<Type>& buf, size_t l, size_t r, size_t m)
{
    if (l >= r || m < l || m > r) return;
    if (r == l + 1 && buf > buf) {
        swap(buf, buf);
        return;
    }
 
    vector<Type> tmp(&buf, &buf + (r + 1));
 
    for (size_t i = l, j = 0, k = m - l + 1; i <= r; ++i) {
        if (j > m - l) {      
            buf = tmp;
        } else if(k > r - l) {
            buf = tmp;
        } else {
            buf = (tmp < tmp) ? tmp : tmp;
        }
    }
}

Существует также итеративный алгоритм сортировки, избавленный от рекурсивных вызовов. Такой алгоритм называют «Восходящей сортировкой слиянием».

// Слияние двух упорядоченных массивов
// m1 - Первый массив
// m2 - Второй массив
// l1 - Длина первого массива
// l2 - Длина второго массива
// Возвращает объединённый массив
               template <class T>
T* merge(T *m1, T* m2, int l1, int l2)
{
    T* ret = new T;
    int n = 0;
    // Сливаем массивы, пока один не закончится
    while (l1 && l2) {
        if (*m1 < *m2) {
            ret = *m1;
            m1++;
            --l1;
        } else {
            ret = *m2;
            ++m2;
            --l2;
        }
        ++n;
    }
    // Если закончился первый массив
    if (l1 == 0) {
        for (int i = 0; i < l2; ++i) {
            ret = *m2++;
        }
    } else { // Если закончился второй массив
        for (int i = 0; i < l1; ++i) {
            ret = *m1++;
        }
    }
    return ret;
}
 
// Функция восходящего слияния
template <class T>
void mergeSort(T * mas, int len)
{
    int n = 1, l, ost;
    T * mas1;
    while (n < len) {
        l = 0;
        while (l < len) {
            if (l + n >= len) break;
            ost = (l + n * 2 > len) ? (len - (l + n)) : n;
            mas1 = merge(mas + l, mas + l + n, n, ost);
            for (int i = 0; i < n + ost; ++i)
                mas = mas1;//тут нужно что-то поменять, потому что это лишнее копирование, и оно увеличивает время работы алгоритма в два раза
            delete [] mas1;
            l += n * 2;
        }
        n *= 2;
    }
}

Пример: char a[] = «ASORTINGEXAMPLE»; mergeSort(a, 16); Альтернативная версия алгоритма Сортировки Слиянием.

 template <typename Item>
void Merge(Item Mas[], int left, int right, int medium)
{
    int j = left;
    int k = medium + 1;
    int count = right - left + 1;
 
    if (count <= 1) return;
 
    Item *TmpMas = new Item;
 
    for (int i = 0; i < count; ++i) {
        if (j <= medium && k <= right) {
            if (Mas < Mas)
                TmpMas = Mas;
            else
                TmpMas = Mas;
        } else {
            if (j <= medium)
                TmpMas = Mas;
            else
                TmpMas = Mas;
        }
    }
 
    j = 0;
    for (int i = left; i <= right; ++i) {
        Mas = TmpMas;
    }
    delete[] TmpMas;
}
 
template <typename Item>
void MergeSort(Item a[], int l, int r)
{
    int m;
 
    // Условие выхода из рекурсии
    if(l >= r) return;
 
    m = (l + r) / 2;
 
    // Рекурсивная сортировка полученных массивов
    MergeSort(a, l, m);
    MergeSort(a, m + 1, r);
    Merge(a, l, r, m);
}

Достоинства и недостатки

Достоинства:

  • Работает даже на структурах данных последовательного доступа.
  • Хорошо сочетается с подкачкой и кэшированием памяти.
  • Неплохо работает в параллельном варианте: легко разбить задачи между процессорами поровну, но трудно сделать так, чтобы другие процессоры взяли на себя работу, в случае если один процессор задержится.
  • Не имеет «трудных» входных данных.
  • Устойчивая — сохраняет порядок равных элементов (принадлежащих одному классу эквивалентности по сравнению).

Недостатки:

  • На «почти отсортированных» массивах работает столь же долго, как на хаотичных. Существует вариант сортировки слиянием, который работает быстрее на частично отсортированных данных, но он требует дополнительной памяти, в дополнении ко временному буферу, который используется непосредственно для сортировки.
  • Требует дополнительной памяти по размеру исходного массива.

Начальная версия алгоритма (не оптимальная):

Основная идея алгоритма состоит в так называемом поиске максимума (и минимума). На каждой итерации выбираем из массива элемент. Если он больше предыдущего максимума, то добавляем этот элемент в конец выборки. Иначе если он меньше предыдущего минимума, то дописываем этот элемент в начало. Иначе кладём в отдельный массив.

Собственно сама выборка

Теперь у нас есть отсортированный набор элементов, и «остальные» элементы, которые нам ещё нужно отсортировать. Но сначала нужно произвести некоторые манипуляции с памятью.

Проверим скорость работы алгоритма по сравнению с Quick Sort

Как видим, это совсем не то, чего мы хотели. Почти в 6 раз дольше, чем QuickSort! Но разы в этом контексте неуместно использовать, так как здесь значение имеет именно асимптотика. В данной реализации алгоритма в худшем случае первый и второй элементы будут минимальным и максимальным. И остальные будут скопированы в отдельный массив.

Сложность алгоритма:

  • Худший случай: O (n 2)
  • Средний случай: O (n 2)
  • Лучший случай: O (n)

Хм, это ничем не лучше той же самой сортировки вставками. Да, действительно мы можем найти максимальный (минимальный) элемент очень быстро, и остальные просто не попадут в выборку.

Можем попытаться оптимизировать сортировку слиянием. Для начала проверим скорость обычной сортировки слиянием:

Для простоты использования нужна какая-нибудь обёртка

Результат тестирования:

Да, прирост в скорости наблюдается, но всё-же эта функция работает не так быстро, как Quick Sort. Тем более мы не можем говорить про O (n) на отсортированных массивах. Поэтому этот вариант тоже отбрасываем.

Варианты оптимизации первого варианта

  1. Для того, чтобы сложность не была O (n2), мы можем складывать элементы, которые не попали в выборку не в 1 массив как ранее, а раскинуть на 2 массива. После чего останется просто отсортировать этих две подчасти, и слить их с нашей выборкой. В результате мы получим сложность равную O (n log n)

  2. Как мы уже заметили, абсолютно максимальный (минимальный) элемент в сортируемом массиве может найтись довольно быстро, и это не очень эффективно. Вот тут в помощь нам вступает сортировка вставками. На каждой итерации выборки будем проверять, можем ли мы вставить поточный элемент в набор из последних, например, восьми вставленных.

Если сейчас не понятно, то не расстраивайтесь. Так и должно быть. Сейчас на коде всё станет ясно и вопросы пропадут.


С этим читают