Алгоритмы сортировки 1

Алгоритм 4. Сортировка слиянием

жүктеу 77 Kb.

бет	5/5
Дата	09.01.2022
өлшемі	77 Kb.
	#31997

1 2 3 4 5

Алгоритмы сортировка

Алгоритм 4. Сортировка слиянием.

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

Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай T(n) - время сортировки массива длины n, тогда для сортировки слиянием справедливо T(n)=2T(n/2)+O(n) (O(n) - это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:

Осталось оценить k. Мы знаем, что 2k=n, а значит k=log2n. Уравнение примет вид T(n)=nT(1)+ log2nO(n). Так как T(1) - константа, то T(n)=O(n)+log2nO(n)=O(nlog2n). То есть, оценка времени работы сортировки слиянием меньше, чем у первых трех алгоритмов (я прошу прощения у тех, кто не понял мои рассуждения или не согласен с ними, - просто поверьте мне на слово). Перед тем как объяснить, чем этот метод лучше, рассмотрим еще один алгоритм.

жүктеу 77 Kb.

Достарыңызбен бөлісу:

1 2 3 4 5