Сортировка Шелла

← →
Dismember © (2007-04-07 07:48) [0]

В общем, задача такая. Есть некоторый массив из n элементов , в котором нужно найти k наибольших элементов, используя сортировку Шелла. Но главная задача - сократить количество сравнения и пересылок, то есть массив не должен быть полностью упорядочен. Предложите какой-нибудь алгоритм :)

← →
jup (2007-04-07 07:56) [1]

Может так:
отсортировать массив любом способом а потом просто взять k последних элементов? Или обязательно использовать сортировку Шелла?

← →
SerJaNT © (2007-04-07 07:59) [2]

procedure sort_shell (var a:array of word);
var
bis,i,j,k:longint;
h:word;
begin
bis:=high(a);
k:=bis shr 1;
While k>0 do
Begin
For i:=0 To bis-k do
begin
j:=i;
While (j>=0) And (a[j]>a[j+k]) do
begin
h:=a[j];
a[j]:=a[j+k];
a[j+k]:=h;
dec(j,k);
end;
end;
k:=k shr 1;
End;
End;

← →
Dismember © (2007-04-07 08:34) [3]

Вся проблема в том, что массив полностью сортировать не нужно. Я понимаю, что проще сначала отсортировать массив, а потом взять последние k элементов, но тот, кому я пытаюсь сдать эту чертову задачу, утверждает, что можно каким-то образом без полной сортировки массива найти в нем максимальные элементы.

> утверждает, что можно каким-то образом без полной сортировки массива найти в нем максимальные элементы.

Конечно можно. Но у вас ведь условие, использовать сортировку Шелла. Ну используйте ее тогда на каком-нибудь подмассиве из одного элемента - это ничему не помешает, а потом делайте задачу k-кратным поиском максимального элемента и перемещением его в низ массива.

Для частичной сортировки массива гораздо лучше использовать модифицированный QuickSort. В STL C++ включен partialsort, основанный как раз на этом.
На мой взгляд, сортировка Шелла несколько хуже подходит для этой задачи, поскольку она сортирует группы элементов с уменьшающимся шагом, быстро выбирая наибольшие элементы в группах, однако при этом не гарантируя, что в какой-то группе нужные большие элементы не будут близки к началу (на шаге 3 демонстрации http://algolist.manual.ru/sort/shell_sort.php большой элемент 10 стоит близко к началу). Полагаю, что можно применить метод, аналогичный выбору медианы за линейное время (с группами по 5 элементов), или задаче с выбором лучших беговых котов по результатам небольшого количества забегов (из пятничных задач), однако это достаточно сложно и не слишком эффективно, в отличие от PartialQuickSort (сложность O(N+kLogk))

>SerJaNT © (07.04.07 07:59) [2]
это не слишком удачная реализация. Уменьшение шага вдвое было как раз изначально и предложено Шеллом, однако при этом, скажем, четные и нечетные элементы не сравниваются друг с другом до последнего прохода, что приводи к квадратичному поведению в худжем случае. Лучше использовать взаимно простые попарно числа, хотя бы из ряда 2^k -1 (1,3,7...)

Сортировка Шелла Найти похожие ветки