Реферат: Методы внутренней сортировки

A[j]:= w

i:= i+1

j:= j-1

все

кц пока i > j;

если m < j

то QuickSort (m, j);

все

если i < t

то QuickSort (i, t);

все

кон

Оценим эффективность метода. Предположим, что размер массива равен числу, являющемуся степенью двойки, и при каждом разделении элемент X находится точно в середине массива. В этом случае при первом просмотре выполняется Nсравнений и массив разделяется на две части размерами »N/2 сравнений и т.д. следовательно,

C = N + 2 × (N / 2) + 4 × (N / 4) + … + N × (N / N) = O(N ×log₂ N).

Внутреннее слияние

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

Алг Sl (арг цел k, m, q, цел таб A [1:N])

нач цел k, i, j, t, цел таб A [1:N]

i:= k

j:= m+1

t:= 1

нц пока (i <= m) и (j <= q)

если A[i] <= A[j] то

D[t]:= A[i]

i:= i +1

иначе

D[t]:= A[j]

j:= j+1

t:= t +1