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

Перейти к: навигация, поиск

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
'''Сортировка слиянием''' (англ. ''Merge sort'') {{---}} алгоритм сортировки, использующий <tex>O(n)</tex> дополнительной памяти и работающий за <tex>O(n\log(n))</tex> времени.
+
'''Сортировка слиянием''' (англ. ''Merge sort'') {{---}} алгоритм сортировки, пред­ло­женный Джо­ном фон Ней­ма­ном в 1945 го­ду.
 +
 
 +
Это устойчивый алгоритм, использующий <tex>O(n)</tex> дополнительной памяти и работающий за <tex>O(n</tex> <tex>\log n)</tex> времени.
  
 
==Принцип работы==
 
==Принцип работы==
Строка 69: Строка 71:
 
==Время работы==
 
==Время работы==
 
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> {{---}} время сортировки массива длины <tex>n</tex>, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br>
 
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай <tex>T(n)</tex> {{---}} время сортировки массива длины <tex>n</tex>, тогда для сортировки слиянием справедливо <tex>T(n)=2T(n/2)+O(n)</tex> <br>
<tex>O(n)</tex> {{---}} время, необходимое на то, чтобы слить два массива длины <tex>n</tex>. Распишем это соотношение:
+
<tex>O(n)</tex> {{---}} время, необходимое на то, чтобы слить два массива. Распишем это соотношение:
 +
 
 +
<tex>T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n)=\dots=2^kT(1)+kO(n)</tex>.
  
<tex>T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n)=\dots=T(1)+\log(n)O(n)=O(n\log(n))</tex>.
+
Осталось оценить <tex>k</tex>. Мы знаем, что <tex>2^k=n</tex>, а значит <tex>k=\log n</tex>. Уравнение примет вид <tex>T(n)=nT(1)+ \log n</tex> <tex>O(n)</tex>. Так как <tex>T(1)</tex> {{---}} константа, то <tex>T(n)=O(n)+\log n </tex> <tex>O(n)=O(n\log n)</tex>.
  
 
==Сравнение с другими алгоритмами==
 
==Сравнение с другими алгоритмами==
 
Достоинства:
 
Достоинства:
 
* устойчивая,
 
* устойчивая,
* можно написать эффективную [[Многопоточная сортировка слиянием|многопоточную сортировку слиянием]],
+
* можно написать эффективную сортировку параллельную сортировку слиянием<ref>[[Многопоточная сортировка слиянием]]</ref>,
 
* сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память<ref>[http://en.wikipedia.org/wiki/External_sorting Wikipedia {{---}} External sorting]</ref>.
 
* сортировка данных, расположенных на периферийных устройствах и не вмещающихся в оперативную память<ref>[http://en.wikipedia.org/wiki/External_sorting Wikipedia {{---}} External sorting]</ref>.
 
Недостатки:
 
Недостатки:
 +
* при любых входных данных время работы {{---}} <tex>O(n\log{n})</tex>,
 
* требуется дополнительно <tex>O(n)</tex> памяти, но можно модифицировать до <tex>O(1)</tex>.
 
* требуется дополнительно <tex>O(n)</tex> памяти, но можно модифицировать до <tex>O(1)</tex>.
  
Строка 93: Строка 98:
 
*[http://ru.wikipedia.org/wiki/Mergesort Википедия {{---}} сортировка слиянием]
 
*[http://ru.wikipedia.org/wiki/Mergesort Википедия {{---}} сортировка слиянием]
 
*[http://www.sorting-algorithms.com/merge-sort Визуализатор]
 
*[http://www.sorting-algorithms.com/merge-sort Визуализатор]
*[https://ru.wikibooks.org/wiki/Примеры_реализации_сортировки_слиянием Викиучебник {{---}} Примеры реализации на различных языках программирования]
+
*[http://ru.wikibooks.org/wiki/%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC Викиучебник {{---}} Примеры реализации на различных языках программирования]
  
  

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: