Скачать: CL | DM;

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

← →
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 элементов, но тот, кому я пытаюсь сдать эту чертову задачу, утверждает, что можно каким-то образом без полной сортировки массива найти в нем максимальные элементы.

---

← →
palva ©   (2007-04-07 09:18) [4]

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

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

---

← →
MBo ©   (2007-04-07 09:58) [5]

Для частичной сортировки массива гораздо лучше использовать модифицированный 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...)

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.46 MB
Время: 0.017 c