VPF::Сортировка сложностью n - Форум программистов

Pori

Дата 16.9.2007, 19:44 (ссылка)

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

Загрузка ...

Шустрый

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

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

Слышал от знакомого про сортировку n-ой степени, он даже мне объяснял алгоритм
Но было уже это давно и я забыл(
Подскажите пожалуйста таковой

Void

Дата 16.9.2007, 19:55 (ссылка)

(голосов:1)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

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

Что такое «сортировка сложностью n» и «сортировка n-й степени»? Если имеется сортировка сложностью O(n), то в общем случае она невозможна, но для некоторых видов данных достижима, например, поразрядная сортировка.

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

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

Pori

Дата 16.9.2007, 20:11 (ссылка)

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

Загрузка ...

Шустрый

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

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

да сортировка сложностью O(n)

esperant0

Дата 17.9.2007, 23:48 (ссылка)

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

Загрузка ...

Опытный

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

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

да на квантовом компьютере можно

и на машине тьюринга с оракулом можно.

и не недетеменистической машине тьюринга можно

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

Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer

Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором а затем стерто и которое он - пользователь не мог видеть.

JackYF

Дата 18.9.2007, 00:01 (ссылка)

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

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

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

угу. А если курнуть, то задача вообще становится настолько тривиальной, что её и решать уже не надо...

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

Пожаловаться на меня как модератора можно здесь.

stg34

Дата 30.9.2007, 12:42 (ссылка)

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

Загрузка ...

Новичок

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

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

Есть такие
Сортировки
Смотри:
1. Сортировка подсчётом
2. Цифровая сортировка
3. Поразрядная сортировка

4d5a

Дата 21.10.2007, 20:01 (ссылка)

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

Загрузка ...

Новичок

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

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

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

Все вообе-то Сортировка подсчётом (не в полной мере) и Цифровая сортировка это грани одной и той же идеи : Не сравнивать элементы а распределять ну типа сделать упрор не на код а на структуру данных. И эта идея нормально реализуется в методе поразрядной сортировки.

Короче это : http://algolist.manual.ru/sort/radix_sort.php то что тебе надо (примеры на C)
А Это простейший случай : элементы массива состоят из одной цифры на паскале

Код



const n=10
type tdim=array[1..n] of integer;

procedure rx01(var A:tdim);
var n,i,c,s:integer;
    count:array [0..9] of integer;
    D:tdim;
begin
  n:=cLen;
  for i:=0 to 9 do  // 1 обнуляем
    count[i]:=0;
  for i:=1 to n do // 2 считаем счетчики
    Inc(count[A[i]]);
  s:=0;
  for i:=0 to 9 do // 3 суммируем для нахождения позиции
  begin
    c:=count[i];
    count[i]:=s;
    s:=s+c;
  end;
  for i:=1 to n do // 4 расставляем
  begin
    c:=A[i];
    D[count[c]+1]:=c;
    Inc(count[c]);
  end;
  for i:=1 to n do // 5 копируем
    A[i]:=D[i];
end;

А вот нормальную реализацию писал на паскале
любой размер типа, беззнаковые целые (конечно соглашусь на C это выглядит намного лаконичнее)

Код


unit sort04;

{
  
  sort04.pas 
  coded by mz

  RSUI radix sort in one proc
  for unsigned int, any type size.
  
}

interface
uses sort07;

procedure RSUI(src:pointer;st,N:tint);

implementation

procedure FillByte(data:pointer;b:byte;count:longint);
var i:integer;
begin
  for i:=0 to count-1 do
    pbyte(longint(data)+i)^:=b;
end;

function CopyMem(Src,Dst:pointer;count:longint):longint;
var i:longint;
begin
  for i:=0 to count-1 do
    PByte(longint(Dst)+i)^:=PByte(longint(Src)+i)^;
  CopyMem:=i;
end;

procedure RSUI(src:pointer;st,N:tint);
var out,sp,counters,count,old:pointer;
    i,j,s,c:tint;
    cp:pint;
    bp,dataEnd:Pbyte;
begin
  old:=src;
  GetMem(out,N*st);
  GetMem(counters,256*sizeof(tint)*st);
  FillByte(counters,0,256*sizeof(tint)*st);
  bp:=pointer(src);
  dataEnd:=pointer(lint(src)+st*N);
  while (bp<>dataEnd) do
    for j:=0 to st-1 do
    begin
      cp:=pointer(lint(counters)+ (256*j+bp^)*sizeof(tint) );
      Inc(cp^);
      Inc(Lint(bp));
    end;
  for i:=0 to st-1 do
  begin
    count:=pointer(lint(counters)+256*i*sizeof(tint));
    if (pint(count)^=N) then continue;
    cp:=count;
    s:=0;
    for j:=1 to 256 do
    begin
      c:=cp^;
      cp^:=s;
      s:=s+c;
      Inc(lint(cp),sizeof(tint));
    end;
    bp:=pointer(Lint(src)+i);
    sp:=src;
    for j:=1 to N do
    begin
      cp:=pointer(lint(count)+bp^*sizeof(tint));
      copyMem(sp,pointer(lint(out)+cp^*st),st);
      Inc(cp^);
      Inc(LInt(sp),st);Inc(Lint(bp),st);
    end;
    swap(src,out);
  end;
  if (out=old) then
  begin
    CopyMem(src,out,st*N);
    swap(src,out);
  end;
  FreeMem(counters,256*sizeOf(tint)*st);
  FreeMem(out,st*N);
end;

end.

RSUI использовать так

Код



const 
 maxL=($FFFF div 4)-1;

type
 lint=longint; 
 la=array[0..maxL] of lint;
 pla=^la;

var
  A:pla;
  n,i:integer;
  sz:byte;

begin
  randomize;
  n:=10;
  sz:=sizeof(lint);
  GetMem(A,n*sz);
  for i:=0 to n-1 do
    A^[i]:=random(1000);
  writeln('rs sort');
  for i:=0 to n-1 do
    write(A^[i],' ');
  writeln;
  RSUI(pointer(A),sz,n);
  for i:=0 to n-1 do
    write(A^[i],' ');
  readln;
  FreeMem(A,n*sz);
end.

Вот.

esperant0

Дата 21.10.2007, 20:05 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(stg34 @ 30.9.2007, 12:42)

Есть такие
Сортировки
Смотри:
1. Сортировка подсчётом
2. Цифровая сортировка
3. Поразрядная сортировка

И вы уверене что ЛЮБЫЕ данные можно отсортировать вашими алгоритмами?

Если нет, то можно отсортированный массив и моментально отсортировать.

Добавлено через 1 минуту и 25 секунд

Цитата(4d5a @ 21.10.2007, 20:01)

В простейшем случае два: распределение-сборка те грубо говоря (2n)

2п? Нет конечно.

nlogk

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

4d5a

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

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

Загрузка ...

Новичок

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

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

2esperant0 да nlogk, но
А я и не писал "O" от .. smile

2n - имел ввиду два прохода для списков

Добавлено через 1 минуту и 27 секунд
и я приписал еще "грубо говоря", короче чистой воды абстракция

Добавлено через 10 минут и 52 секунды

Цитата

И вы уверене что ЛЮБЫЕ данные можно отсортировать вашими алгоритмами?

В смысле 'ЛЮБЫЕ' ? Если алгоритм есть значит он работет - > сортирует, вопрос в том КАК

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