VPF::[Pascal] сортировка методом Хиббарда

Silvery

Дата 17.12.2006, 21:21 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 17.12.2006

Репутация: нет
Всего: нет

Составить программу, выполняющую сортировку столбцов матрицы методом Хиббарда. Оформить в виде модуля. smile

Anark1

Дата 18.12.2006, 20:26 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 622
Регистрация: 15.12.2006
Где: RF -> Moscow

Репутация: нет
Всего: 11

Я о таком методе что то не слышал. Объясни в чем суть.

--------------------

Enjoy yourself, still you can...;)

Silvery

Дата 18.12.2006, 21:35 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 17.12.2006

Репутация: нет
Всего: нет

Метод Шелла

В рассмотренных алгоритмах сортировки запись перемещается каждый раз только на одну позицию. При этом среднее время работы будет в лучшем случае пропорционально n . Методом, существенно превосходящим простые вставки, при котором записи перемещаются большими скачками, является метод Шелла (сорти-
ровка с убывающим шагом). Метод состоит в том, что упорядочиваемая таблица разделяется на группы элементов, каждая из которых упорядочивается методом вставки. В процессе упорядочения размеры таких
групп увеличиваются до тех пор, пока все элементы таблицы не войдут в упорядоченную группу. Выбор очередной упорядочиваемой группы и ее расположение внутри таблицы производятся так, чтобы можно было использовать предшествующую упорядоченность. Группой таблицы называют последовательность элементов, номера которых образуют арифметическую прогрессию с разностью h (h называют шагом группы). В начале процесса упорядочения выбирается первый шаг группы h1, который зависит от размера таблицы. Шелл предложил брать

h1=[n/2], а hi=h((i-1)/2).

В более поздних работах Хиббард показал, что для ускорения процесса целесообразно определить шаг h1 по формуле:

h1=2**k+1 , где 2**k < n <= 2**(k+1).

Добавлено @ 21:39
надеюсь,вам более понятно о чем написано в скопированной мною статье smile

PrinceMike

Дата 20.12.2006, 23:49 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 184
Регистрация: 23.11.2006
Где: Москва

Репутация: нет
Всего: 1

Хибборд и Шелл это идин и тот же чел? smile

ну да ладно)

Код


procedure Shell(var item: DataArray; count:integer);
const
  t = 5;
var
  i, j, k, s, m: integer;
  h: array[1..t] of integer;
  x: DataItem;
begin
  h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=2; h[5]:=1;
  for m := 1 to t do
    begin
  k:=h[m];
  s:=-k;
  for i := k+1 to count do
  begin
    x := item[i];
    j := i-k;
    if s=0 then
    begin
      s := -k;
      s := s+1;
      item[s] := x;
    end;
    while (x<item[j]) and (j<count) do
      begin
        item[j+k] := item[j];
        j := j-k;
      end;
      item[j+k] := x;
    end;
  end;
end; { конец сортировки Шелла }

Код


PROGRAM SHELL;
CONST N=5;
VAR A: ARRAY [1..5] OF INTEGER;
I, J, K, C: INTEGER;
BEGIN
RANDOMIZE;
FOR I: =1 TO N DO
BEGIN a[i]:= random(15)-1;
WRITE (a[i]: 4);
END;
K:= N div 2;
WHILE k>0 do BEGIN
FOR j:= N-k downto 1 do BEGIN
I:=j;
While i<= n-k do BEGIN
IF a[i]>a[i+k] THEN BEGIN
C: = a[i];
a[i]:= a[i+k];
a[i+k]:=c;
END;
I:= i+k;
END;
END;
K:=K DIV 2;
END;
WRITELN;
FOR i:=1 to n do write(a[i]:4);
END.

Цитата

Генератор случайных чисел.
Для ввода больших массивов удобно использовать специальную функцию – генератор случайных чисел – random(x). Вызов ее без аргумента возвращает случайное вещественное число из интервала [0,1), а вызов с аргументом Х, где Х. – случайное целое число из промежутка [0;n). Случайные целые числа, принадлежащие отрезку [a,b], вычисляют по формуле a+random(b-a+1). Эта функция обычно используется совместно с процедурой randomize, переустанавливающей базу генерации случайных чисел, т.е. позволяющей при последовательных запусках программы получать разные случайные последовательности.

Цитата

Метод Шелла.
Общий метод сортировки массивов, который использует сортировку вставкой. Идея алгоритма состоит в обмене элементов, расположенных не только рядом, как в сортировке методом вставок, но и далеко друг от друга, что значительно сокращает общее число операций перемещения элементов.   Сортировку методом Шелла иными словами называют сортировкой с убывающим шагом. Эффективность этого алгоритма объясняется тем, что при каждом проходе используется относительно небольшое число элементов, а упорядоченность увеличивается при каждом новом просмотре данных.
Пример.
Нам даны 16 записей в произвольном порядке.

•    Сначала делим их на 8 групп по 2 записи в группе (R1,R9; R2,R10…R8,R16) т.е. с шагом 8. В результате сортировки каждой группы приходим ко второй строке заметим, что элементы 3 и 9 поменялись местами, а 16 и 15 переместились вправо. Эта операция будет называться первым просмотром.

•    Затем делим всё на четыре группы по 4 элемента в каждой (R1,R5,R9,R13…R4,R8,R12,R16) шаг 4.

•    Потом на две группы  по 8 элементов в каждой шаг – 2.

•    Ну и затем сортируем все 16 записей.

7  2    9    1    16    4    15    5    11    6    3    8    10    12    14    13
7    2    3    1    10    4    14    5    11    6    9    8    16    12    15    13
7    2    3    1    10    4    9    5    11    6    14    8    16    12    15    13
3    1    7    2    9    4    10    5    11    6    14    8    15    12    16    13
1    2    3    4    5    6    7    8    9    10    11    12    13    14    15    16

--------------------

Silvery

Дата 22.12.2006, 17:26 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 17.12.2006

Репутация: нет
Всего: нет

Огромное вам спасибо!!!все понятно,что такое ренндом знаю smile

PrinceMike

Дата 24.12.2006, 17:50 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 184
Регистрация: 23.11.2006
Где: Москва

Репутация: нет
Всего: 1

Цитата(Silvery @ 18.12.2006, 21:35

)

В более поздних работах Хиббард показал

Цитата(PrinceMike @ 20.12.2006, 23:49

)

Хибборд и Шелл это идин и тот же чел? smile ну да ладно)

Терь понял) сначала не прочитал до конца)

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Object Pascal: кроссплатформенные технологии \| Следующая тема »