[aquatell]

Здравствуйте!
Ребята подскажите пожалуйста какой алгоритм будет являться самым быстрым для сортировки одномерного динамического массива записей на 1 млн строк.
Массив у меня динамический и размерность я устанавливаю в цикле, в результате он равен = 1 млн.

Код:

type
  X=Record
  Domain: String;
  ZoneDomain: String;
end; 

Var
Arr:array of X;
I:Integer;

Begin
// Устанавливаю размер
SetLength(Arr,1000000);

//Дальше заполняю вот так
 for i:=0 to 1000000 do
 begin
 Arr[AllStr].Domain:='доменное имя';
 Arr[AllStr].ZoneDomain:='доменная зона например com';
 end;
 end;
 { Теперь надо весь этот массив отсортировать по доменному имени, чтобы шли в алфавитном порядке.
 Алгоритм методом шела слишком медленный , а на другие не хватает опыта слишком сложные }

[lmikle]

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

Код:

var
  A : array ['a'..'z'] Of TList<X>;

[aquatell]

Применил очень шустрый алгоритм, один из быстрых.
Он так и называется "Быстрая сортировка".
1 млн записей сортирует за 3 сек. На 4-х ядерном процессоре 2,4 Ghz
Другие алгоритмы очень долго с этим справляются - в частности "пузырьком" и "вставкой", они хороши для меньшего количества записей.
Собственно вот сам код алгоритма "Быстрая сортировка", может многим пригодится

Код:

{Сортировка QuickSort}

procedure QuickSort(var data: array of double);

procedure QSort(var b: array of double; iLo, iHi: Integer);

var

   Lo, Hi: Integer;

   Mid, t: double;

begin

   Lo := iLo;

   Hi := iHi;

   Mid := b[(Lo + Hi) div 2];

   repeat

     while b[Lo] < Mid do Inc(Lo);

     while b[Hi] > Mid do Dec(Hi);

     if Lo <= Hi then

     begin

       t := b[Lo];

       b[Lo] := b[Hi];

       b[Hi] := t;

       Inc(Lo);

       Dec(Hi);

     end;

   until Lo > Hi;

   if Hi > iLo then QSort(b, iLo, Hi);

   if Lo < iHi then QSort(b, Lo, iHi);

end;

begin

QSort(data, Low(data), High(data));

end;

[poli-smen]

Сообщение от aquatell

Применил очень шустрый алгоритм, один из быстрых.
Он так и называется "Быстрая сортировка".
1 млн записей сортирует за 3 сек. На 4-х ядерном процессоре 2,4 Ghz
Другие алгоритмы очень долго с этим справляются - в частности "пузырьком" и "вставкой", они хороши для меньшего количества записей.
Собственно вот сам код алгоритма "Быстрая сортировка", может многим пригодится

Это слишком известный алгоритм чтобы о нём не знать. Например в стандартных классах TStringList и TList методы Sort используют именно быструю сортировку. Кроме того в стандартной поставке Delphi в папке "Demos\Threads" есть пример использования потоков (thread) и плюс скорости работы разных алгоритмов сортировки (пузырьковая, выбором и быстрая).

[aquatell]

Сообщение от poli-smen

Это слишком известный алгоритм чтобы о нём не знать.

Теперь уже буду знать, я просто узнаю о некоторых вещах по мере необходимости, даже если никогда не сталкивался с подобным, стараюсь разобраться, до сих пор мне не требовались подобные алгоритмы