| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Иерархоческая сортировка
Seleznew © (2009-09-18 07:56:00)Доброго времени суток, мастера!
Вопрос по сортировке.
Есть массив в котом содержатся значения вида:
12
13
121
123
22
27
221
1211
нужно отсортировать этот массив так, чтобы последовательность стала такой:
12
121
1211
123
13
22
221
27
то есть каждый разряд содержит в себе все младшие разряды, нужно отсортировать по возрастанию.
Подскажите, как такое можно реализовать?
Seleznew (2009-09-20 09:52:00) [1]спасибо тем кто откликнулся. Решение я нашел сам, но благодаря вам. самым оптимальным оказался совсем другой вариант. т.к. структура данных если присмотреться представляет из себя дерево, то на этапе загрузки я переношу значения КОДОВ НАПРАВЛЕНИЙ в дерево в виде строк, и дальше работаю с этим деревом. т.е. добавляю, убираю узлы, делаю выгрузку. при таком подходе необходимость в сортировке всего этого добра просто отпадает. Еще раз спасибо!
Seleznew (2009-09-20 09:46:00) [2]
> почему-то жалко провайдера услуг
это Вы конечно да. правы. .можете думать и говорить что хотите. только вот никакой это не провайдер это первое. мне НИЧЕГО не платят за этот проект это второе. ну и третье. это конкурс. на другой проект. такая программа которую я пытаюсь написать есть. и давно работает. только медленно. у кого результат будет быстрей, тот и проходит. да. я НЕ ПРОГРАММИСТ. я вообще к программированию по образованию таким далеким боком, что вам мастера и не снилось. математику, комбинаторику, статистику и проч я тоже изучал только дома только сам и только по книжкам. поэтому прошу впредь в мой адрес таких завуалированных оскорблений не слать.
Inovet (2009-09-19 21:19:00) [3]> [38] Anatoly Podgoretsky © (19.09.09 20:46)
> > Inovet (19.09.2009 13:57:36) [36]
>
> Да какие там числа, если только по недоразумению.
> Это обычные идетификаторы, типа номеров счетов или телефонных номеров, по природе строки.
Вообще-то да, похоже. Только вот функции смущают из
> [35] Seleznew (19.09.09 12:24)
СовестьДМ (2009-09-19 21:03:00) [4]
> > И откуда к тебе такой граненый массив свалился, можно
> полюбопытствовать > ?выгрузка из билинговой системы.
почему-то жалко провайдера услуг
а впрочем пофиг - сам сэкономил на программистах- сам дураг
Anatoly Podgoretsky (2009-09-19 20:46:00) [5]> 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)
> > У вас же строки, а не
числа
>
> дело в том, что у меня как я
выгружу так и будет....
>
> Ну думаю пояснений не
надо...
Надо. Нафиг там строки,
если это числа ещё и целые
видимо?
Alx2 (2009-09-19 14:38:00) [6]Возможные решения:
Время работы 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 (2009-09-19 13:57:00) [7]> [35] Seleznew (19.09.09 12:24)
> > У вас же строки, а не числа
>
> дело в том, что у меня как я выгружу так и будет....
>
> Ну думаю пояснений не надо...
Надо. Нафиг там строки, если это числа ещё и целые видимо?
Seleznew (2009-09-19 12:24:00) [8]
> размер массива до сих пор не озвучен...
65536*(+/-)200-250
> У вас же строки, а не числа
дело в том, что у меня как я выгружу так и будет....
вот функции которые я могу использовать:
.valueAsString
.valueAsInteger
.valueAsReal
.valueAsDouble
.valueAsDWord
.valueAsWord
Ну думаю пояснений не надо...
MBo (2009-09-19 10:22:00) [9]размер массива до сих пор не озвучен...
palva (2009-09-19 10:05:00) [10]А о каком алгоритме речь? У вас же строки, а не числа. Вы хотите предварительно преобразовать в строки, что ли? Если строки состоят только из цифр, то их можно представить в виде чисел. Если каждая строка не слишком велика, скажем, до 9 цифр, то для представления строки подойдет тип Integer. Этот тип можно эффективно сравнивать одной процессорной командой. И зачем тогда алгоритм без сравнений? Кроме того, вы потратите время на преобразование туда и обратно. Будет ли это быстрее, чем просто загрузить массив в StringList и применить Sort - не знаю. Если у вас проблемы с памятью, то полезнее подумать об экономном формате массива. Например, использовать строки для хранения десятичных цифр довольно неэкономно. Простой переход к хранению двух цифр в одном байте уже даст экономию.
Seleznew (2009-09-19 08:28:00) [11]Может все таки подскажите идею алгоритма с числами без сравнений?
Seleznew (2009-09-18 19:18:00) [12]ну... я помню... Правда когда мне этот форум помогал осваивать d, тут были совсем другие порядки)))
Alx2 (2009-09-18 17:44:00) [13]>Seleznew (18.09.09 17:39) [29]
Сорри. Тут довольно часто удовлетворенность автора топика задвигается куда подальше, а вот поднятая тема долго еще торкает :)
Seleznew (2009-09-18 17:39:00) [14]ага
palva (2009-09-18 17:38:00) [15]А делать-то нечего... работы нет... кризис...
Seleznew (2009-09-18 17:35:00) [16]я тут катался под столом)
Вы тут типо уже на меня забили все и промеж собой пробавляетесь???
palva (2009-09-18 17:15:00) [17]У меня строка как бы дополняется символами '/' код которых на единицу меньше чем код символа '0'.
palva (2009-09-18 17:11:00) [18]Поразрядная сортировка требует два массива дополнительной памяти равновеликие исходному массиву (при усложнении алгоритма можно обойтись одним массивом) и целый массив размера равного мощности одного разряда. Время сортировки линейно зависит от длины массива и от длины ключа. Приведенный мной алгоритм используется как основной рабочий алгоритм для внутренней сортировки в СУБД ADABAS (на IBM 360).
Alx2 (2009-09-18 17:08:00) [19]>Anatoly Podgoretsky © (18.09.09 16:52) [19]
А... Если важно не запороть данные, то нули лепить только на этапе сравнения.
Типа:
if valueExpandedWithZeros(a[k])>valueExpandedWithZeros(a[l]) then ...
palva © (18.09.09 16:54) [21]
Точно :( Я не учел, что ноль тоже имеет значение. Тогда ой.
Seleznew (2009-09-18 17:01:00) [20]А нет. нули есть. одинаковых значений нет.
| |
Страницы: 