19.05.2021 07:47
prince86 2 1200 Источник

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

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

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

  • Поразрядная сортировка.

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

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

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

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

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

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

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

Наибольшая временная сложность алгоритма равна  O( nlog n ).

Принцип работы

Сортировка слиянием - это эффективный алгоритм сортировки. Он работает по технике «Разделяй и властвуй».

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

  • Властвуй: То есть рекурсивная сортировка подсписков.

  • Соединяй: Слияние обоих отсортированных подсписков в один.

По этой технике большая задача делится на более мелкие части, а затем эти мелкие части которые легче будет решить, а затем их можно объединить, чтобы получить окончательный результат. В этом случае весь массив разделен на подсписок n. В каждом подсписке будет один элемент. И мы будем продолжать делить подсписок, пока не получим подсписок с одним элементом. Затем, наконец, мы объединяем каждый из подсписок, и этот процесс объединения подсписок продолжается до тех пор, пока мы не получим новый отсортированный подсписок. И мы продолжаем объединять подсписки, пока не получим окончательный полный отсортированный список.

Принцип работы включает следующие шаги:

  • Разделить заданный массив на подсписок;

  • Объединить подсписки для получения одного полного отсортированного списка.

Возьмем к примеру массив из пяти элементов от 0 до 4. Этот массив будет разделен на две (левую и правую) части. Левая часть массива содержит 2 элемента, а правая часть - 3 элемента. Левая часть также будет разделена на две части, и тогда мы получим два отдельных подсписка. Как только мы получим отсортированные подсписки для левой части, они будут объединены в один отсортированный левый массив.

Теперь отсортируем правую часть массива, сначала разделив его на две части. Правая часть теперь будет содержать еще две части, то есть левую и правую части. Левая часть содержит только один элемент, а правая часть содержит два элемента. Левая часть уже отсортирована. Итак, теперь мы отсортируем правую часть, разделив ее на две части. Теперь эти две отсортированные части правой части будут объединены. Затем отсортированные слева и справа части правой стороны будут объединены в один отсортированный правый массив. Наконец, мы получим единый отсортированный массив / список, объединив отсортированный слева и справа массив.

Пример

Чтобы понять эту концепцию, давайте рассмотрим массив «B», который приведен ниже. В этом массиве всего девять элементов.

Мы разделим этот массив на два подмассива. Для этого мы найдем его среднюю точку, а затем разделим этот массив от этой средней точки. Итак, находим средину:

Итак, этот массив разделен по индексу 4, подмассивы будут:

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

Средняя точка первого подсписка:

Средняя точка второго подсписка:

Теперь у нас есть 4 подсписка. Они будут дальше отделены от своих средних точек.

Средняя точка третьего подсписка :

Средние точки четвертого, пятого и шестого подсписка :

Есть только один подсписок, состоящий из 2 элементов. Итак, мы разделим этот подсписок на следующие подсписки. Остальные подсписки останутся такими же, потому что они содержат по одному элементу.

Средняя точка седьмого подсписка:

 Далее мы объединим эти подсписки. Этот процесс будет выполняться путем объединения первых двух элементов и их сравнения. Видно, что 5 меньше 15, поэтому мы сначала поместим 5, а затем 15 в новый отсортированный подсписок.

И этот первый новый отсортированный подсписок будет сравниваться с третьим элементом, который равен 24. И, во-вторых, отсортированный подсписок будет:

Затем мы сравним 4-й и 5-й элементы подсписка, и можно увидеть, что 1 меньше 8. Итак, теперь сначала будет помещен 1, а затем 8. После этого мы получим 3-й отсортированный подсписок.:

Теперь этот третий отсортированный подсписок будет сравниваться со вторым отсортированным подсписком, и мы получим 4-й отсортированный подсписок:

Точно так же мы объединим 5-й отсортированный подсписок, сравнив и объединив 6-й и 7-й подсписки.

Теперь мы получим 6-й отсортированный подсписок, сравнив 8-й и 9-й подсписки.

Затем мы сравним и объединим 5-й и 6-й отсортированные подсписки, чтобы получить 7-й отсортированный подсписок.

В конце концов, 4-й и 7-й отсортированные подсписки будут сравниваться и объединяться, и будет получен 8-й отсортированный подсписок. Для этого мы сравним первый элемент 4-го и 7-го отсортированных подсписок и найдем элемент меньшего размера. Меньший элемент будет помещен первым. Затем указатель будет увеличиваться в этом отсортированном подсписке и сравниваться с другим отсортированным подсписком.

Алгоритм

Основанный на принципе разделяй и властвуй, алгоритм сортировки слиянием будет выглядеть так: 

merge( B , fv , lv ){ 
  if ( lv < fv ){
    M = (lv +fv )/2 
    mergesort ( B , lv , M ) 
    mergesort ( B , M + 1 , fv ) 
    merge( B , lv , M , fv )
  }
}

Использование кода

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

merge( B ,fv , M , lv )
x = fv;
y = M + 1;
z = fv;

while ( x ? M & y ? lv ){
	if ( B [x] ? B[y] ){
			C[z] = B [z];
			x++;
			z++;
  }else{
			C [z ] = B [y]
			y++;
			z++;
	}
	if ( x > M ){
		while ( y ? lv ){
      C[z] = B[y];
      y++;
      z++;
		}
   }else{
			while ( x ? M ){
				C[z] = B[x];
				x++;
				z++;
			}
		}
	for ( z = lv ; z ? fv ; z++ ){
			B[z] = C[z];
	}
}

Псевдокод

Чтобы понять принцип работы псевдокода сортировки слиянием, в качестве входных данных будет взят несортированный массив «B». И на выходе мы получим отсортированный массив. Мы разделим этот несортированный массив на подмассивы. Как только мы получим одноэлементный массив, нам не нужно будет делить его дальше, потому что это будет отсортированный массив. Это называется базовый вариант. Итак, сначала мы напишем базовый вариант, а затем будут созданы левый и правый массив. Затем эти массивы будут отсортированы и объединены. 

if ( x == 1 ){
	return B;
}
L = mergesort( L );   
R = mergesort( R );    
m_array = merge ( L , R );  
return merdgedarray ;

Анализ времени выполнения

Время выполнения алгоритма обозначается как T(N). Рассмотрим два примера:

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

  • Для слияния слева и справа время будет:

Где «b» - это просто константа. И bN показывает, что слияние занимает некоторое постоянное количество времени на каждый сливаемый элемент.

Можем записать как:

Таким образом, время выполнения сортировки слиянием будет ( Nlog2N )

K-Way слияние

Также известно как многостороннее слияние. Используется для внешней сортировки. Оно имеет входные k отсортированных массивов, в каждом из которых содержится n элементов. Здесь мы объединим отсортированный массив, чтобы получить отсортированный вывод.

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

Используется при внешнем слиянии. Он состоит из n элементов. Рассмотрим на примере двухстороннее слияние. В качестве входных данных были взяты два массива. Каждый массив состоит из четырех элементов. Размер обоих массивов - четыре. Оба массива проиндексированы от 0 до 3. Чтобы объединить эти два массива, нам нужен указатель с тремя указателями, который помещается в начальный элемент каждого массива. Оба массива уже отсортированы. Объединив эти два массива, мы получим результирующий массив, состоящий из восьми элементов. Сравним первый элемент первых двух массивов. И меньший элемент будет помещен первым в выходной массив. Затем указатель выходного массива и второго массива будет увеличен, и будет продолжен тот же процесс сравнения элементов. В итоге на выходе мы получим отсортированный массив.

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

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

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

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

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

  • Стабильное время выполнения.

  • Можно использовать для больших файлов.

  • Идеально для организации труднодоступных данных.

Недостатки:

  • Для короткого списка процесс более медленный.

  • Требует дополнительной памяти для хранения информации.

Применение:

  • Для организации связанных списков за время O (nlog n).

  • Инверсивный счет.

  • Сортировка большого количества информации.