сравнение методов сортировки

← →
unlink (2006-02-24 11:27) [0]

на форме несколько чек-боксов.
Если чек-бокс отмечен - значит сортировать определённым методом.
6 методов и, соответственно, 6 чек-боксов.

+-------
генерирую массив на 10 000 случайных чисел.

Для всех 6 чек-боксов происходит следующее:
если чекбокс отмечен, что:
получаю текущее время
сортирую
получаю текущее время, отнимаю от него время до сортировки

! Притом отсортированный массив не возвращаем - он нам не нужен, нужно только время сортировки.
+-------
ПРОБЛЕМА:

Если сортировать каким-то одним методом, то мы получаем одно время, если всеми - то для того же метода и того-же массива время изменяется.

До | идёт время сортировки массива одним методом, после - всеми.

78 94 62 |78
359 360 375 |250
1328 1282 1296 |250
1015 953 1032 |0
16 0 0 |0
0 16 0 |0

т.е. например, если мы сортируем только пузырьком, то затрачивается 953-1032 мсек, а если отмечаем все методы - то 0 мс. но это же невозможно!
+-------

← →
API (2006-02-24 12:03) [1]

т.е. например, если мы сортируем только пузырьком, то затрачивается 953-1032 мсек, а если отмечаем все методы - то 0 мс. но это же невозможно!

Массив генерируется каждый раз новый?

← →
_RusLAN © (2006-02-24 12:04) [2]

unlink (24.02.06 11:27)
но это же невозможно!
Ну ничего не поделаеш. Ноль так ноль. Вот если бы код был показан, то еще можно было бы что-то придумать, а так остается только смирится с этим.

← →
unlink (2006-02-24 12:27) [3]

+----------------------------------------------
procedure TForm1.Button1Click(Sender: TObject);
var
s,ps : cardinal;
v : vektor;
begin

Button1.Enabled:=False;
s:=GetTickCount;
v:=gen_vektor(StrToInt(Edit1.Text));

if CheckBox1.Checked then begin
ps:=GetTickCount;
str_ins(v);
Label1.Caption:=IntToStr(GetTickCount-ps);
end;

if CheckBox2.Checked then begin
ps:=GetTickCount;
bin_ins(v);
Label2.Caption:=IntToStr(GetTickCount-ps);
end;

if CheckBox3.Checked then begin
ps:=GetTickCount;
str_sel(v);
Label3.Caption:=IntToStr(GetTickCount-ps);
end;

if CheckBox4.Checked then begin
ps:=GetTickCount;
bubl_sort(v);
Label4.Caption:=IntToStr(GetTickCount-ps);
end;

if CheckBox5.Checked then begin
ps:=GetTickCount;
shake_sort(v);
Label5.Caption:=IntToStr(GetTickCount-ps);
end;

if CheckBox6.Checked then begin
ps:=GetTickCount;
heap_sort(v);
Label6.Caption:=IntToStr(GetTickCount-ps);
end;

if CheckBox7.Checked then begin
ps:=GetTickCount;
quick_sort(v);
Label7.Caption:=IntToStr(GetTickCount-ps);
end;

Label8.Caption:=IntToStr(GetTickCount-s);
SetLength(v,0);
Button1.Enabled:=True;
end;
+----------------------------------------------
function gen_vektor(size: integer): vektor;
var
i : integer;
begin
SetLength(result,size);
randomize;
for i:=0 to size-1 do
result[i]:=random(random(5555))-random(random(5555));
end;
+----------------------------------------------
type vektor = array of real;
+----------------------------------------------

← →
API (2006-02-24 12:37) [4]

Label8.Caption:=

1. Вы уверены, что считываете суммарное значение именно с Label8?

2. Я так понял, у вас все методы сортировки отрабатывают последовательно
с одним и тем же массивом. То есть, если отработал первый метод сортировки, то все остальные работают с уже отсорированным массивом?

← →
_RusLAN © (2006-02-24 12:45) [5]

похоже что [1]: после первой сортировки все остальные процедуры сортируют уже отсортированый массив. Если только в процедурах не создается копия массива.

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

← →
unlink (2006-02-24 13:45) [6]

Идея понятна, но непонятно каким образом это происходит:
вот например:
function bubl_sort(var a: vektor): vektor;
но в основном коде я же не делаю v:=bubl_sort(v);

по идее ф-ции должны сортировать один и тот же массив.

есть идея не возвращать результат, или ввести boolean параметр, кот. если установлен, то возвращать рез-тат...

А как ещё можно отключить возвращение рез-та?

← →
unlink (2006-02-24 13:49) [7]

грубо говоря, все ф-ции выглядят примерно так:

function bubl_sort(var a: vektor): vektor;
var
i,j : integer;
x : real;
begin
for i:=1 to Length(a)-1 do
for j:=Length(a)-1 downto i do
if a[j-1]>a[j] then
begin
x:=a[j-1];
a[j-1]:=a[j];
a[j]:=x;
end;
result:=a;
end;

т.е. идёт работа с массивом a, а в конце result:=a.

← →
Плохиш © (2006-02-24 13:49) [8]

> function bubl_sort(var a: vektor): vektor;

Код функции можно увидеть? А то var больно смущает.

← →
Плохиш © (2006-02-24 13:51) [9]

> unlink (24.02.06 13:49) [7]

Спасибо, уже не смущает. Так и запишем, проведена массовая фальсификация результатов.

> _RusLAN © (24.02.06 12:45) [5]

Телепат, блин :-)

← →
API (2006-02-24 13:52) [10]

по идее ф-ции должны сортировать один и тот же массив

То есть, у Вас в программе используется один массив? Больше нигде созданий копии массива не производится? Тогда второй метод сортировки будет сортировать массив, уже осортированный первым методом.
Хотите, чтобы этого не было - каждый раз создавайте копию массива и передавайте ее для сортировки. Или поступайте как-нибудь по-другому. Я не могу в данном случае дать конкретный совет, потому что я не знаю, как работают Ваши методы сортировки.

А как ещё можно отключить возвращение рез-та?

Использовать вместо "функции" - "процедуры"...

> А как ещё можно отключить возвращение рез-та?

Например, убрав слово var из описаний функций.

> Использовать вместо "функции" - "процедуры"...

В данном случае не поможет, т.к. результат возвращается через параметр a

← →
API (2006-02-24 14:02) [13]

Плохиш ©
> Использовать вместо "функции" - "процедуры"...
В данном случае не поможет, т.к. результат возвращается через параметр a

Прошу прощения. Невнимательно прочитал вопрос.

unlink

Автору могу посоветовать создавать локальную копию массива.

← →
API (2006-02-24 14:12) [14]

Например, убрав слово var из описаний функций.

В общем случае, следует внимательно следить за размером массива. При 10000 элементах (как у автора), в общем случае - ничего страшного не произойдет. Но при больших массивах (у автора они - динамические, т.е., максимальный размер заранее не известен) возможно переполнение стека.
Лично я делал бы копию массива своими руками, не полагаясь в данном случае на стек.

Мне так кажется...

> Мне так кажется...

Хм, правильно кажется :-) в данном случае убирание var не поможет. Тут только созданием нового массива Result, копированием в него из a и последующей сортировкой массива Result.

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