| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / 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-18 16:59:00) [21]palva ©
> Дописывать нули (справа, естественно) чревато следующим...
ну насколько мне известно (хотя это надо будет проверить) одинаковых входных значений быть там не может. точно так же как и нулей.
palva (2009-09-18 16:54:00) [22]Дописывать нули (справа, естественно) чревато следующим: строки
123
1230
123
1230
сохранят свой порядок, тогда как по логике вещей первая и третья строки меньше, чем вторя и четвертая. Хотя возможно, что по смыслу задачи это не принципиально.
Seleznew (2009-09-18 16:54:00) [23]Прошу прощения за оффтоп...
Но тут имеет место некоторое нарушение этикета.
Товарищ новый! Я бы попросил Вас впредь не следить за моими ветками, а разбираться со своими тараканами! У нас с Вами был уговор: честное выполнение проекта. Кто раньше успеет тому и заказ. Я не знаю каким образом вы прознали про сей достойный форум, но если шпионите, то хотя-бы делали бы это тихо!!! И еще: Уважаемый конкурент!!!! Я бы не стал на Вашем месте трубить на весь интернет про этот проект. Имхо заказчик будет недоволен...
Уважаемая администрация! если этот и предыдущие посты нарушают правила форума, прошу удалить их или закрыть ветку. Еще раз спасибо всем откликнувшимся.
Anatoly Podgoretsky (2009-09-18 16:52:00) [24]> Alx2 (18.09.2009 16:45:18) [18]
И потом решать как и сколько удалять
Alx2 (2009-09-18 16:45:00) [25]Черт. Один опечатки:
>дописывать нули слева
Справа, конечно :)
Alx2 (2009-09-18 16:44:00) [26]>а перед сравнением дописывать нули
Или сделать это предварительно, на шаге предобработки, если не жалко данных.
Alx2 (2009-09-18 16:41:00) [27]>и дописывать нули в начало строки....
Имхо, если в массиве только числа (целые), то не дописывать нули в строку (в которую еще перегонять надо), а перед сравнением дописывать нули слева к меньшему числу, так чтобы разрядность (в десятичной системе) выровнять и затем - сравнивать.
PS
Поразрядную, при заявленном дефиците памяти, подобрать трудно будет - в качестве вспомогательной нужна т.н. сохраняющая порядок сортировка, не требующая O(n) дополнительной памяти. Но если получится - на огромных количествах будет быстрее, конечно, чем quickSort или ее родственники, которые для сортировки используют только сравнения.
новый (2009-09-18 16:36:00) [28]Или я не прав? Сергей это же Вы? прошу прощения что невольно вмешался в дискуссию... Ник Ваш довольно приметен.. решил отблагодорить коллег за Вас :Р
новый (2009-09-18 16:31:00) [29]
> И откуда к тебе такой граненый массив свалился, можно полюбопытствовать
> ?
выгрузка из билинговой системы.
> Каковы реальные количества чисел?
ну соответственно откуда куда может позвонить человек в пределах одного оператора связи.
> Если хочется, то почему бы не сделать?
Спасибо! буду тестить... В принципе за весь день начитался всякого и что-то такое уже крутилось в голове... Только оно не успело оформиться вот в такую законченную форму)) Только я думал при заполнении массива задаться определенной максимальной длинной и дописывать нули в начало строки....
palva (2009-09-18 16:23:00) [30]На Delphimaster есть статья, посвященная поразрядной сортировке
http://www.delphimaster.ru/articles/dsort/index.html
Но реализация там другая.
palva (2009-09-18 16:12:00) [31]Если хочется, то почему бы не сделать? (Как говорят в среде питерских, пацан сказал - пацан сделал.)
Сортирует она лексикографически, но в коде нет сравнений.
Ну там есть пара сравнений технического характера, но они возникают из-за того, что строки имеют различную длину.
{$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.
Anatoly Podgoretsky (2009-09-18 11:03:00) [32]
> Для таких массивов сразу хочется реализовать поразрядную
> сортировку.
А это и будет строковая, лексикографическая сортировка, а с числами возможна только двоичная поразрядная.
palva (2009-09-18 09:48:00) [33]Для таких массивов сразу хочется реализовать поразрядную сортировку.
MBo (2009-09-18 09:18:00) [34]>сорт стринглистовский отжирает много памяти
нет, не отжирает
Только если у тебя сотни миллионов чисел и соответственно строк - то список строк в памяти, конечно, будет больше места занимать, чем числа.
Каковы реальные количества чисел?
Сергей М. (2009-09-18 09:18:00) [35]
> почти на грани
И откуда к тебе такой граненый массив свалился, можно полюбопытствовать ?
> сорт стринглистовский отжирает много памяти
Глупостей ты начитался)
Seleznew (2009-09-18 09:09:00) [36]почти на грани.
только я читал где-то что сорт стринглистовский отжирает много памяти...
Сергей М. (2009-09-18 09:08:00) [37]
> в память такой метод не упрется?
А массив у тебя в память не уперся ?
Seleznew (2009-09-18 09:03:00) [38]а в память такой метод не упрется? О_о
MBo (2009-09-18 08:59:00) [39]да что там - загнать все числа (переводя в строки) в TStringList и использовать его встроенную сортировку
Seleznew (2009-09-18 08:39:00) [40]Спасибо! А не подскажите, где почитать про реализацию на delphi?
| |
Страницы: 