| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL | | Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

	« предыдущая ветвь | форум | следующая ветвь »

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

Infinityx93 ©   (2007-06-07 01:11:00) 

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

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

---

MBo   (2007-06-07 14:08:00) [1]

В 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 )

---

Сергей М.   (2007-06-07 13:52:00) [2]

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


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

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

---

Loginov Dmitry   (2007-06-07 13:48:00) [3]

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


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

---

Сергей М.   (2007-06-07 13:23:00) [4]

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



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


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

---

Loginov Dmitry   (2007-06-07 11:39:00) [5]

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

---

MBo   (2007-06-07 07:04:00) [6]

Вот рабочий 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 не сильно хуже.

---

Наверх