VPF::[Delphi] Адресная сортировка - Форум программистов

ftp27host

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

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

Загрузка ...

Новичок

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

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

Напишите, пожалуйста, пример адресной сортировки. По скудным описаниям в интернете никак не пойму как она вообще работает :(

THandle

Дата 27.8.2010, 13:45 (ссылка)

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

Загрузка ...

Хранитель Клуба
Group Icon

Награды: 1

Профиль
Группа: Админ
Сообщений: 3639
Регистрация: 31.7.2007
Где: Moscow, Dubai

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

Для домашних заданий, курсовых, существует "Центр Помощи".

Тема перенесена!

Добавлено через 32 секунды
ftp27host, а можешь дать хоть какое то описание данной сортировки?

kemiisto

Дата 27.8.2010, 14:04 (ссылка)

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

Загрузка ...

Дикий Кот. =^.^=

Награды: 1

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

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

Возможно речь идёт о сортировке вставками (Insertion sort). Или есть ещё Multiple Link List Sort. Там тоже для каждого элементам вычисляется его адрес в отсортированном массиве.

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

XMPP-канал.

Unit testing isn't enough. You need static typing.

Пей, кури, пиши на си! smile

ftp27host

Дата 31.8.2010, 23:26 (ссылка)

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

Загрузка ...

Новичок

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

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

Цитата

Вот про адресную сор-ку:используется для целых чисел не очень большого диапазона. Идея сортировки: для каждого элемента массива определить количество элементов меньше его находящихся в данном массиве, после чего поместить этот элемент на соответствующее место. Сор-ка проходит следующим образом: за линейный проход для каждого значения подсчитываем сколько раз он втречается в данном массиве, затем определяем сумму всех предыдущих элементов и таким образом получаем позицию для вставки соответствующего элемента (опять за линейный прход). Необходимо следить, чтобы 2 одинаковых эл-та не были записаны на одно и то же место.

Код


var mas: array [0..n] of byte;
a: array [byte] of o..n;
for i:= 0 to n do a[mas[i]] :=a[mas[i]]+1;
k:=0;
s:=0;
for i:=0 to 255 do
if a[i] <>0 then
begin
s:=s+a[i];
while k+1<>s do begin k:=k+1;
mas[k]:=i;
end;
end.

kemiisto

Дата 1.9.2010, 00:16 (ссылка)

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

Загрузка ...

Дикий Кот. =^.^=

Награды: 1

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

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

Ну, если допустить, что описание дурацкое, то это сортировка подсчётом (Counting sort).

Код


PROGRAM Sort;

CONST
  n = 8;
  k = 100;

TYPE
  IntegerArray = ARRAY [0..n-1] OF INTEGER;

PROCEDURE Fill(var a: IntegerArray);
BEGIN
  a[0] := 44;
  a[1] := 55;
  a[2] := 12;
  a[3] := 42;
  a[4] := 94;
  a[5] := 18;
  a[6] := 06;
  a[7] := 67;  
END;  
  
PROCEDURE Print(a: IntegerArray);
VAR
  i: INTEGER;
BEGIN
  FOR i := 0 TO n - 1 DO
    Write(a[i], ' ');
  Writeln;
END;  

PROCEDURE CountingSort(VAR a: IntegerArray);
VAR
  i, j, b: INTEGER; 
  c: ARRAY [0..k-1] OF INTEGER;
BEGIN
  FOR i := 0 TO n - 1 DO
    c[i] := 0;
  FOR i := 0 TO n - 1 DO
    Inc(c[a[i]]);
  b := 0;
  FOR j := 0 TO k - 1 DO
    FOR i := 0 TO c[j] - 1 DO
    BEGIN
      a[b] := j;
      b := b + 1;
    END;
END;

VAR ia: IntegerArray;
  
BEGIN
  Fill(ia);
  Print(ia);
  CountingSort(ia);
  Print(ia);
END.

Это сообщение отредактировал(а) kemiisto - 1.9.2010, 00:18

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

XMPP-канал.

Unit testing isn't enough. You need static typing.

Пей, кури, пиши на си! smile

ftp27host

Дата 1.9.2010, 12:46 (ссылка)

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

Загрузка ...

Новичок

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

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

Спасибо, kemiisto. Немного переделал и все сработало.
p.s. Какой нерациональный алгоритм >.>

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