Азарту ради, я написал код с сортировкой с использованием дополнительной памяти (деление интервала значений на секции):
| Скрытый текст |
| procedure TDoubleArray.QSort10Sections;
const
SectionsCount=100;
var
sectionsize:integer;
Sections:array[0..SectionsCount-1] of tdoublearray;
q,w:integer;
minval,maxval:double;
interval:double;
begin
if fcount<300 then begin
QSort2GPT;
exit;
end;
minval:=MaxSafeFloat;
maxval:=-MaxSafeFloat;
for q:=0 to fcount-1 do begin
if fitems[q]<minval then minval:=fitems[q];
if fitems[q]>maxval then maxval:=fitems[q];
end;//next q
minval:=minval-minsafefloat;
maxval:=maxval+minsafefloat;
interval:=maxval-minval;
sectionsize:=fcount div sectionscount;
for q:=0 to sectionscount-1 do begin
sections[q]:=TDoubleArray.Create;
sections[q].Capacity:=sectionsize*10;
end;
for q:=0 to fcount-1 do begin
sections[floor((sectionscount-1)*(fitems[q]-minval)/interval)].Add(fitems[q]);
end;
count:=0;
for q:=0 to SectionsCount-1 do begin
sections[q].QSort10Sections;
for w:=0 to sections[q].fcount-1 do add(sections[q].fitems[w]);
sections[q].Free;
end;
end;
|
| |
Прежде чем кликать по спойлеру, ответьте на вопрос — вы бы легко написали этот алгоритм?
Мой алгоритм вышел примерно на 30% быстрее стандартной быстрой сортировки со схемой Хоара. Памяти он расходует не особо много. А вы бы опять искали готовый алгоритм вместо голимого придумывания велосипеда?
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.