сортировка строк

← →
Infinityx93 © (2007-06-07 01:11) [0]

Есть около 70000 строк надо отсортировать, желательно побыстрее.
использовал пузырек слишком долго, шелла быстро но сортирует криво =(,
слиянием так и не получилось, подскажите плз какой нить способ сортировки.

З.Ы.
строки в основном повторяются, поэтому метод быстрой сортировки не использовал.

← →
MBo © (2007-06-07 07:04) [1]

Вот рабочий ShellSort для целых, на строки сам переделаешь

procedure ShellSort(var A: array of Integer; l, r: Integer); var i, j: integer; h: integer; Temp: Integer; Ninth: integer; begin h := 1; Ninth := (r - l) div 9; while (h <= Ninth) do h := (h * 3) + 1; while (h > 0) do begin for i := (l + h) to r do begin Temp := A[i]; j := i; while (j >= (l + h)) and (Temp < A[j - h]) do begin A[j] := A[j - h]; dec(j, h); end; A[j] := Temp; end; h := h div 3; end; end;

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

Есть модификации быстрой сортировки, которые хорошо справляются со множеством дубликатов. Однако для указанного количества shellsort не сильно хуже.

← →
Loginov Dmitry © (2007-06-07 11:39) [2]

Используй TStringList. В нем уже реализован QuickSort.

← →
Сергей М. © (2007-06-07 13:23) [3]

> Loginov Dmitry © (07.06.07 11:39) [2]

> В нем уже реализован QuickSort.

Ты чем слушал ?)

← →
Loginov Dmitry © (2007-06-07 13:48) [4]

> Ты чем слушал ?)

Я читал, а не слушал...
А про QuickSort упомянул так... к слову. Авось все-таки поможет. Нет - так нет...

> Я читал, а не слушал

Долго же ты читал)

За это время фразу Автора про "строки в основном повторяются" можно было изучить вдоль и поперек)

В TStringList реализация сортировки вполне достойная и, видимо, не боится дубликатов

var t: DWord; sl: TStringList; i, j: Integer; s: string; begin Randomize; sl := TStringList.Create; SetLength(s, 60); for i := 1 to 300000 do begin for j := 1 to 60 do s[j] := Chr(32 + Random(96)); sl.Add(s); //1// почти уникальные строки // sl.Add(StringOfChar(Chr(65 + Random(26)), 60)); //2// всего 26 разных строк end; t:= GetTickCount; sl.Sort; Caption := IntToStr(GetTickCount - t) + " " + sl[0]; sl.Free;

время выполнения случая //1// почти такое же, как //2 (с закомментированной строкой //1 )

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