Задачка

← →
default © (2006-08-21 09:32) [0]

"Дан массив, содержащий некоторую перестановку чисел 0.. N-1
Отсортировать его за О(N) операций и с O(1) доп. памяти."
когда-то была предложена MBo
решение у меня её есть(для проверки вашего)
так решать её нельзя: for i := 0 to High(A) do A[i] := i;
ибо подразумевается, что сортироваться могут записи, ключ сортировки которых как раз такое число
задача в принципе имеет практическую ценность
например, сортировка записей о всех жителях дома с полем номера квартиры(жители одной квартиры представляют одну запись)

← →
Vendict © (2006-08-21 19:22) [1]

default © (21.08.06 9:32)
можно с O(N) дополнительной памяти за O(N) время - цифровая сортировка.
Есть же теорема в книжке "Алгоритмы. Построение и анализ" что осортировать быстрее чем за O(nlogn) невозможно.
Цифровая сортировка отдельно, но там используется O(max)
(где max - наибольшее число) памяти.
Интересно, решаема ли твоя задача...

← →
default © (2006-08-21 19:48) [2]

Vendict © (21.08.06 19:22) [1]
я её решил минут за 40(возможно потому, что раньше решал задачи со сходной идеей), так что решаема

← →
MBo © (2006-08-21 19:58) [3]

>то осортировать быстрее чем за O(nlogn) невозможно
Это для универсальных сортировок, основанных на сравнениях.
В данном же случае есть особые условия, которые позволяют уложиться в указанные ограничения.

← →
Vendict © (2006-08-21 21:38) [4]

default © (21.08.06 19:48) [2]
значит ты будешь ждать пока кто-нибудь ещё решит ? интересно знать окончание ветки. мне самому думать влом.
MBo © (21.08.06 19:58) [3]
универсальных сортировок, основанных на сравнениях.
да да. совсем забыл. а разве можно без сравнения ?

← →
DillerXX © (2006-08-21 21:41) [5]

> да да. совсем забыл. а разве можно без сравнения ?

Читаем с-ва перестановки. И тем более цифровой метод (или как называется?) тоже без сравнения. Точнее только сравнение с 0 кажой ячейки в конце происходит.

← →
Ketmar © (2006-08-21 22:00) [6]

> [5] DillerXX © (21.08.06 21:41)
кажется, RadixSort называется. когда-то отлично использовался мной в 3d-интрушках на асме под DOS. %-)

← →
default © (2006-08-21 22:07) [7]

Vendict © (21.08.06 21:38) [4]
ну да
есть на этом форуме люди которым такие задачи интересны
например, SergP, порой такие финты выдаёт:)

← →
guav © (2006-08-21 22:25) [8]

> так решать её нельзя: for i := 0 to High(A) do A[i] := i;

А так можно ?
for i := 0 to High(A) do Result[A[i]] := A[i];

← →
SergP © (2006-08-21 23:11) [9]

> [8] guav © (21.08.06 22:25)
> > так решать её нельзя: for i := 0 to High(A) do A[i] :=
> i;
>
> А так можно ?
> for i := 0 to High(A) do Result[A[i]] := A[i];

не выполняется условие (выделенное жирным)

> Отсортировать его за О(N) операций и с O(1) доп. памяти.

ИМХО так должно быть:

for i:=0 to N-1 do begin k:=a[a[i]]; a[a[i]]:=a[i]; a[i]:=k; end;

← →
default © (2006-08-21 23:13) [10]

guav © (21.08.06 22:25) [8]
"и с O(1) доп. памяти."

← →
default © (2006-08-21 23:17) [11]

SergP © (21.08.06 23:11) [9]
неа, подумай, ты не такие задачи решал:) эта фигня почти-что

← →
guav © (2006-08-21 23:49) [12]

i := 0; for i := 0 to High(A) do begin j := A[i]; while j <> i do begin k := A[j]; A[j] := j; j := k; end; end;

← →
default © (2006-08-22 00:00) [13]

guav © (21.08.06 23:49) [12]
ход мысли верен
есть ошибка(думаю по невнимательности)

Думаю ошибка в условии внутреннего цикла
i := 0; for i := 0 to High(A) do begin j := A[i]; while A[i] <> i do begin k := A[j]; A[j] := j; j := k; end; end;

> [11] default © (21.08.06 23:17)
> SergP © (21.08.06 23:11) [9]
> неа, подумай, ты не такие задачи решал:) эта фигня почти-
> что

После того как запостил и сам увидел что фигня... Но здесь сообщения редактировать нельзя.. :-)

guav © (22.08.06 00:11) [14]
верно, почти один в один
procedure HyperSort(var A: Array of Cardinal); var i, j, t: Cardinal; begin for i := 0 to High(A) do begin j := A[i]; while i <> A[i] do begin t := A[j]; A[j] := j; j := t; end; end; end;
SergP © (22.08.06 09:34) [15]
я имел ввиду фигня про сложность задачи:)

Попробую то же самое на великом и могучем русском языке.

Просматриваем массив с начала. Если все время a[i] = i, то все элементы на своем месте и ничего делать не надо. Но вот встретился первый элемент для которого a[i] <> i, скажем, a[k]. Вынимаем его из массива, в массиве остается дыра. Вынутый элемент должен находиться на a[k] месте. Но это место занято каким-то другим элементом a[a[k]], который явно находится не на своем месте, поскольку в противном случае он был бы равен a[k], а мы знаем что в массиве нет одинаковых элементов. Так что элемент a[a[k]] вынем, а на его место вставим элемент a[k]. В результате количество элементов на своем месте увеличится на один, а вынутый элемент изменит свое значение. Далее найдем место для нового вынутого элемента и т. д. До бесконечности это продолжаться не может, поскольку число элементов не на своем месте все время уменьшается, и в конце-концов мы обнаружим, что очередной вынутый элемент претендует на место, занятое дырой с индексом k. Закроем эту дыру и продолжим последовательный просмотр массива в поисках элементов не на своем месте.

← →
SergP. (2006-08-22 10:52) [18]

> procedure HyperSort(var A: Array of Cardinal);
> var
> i, j, t: Cardinal;
> begin
> for i := 0 to High(A) do begin
> j := A[i];
> while i <> A[i] do begin
> t := A[j];
> A[j] := j;
> j := t;
> end;
> end;
> end;

Біла у меня такая мысль, но почему-то первоначально показалось, что
условите Отсортировать его за О(N) не выполняется из-за вложенных циклов. Хотя на самом деле в принципе оно все-таки выполняется

offtopic
palva © (22.08.06 10:23) [17]
Вы вроде бы знакомы с C#?
будет время загляните сюда http://delphimaster.net/view/13-1156238574/

Задачка Найти похожие ветки