logo
shpori (1) / shpori (1)

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

Вход: массив элементов (a1,…,an), принадлежащих некоторому вполне упорядоченному множеству S

Выход: перестановка этих элементов (b1,…,bn) такая, что bi£bi+1, i=1,…,n-1.

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

Идея: на i-м каждом шаге элемент ai вставляется на свое место в уже отсортированный подмассив (a1,…,ai-1)

for (i=2; i£n; i++)

{

curr = a[i];

j = i-1;

while ((j>0) && (a[j] > curr))

{

a[j+1] = a[j];

j--;

}

a[j+1] = curr;

}

На i-м шаге в худшем случае выполняется С*(i-1) операций

T = C + 2C +…+C(n-1) = Cn(n-1)/2 = O(n(n-1)/2)

Трудоемкость в среднем - O(n(n-1)/4).

Дерево алгоритма сортировки:

1)Внутренние вершины получают метки (i,j). Такая

вершина соответствует операции сравнения элементов

ai и aj. Корень соответствует самой первой операции

сравнения.

2) Каждый лист соответствует результату работы

алгоритма и получает пометку (b1,…,bn), где (b1,…,bn) –

пересатновка элементов массива, получившаяся в

результате выполнения алгоритма.

3) Каждое ребро получает метку £ или > в соответствии

с результатом выполнения операции сравнения в

вершине, из которой это ребро выходит

Трудоемкость в худшем случае – длина самого длинного

пути из корня дерева в его лист (высота дерева)

Лемма. Пусть высота дерева c L листьями равна h. Тогда L£2h.

В дереве алгоритма число листьев равно n!. L = n! £ 2h

Метод “разделяй и властвуй”

1. Разделение задачи на несколько подзадач

2. Решение этих подзадач (например, рекурсивно)

3. Комбинирование решений подзадач и получение из них решения исходной задачи

QuickSort

Пусть A[p…r] = (ap,…,ar) A=A[1…n]

1.Переупорядочеваем подмассив A[p…r] таким образом, чтобы существовал qÎ [p,r] такой, что для любого iÎ [p,q-1] ai£aq и для любого jÎ [q+1,r] aq£aj

Quicksort(A,p,r)

{

if (p < r)

{

q = Findq(A,p,r);

QuickSort(A,p,q-1);

QuickSort(A,q+1,r);

}

}

Quicksort(A,1,n)

x = A[r]; q = p;

for (i=p; i<=r;i++)

{

if (A[i]<=x)

{

swap(A[i],A[q]);

q++;

}

}

Трудоемкость процедуры Findq - Cm = O(m), где m=r-p

2.Cортируем подмассивы A[p…q-1] и A[q+1…r]

Худшая трудоемкость у алгоритма QuickSort будет тогда, когда на каждом шаге Findq будет генерировать разбиение массива A[p…r] на подмассивы из 1 элемента и m-1 элемента

Трудоемкость в худшем – T(n) = Cn + C + T(n-1) = O(n2)

В лучшем случае разбивает массив на 2 подмассива примерно равной длины. Тогда T(n) = Cn + 2T(n/2)

Лемма. Решение этого рекуррентного уравнения – O(nlogn)

Сортировка подсчетом

T(n) = O(maxi=1,…,n(a[i])*n)