Иерархоческая сортировка

← →
Seleznew (2009-09-18 07:56) [0]

Доброго времени суток, мастера!

Вопрос по сортировке.
Есть массив в котом содержатся значения вида:
12
13
121
123
22
27
221
1211

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

12
121
1211
123
13
22
221
27

то есть каждый разряд содержит в себе все младшие разряды, нужно отсортировать по возрастанию.
Подскажите, как такое можно реализовать?

← →
Seleznew (2009-09-18 07:58) [1]

извините ошибся в названии темы:
Иерархическая сортировка

← →
MBo © (2009-09-18 08:13) [2]

Лексикографическое упорядочение - проще всего сортировать строковые представления.

← →
Seleznew (2009-09-18 08:39) [3]

Спасибо! А не подскажите, где почитать про реализацию на delphi?

← →
MBo © (2009-09-18 08:59) [4]

да что там - загнать все числа (переводя в строки) в TStringList и использовать его встроенную сортировку

← →
Seleznew (2009-09-18 09:03) [5]

а в память такой метод не упрется? О_о

← →
Сергей М. © (2009-09-18 09:08) [6]

> в память такой метод не упрется?

А массив у тебя в память не уперся ?

← →
Seleznew (2009-09-18 09:09) [7]

почти на грани.
только я читал где-то что сорт стринглистовский отжирает много памяти...

← →
Сергей М. © (2009-09-18 09:18) [8]

> почти на грани

И откуда к тебе такой граненый массив свалился, можно полюбопытствовать ?

> сорт стринглистовский отжирает много памяти

Глупостей ты начитался)

← →
MBo © (2009-09-18 09:18) [9]

>сорт стринглистовский отжирает много памяти
нет, не отжирает

Только если у тебя сотни миллионов чисел и соответственно строк - то список строк в памяти, конечно, будет больше места занимать, чем числа.
Каковы реальные количества чисел?

← →
palva © (2009-09-18 09:48) [10]

Для таких массивов сразу хочется реализовать поразрядную сортировку.

← →
Anatoly Podgoretsky © (2009-09-18 11:03) [11]

> Для таких массивов сразу хочется реализовать поразрядную
> сортировку.

А это и будет строковая, лексикографическая сортировка, а с числами возможна только двоичная поразрядная.

← →
palva © (2009-09-18 16:12) [12]

Если хочется, то почему бы не сделать? (Как говорят в среде питерских, пацан сказал - пацан сделал.)
Сортирует она лексикографически, но в коде нет сравнений.
Ну там есть пара сравнений технического характера, но они возникают из-за того, что строки имеют различную длину.
{$APPTYPE CONSOLE} const arsize = 7; numrazr = 3; type TArr = array [0..arsize-1] of string; var ar: TArr = ("12","13","124","123","28","27","121"); artemp: array [Boolean] of TArr; arnum: array["/".."9"] of Integer; b, nb: Boolean; c: Char; r, i: integer; begin b := False; artemp[b] := ar; for r:=numrazr downto 1 do begin // Подсчет for c:="/" to "9" do arnum[c]:=0; for i:=0 to arsize-1 do begin if r <= Length(artemp[b][i]) then c:=artemp[b][i][r] else c:="/"; Inc(arnum[c]); end; for c:="0" to "9" do arnum[c]:=arnum[c]+arnum[Pred(c)]; for c:="9" downto "0" do arnum[c]:=arnum[Pred(c)]; arnum["/"] := 0; // Перенос nb := not b; for i:=0 to arsize-1 do begin if r <= Length(artemp[b][i]) then c:=artemp[b][i][r] else c:="/"; artemp[nb][arnum[c]] := artemp[b][i]; Inc(arnum[c]); end; b := nb; end; ar := artemp[b]; for i:=0 to arsize-1 do Write(" ", ar[i]); WriteLn; readln; end.

← →
palva © (2009-09-18 16:23) [13]

На Delphimaster есть статья, посвященная поразрядной сортировке
http://www.delphimaster.ru/articles/dsort/index.html
Но реализация там другая.

← →
новый (2009-09-18 16:31) [14]

> И откуда к тебе такой граненый массив свалился, можно полюбопытствовать
> ?

выгрузка из билинговой системы.

> Каковы реальные количества чисел?

ну соответственно откуда куда может позвонить человек в пределах одного оператора связи.

> Если хочется, то почему бы не сделать?

Спасибо! буду тестить... В принципе за весь день начитался всякого и что-то такое уже крутилось в голове... Только оно не успело оформиться вот в такую законченную форму)) Только я думал при заполнении массива задаться определенной максимальной длинной и дописывать нули в начало строки....

← →
новый (2009-09-18 16:36) [15]

Или я не прав? Сергей это же Вы? прошу прощения что невольно вмешался в дискуссию... Ник Ваш довольно приметен.. решил отблагодорить коллег за Вас :Р

← →
Alx2 © (2009-09-18 16:41) [16]

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

PS
Поразрядную, при заявленном дефиците памяти, подобрать трудно будет - в качестве вспомогательной нужна т.н. сохраняющая порядок сортировка, не требующая O(n) дополнительной памяти. Но если получится - на огромных количествах будет быстрее, конечно, чем quickSort или ее родственники, которые для сортировки используют только сравнения.

← →
Alx2 © (2009-09-18 16:44) [17]

>а перед сравнением дописывать нули

Или сделать это предварительно, на шаге предобработки, если не жалко данных.

← →
Alx2 © (2009-09-18 16:45) [18]

Черт. Один опечатки:

>дописывать нули слева
Справа, конечно :)

← →
Anatoly Podgoretsky © (2009-09-18 16:52) [19]

> Alx2 (18.09.2009 16:45:18) [18]

И потом решать как и сколько удалять

← →
Seleznew (2009-09-18 16:54) [20]

Прошу прощения за оффтоп...
Но тут имеет место некоторое нарушение этикета.
Товарищ новый! Я бы попросил Вас впредь не следить за моими ветками, а разбираться со своими тараканами! У нас с Вами был уговор: честное выполнение проекта. Кто раньше успеет тому и заказ. Я не знаю каким образом вы прознали про сей достойный форум, но если шпионите, то хотя-бы делали бы это тихо!!! И еще: Уважаемый конкурент!!!! Я бы не стал на Вашем месте трубить на весь интернет про этот проект. Имхо заказчик будет недоволен...

Уважаемая администрация! если этот и предыдущие посты нарушают правила форума, прошу удалить их или закрыть ветку. Еще раз спасибо всем откликнувшимся.

← →
palva © (2009-09-18 16:54) [21]

Дописывать нули (справа, естественно) чревато следующим: строки
123
1230
123
1230
сохранят свой порядок, тогда как по логике вещей первая и третья строки меньше, чем вторя и четвертая. Хотя возможно, что по смыслу задачи это не принципиально.

← →
Seleznew (2009-09-18 16:59) [22]

palva ©

> Дописывать нули (справа, естественно) чревато следующим...

ну насколько мне известно (хотя это надо будет проверить) одинаковых входных значений быть там не может. точно так же как и нулей.

← →
Seleznew (2009-09-18 17:01) [23]

А нет. нули есть. одинаковых значений нет.

← →
Alx2 © (2009-09-18 17:08) [24]

>Anatoly Podgoretsky © (18.09.09 16:52) [19]

А... Если важно не запороть данные, то нули лепить только на этапе сравнения.
Типа:
if valueExpandedWithZeros(a[k])>valueExpandedWithZeros(a[l]) then ...

palva © (18.09.09 16:54) [21]

Точно :( Я не учел, что ноль тоже имеет значение. Тогда ой.

← →
palva © (2009-09-18 17:11) [25]

Поразрядная сортировка требует два массива дополнительной памяти равновеликие исходному массиву (при усложнении алгоритма можно обойтись одним массивом) и целый массив размера равного мощности одного разряда. Время сортировки линейно зависит от длины массива и от длины ключа. Приведенный мной алгоритм используется как основной рабочий алгоритм для внутренней сортировки в СУБД ADABAS (на IBM 360).

← →
palva © (2009-09-18 17:15) [26]

У меня строка как бы дополняется символами "/" код которых на единицу меньше чем код символа "0".

← →
Seleznew (2009-09-18 17:35) [27]

я тут катался под столом)
Вы тут типо уже на меня забили все и промеж собой пробавляетесь???

← →
palva © (2009-09-18 17:38) [28]

А делать-то нечего... работы нет... кризис...

← →
Seleznew (2009-09-18 17:39) [29]

ага

>Seleznew (18.09.09 17:39) [29]

Сорри. Тут довольно часто удовлетворенность автора топика задвигается куда подальше, а вот поднятая тема долго еще торкает :)

← →
Seleznew (2009-09-18 19:18) [31]

ну... я помню... Правда когда мне этот форум помогал осваивать d, тут были совсем другие порядки)))

← →
Seleznew (2009-09-19 08:28) [32]

Может все таки подскажите идею алгоритма с числами без сравнений?

А о каком алгоритме речь? У вас же строки, а не числа. Вы хотите предварительно преобразовать в строки, что ли? Если строки состоят только из цифр, то их можно представить в виде чисел. Если каждая строка не слишком велика, скажем, до 9 цифр, то для представления строки подойдет тип Integer. Этот тип можно эффективно сравнивать одной процессорной командой. И зачем тогда алгоритм без сравнений? Кроме того, вы потратите время на преобразование туда и обратно. Будет ли это быстрее, чем просто загрузить массив в StringList и применить Sort - не знаю. Если у вас проблемы с памятью, то полезнее подумать об экономном формате массива. Например, использовать строки для хранения десятичных цифр довольно неэкономно. Простой переход к хранению двух цифр в одном байте уже даст экономию.

размер массива до сих пор не озвучен...

← →
Seleznew (2009-09-19 12:24) [35]

> размер массива до сих пор не озвучен...

65536*(+/-)200-250

> У вас же строки, а не числа

дело в том, что у меня как я выгружу так и будет....
вот функции которые я могу использовать:
.valueAsString
.valueAsInteger
.valueAsReal
.valueAsDouble
.valueAsDWord
.valueAsWord

Ну думаю пояснений не надо...

> [35] Seleznew (19.09.09 12:24)
> > У вас же строки, а не числа
>
> дело в том, что у меня как я выгружу так и будет....
>
> Ну думаю пояснений не надо...

Надо. Нафиг там строки, если это числа ещё и целые видимо?

Возможные решения:

Время работы O(n*log(n)), затраты памяти O(log(n)) - алгоритмы семейства quickSort

Время работы O(n*log(Max-Min)), затраты памяти O(log(Max-Min)) -
алгоритмы семейства поразрядной сортировки.
Растотчительность на памяти порядка O(n) в radixSort достаточно лего фиксится.

Время работы O(n*log(n)), затраты памяти O(1) -
алгоритмы семейства heapSort

Осталось узнать критерий.
Так как размеры массива оказались и не такие большие, то:
Если элементы массивы сильно разнородные - рекомендую quickSort
Если мало отличаются друг от друга (мала разница максимального и минимального) - то "спецзаточенный" radixSort (соединить идеи quickSort с raidxSort). Кол-во проходов по массиву в нем можно сделать равным количеству разрядов в двоичном представлении разности Max-Min. Память кушать можно не больше, чем в quickSort.

> Inovet (19.09.2009 13:57:36) [36]

Да какие там числа, если
только по недоразумению.
Это обычные идетификаторы,
типа номеров счетов или
телефонных номеров, по
природе строки.

"Inovet" <anvas@fromru.com>
сообщил/сообщила в
новостях следующее:
news:1253246214.36@delphimaster.ru...
Inovet © (19.09.2009 13:57) [36]
> [35] Seleznew (19.09.09 12:24)
> > У вас же строки, а не
числа
>
> дело в том, что у меня как я
выгружу так и будет....
>
> Ну думаю пояснений не
надо...

Надо. Нафиг там строки,
если это числа ещё и целые
видимо?

> > И откуда к тебе такой граненый массив свалился, можно
> полюбопытствовать > ?выгрузка из билинговой системы.

почему-то жалко провайдера услуг
а впрочем пофиг - сам сэкономил на программистах- сам дураг

> [38] Anatoly Podgoretsky © (19.09.09 20:46)
> > Inovet (19.09.2009 13:57:36) [36]
>
> Да какие там числа, если только по недоразумению.
> Это обычные идетификаторы, типа номеров счетов или телефонных номеров, по природе строки.

Вообще-то да, похоже. Только вот функции смущают из

> [35] Seleznew (19.09.09 12:24)

Иерархоческая сортировка Найти похожие ветки