Самый быстрый вид сортировки массива

[pu4koff]

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

Полностью согласен. Обычные выкладки из учебников. Все дружно забыли что человека интереует опыт сортировки строковых данных, а не чисел. Данные по сортировке чисел, ИМХО, топикстартеру известны.

Если паскаль/делфи и сортировка строк по длине, то тут и есть сортировка чисел. Если Си с сишными строками, то тут уже несколько сложнее будет, т.к. длина строки достаточно долго вычисляется. Опять же при сортировке требуется перестановка элементов. Перестановка указателей на строки вероятно будет быстрее, чем:

temp := str[i];
str[i] := str[k];
str[k] := temp;

[Stilet]

Есть технология Rush More - считаю что самая быстрая сортировка описана там.
Вот еще придумал такую сортировку, поскольку не знаю ее аналогов назвал ее методом индексов.

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs;

type
  TForm1 = class(TForm)
    procedure FormCreate(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;
  function q(a:array of int64):string;
var
  Form1: TForm1;

implementation

{$R *.dfm}
   //********** FUNCTION **********
  function q;
  var i:array of int64;k:integer;
  begin          result:='';
   for k:=0 to length(a) do begin
    if length(i)<a[k] then setlength(i, a[k]+1);
    i[a[k]]:=a[k];
   end;
    for k:=length(i)-2 downto 0 do if i[k]<>0 then
     result:=result+' '+inttostr(i[k]);
  end;
  //********** END FUNCTION ******  {}


procedure TForm1.FormCreate(Sender: TObject);

begin
  caption:=q([1,5,6,9,0,5,0,5,9999,0,2,3,0,2,6,0,2,3,0,3]);
end;

end.

Она правда ресурсоемкая в случае с большими числами, а если диапазон мал, воплне работает быстро.

Если кто знает аналог просьба показать.

[Arigato]

Stilet
Судя по идеи - вариант линейной сортировки (смотрите моё предыдущее сообщение). Вот только приведённый пример у меня не сработал.

[pu4koff]

Мне это несколько напомнило сортировку подсчетом. И почему я её всегда путаю с быстрой сортировкой... В универе неправильно её препод называл или я туплю)

[Stilet]

Поправил функу, там баги были

Судя по идеи - вариант линейной сортировки

Понял, дружище, так пускай и будет

Вот только приведённый пример у меня не сработал.

Должно работать. Поправленный код у меня норм работает.

Мне это несколько напомнило сортировку подсчетом.

Похоже.

[Altera]

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

Я никогда не парюсь с сортировка и всегда сортирую по алгоритму прямого выбора. Этот алгоритм я всегда активно пропагандирую и советую.
общий принцип такой:

for i:=1 to n-1 do
 for j:=i+1 to n do
  if m[i]<m[j] then <меняем их местами>

для задачи сортировки массива строк по длине этот алгоритм вполне подходит

Если бы это был такой хороший метод, то, наверное, не разрабатывали-бы алгоритм быстрой сортировки:

procedure Tmain_form.QSS(const list: tList; aFirst, aLast: integer; const aCompare: tCompareFunc);
var
L, R: integer;
pivot, temp: pointer;
begin
   while aFirst < aLast do
   begin
      pivot := list.list[(aFirst + aLast) div 2];
      L := aFirst - 1;
      R := aLast + 1;
      while True do
      begin
         repeat dec(R) until (aCompare(list.list[R], pivot) <= 0);
         repeat inc(L) until (aCompare(list.list[L], pivot) >= 0);

         if L >= R then break;

         temp := List.list[L];
         List.list[L] := List.list[R];
         List.list[R] := temp;
      end;

      if aFirst < R then
         QSS(list, aFirst, R, aCompare);

      aFirst := R + 1;
   end;
end;

Это из книги Бакнелл Джулиан - Фундаментальные алгоритмы и структуры данных в Delphi

Вообще советую почитать, там интересные вещи написаны.

[Stilet]

Altera

Идеальных алгоритмов не бывает.
Бывают оптимальные решения для конкретно поставленной задачи.

[Altera]

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

Идеальных алгоритмов не бывает.
Бывают оптимальные решения для конкретно поставленной задачи.

Та написано, в той книге, что это алгоритм используют повсеместно, в том числе и в Delphi.

[pu4koff]

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

Та написано, в той книге, что это алгоритм используют повсеместно, в том числе и в Delphi.

Ну на заборе тоже много чего написано. На десяти элементах этот алгоритм будет не самый эффективный. Опять же можно сделать быстрее сортировку, но памяти больше дополнительной потребуется. Или у нас массив будет наполовину отсортированный уже - тут уже другой алгоритм лучше отработает. В делфях может и этот алгоритм используется, но там же он выбирался как золотая середина, т.е. по времени неплохо, по расходу памяти нормально, а кого не устраивет результат - пусть пишет алгоритм под свою конкретную задачу

[Warnes]

Сколько людей,столько и мнений. Надо как-нибудь протестировать на скорость сортировки.