подсчеты перестановок и сравнений в сортировках +графика Опции

[kreativshik]

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

uses crt;
const n=100;
type tm= array [1..n] of integer;
var i,j,peres,k,u,temp,srav,otv:integer;
a,b:tm ;

procedure pech_massiv(a:tm);
  begin
      randomize;
    for i:=1 to n do
        write(a[i],' ');
     writeln;
  end;



       Procedure pr_vkl (var a:tm);
var
i,j,m,r:integer;
begin
for i:=2 to n do
begin
r:=a[i];
j:=i-1;
while (j>=1)and(r<a[j]) do begin
a[j+1]:=a[j];
dec(j);
Inc(Srav);
          Inc(Peres);
end;
a[j+1]:=r;
end;
       textcolor(blue);
 for i:=1 to n do

	write(a[i],' ');
        writeln;
        textcolor(white);
        writeln('Metod priamogo vklycheniia:');
        writeln('Chislo perestanovok = ',peres);
    writeln('Chislo sravneniy = ',srav);
    readln;
end;












procedure vybor(a:tm);
begin
    peres:=0;
    srav:=0;


    for  i:= 1  to  n-1  do
	begin
	    k := i;
	    temp := a [i];
	    for  j := i+1  to  n  do
		begin
		    inc(srav);
		    if  a [j] < temp  then
			begin
			    k := j;
			    temp := a [j];
			end;
		end;
	    a [k] := a [i];
            if k <> i then inc(peres);
	    a [i] := temp;
	end;
    write('Sortirovka');
    textcolor(red);
    for i:=1 to n do

	write(a[i],' ');
        writeln;
        textcolor(3);
        writeln('Metod priamogo vybora:');
    textcolor(white);
    writeln('Chislo perestanovok = ',peres);
    writeln('Chislo sravneniy = ',srav);

end;

begin
    clrscr;
    textcolor(5);
        writeln('Neotsortirovannyu massiv:');
        randomize;
    for i:=1 to n do
    begin
        a[i]:=random(100);
        textcolor(green);
        write(a[i],' ');
     end;
     writeln;

       Srav:=0;
  Peres:=0;
        b:=a          ;
        vybor(a);
         pr_vkl(a);

         textcolor(5);
                      writeln('massiv otsortirovannyu po vozrastaniy:');
        textcolor(green);
        for i:=2 to n do
         for j:=n downto 1 do
           if a[j-1]>a[j] then
           begin
           u:=a[j-1];
           a[j-1]:=a[j];
           a[j]:=u;
           end;
           for i:=1 to n do
           write (a[i], ' ');
           writeln;
             b:=a          ;

        Srav:=0;
        Peres:=0;
             vybor(a);
             pr_vkl(b);
              writeln;
           {clrscr;}
           textcolor(5);
           writeln('Massiv otsortirovannyu po ybyvaniy:');




             textcolor(green);
        for i:=2 to n do
         for j:=n downto 1 do
           if a[j-1]<a[j] then
           begin
           u:=a[j-1];
           a[j-1]:=a[j];
           a[j]:=u;
           end;
           for i:=1 to n do
           write (a[i], ' ');
           writeln;
              Srav:=0;
              Peres:=0;
             vybor(a);
             pr_vkl(a);

     writeln;


        b:=a;
     repeat
	begin
	    writeln('   1-Exit ');
	    readln(otv);
	    case otv of
                 1:end;

	end;
    until otv=1;

end.

[volvo]

И добавление счетчиков в алгоритмы сортировки и работа с гистограммами рассматривались на форуме. Пользуйся поиском...

[kreativshik]

нет там ничего ,что мне надо =(

[kreativshik]

помогите хоть кто нибудь плиз

[kreativshik]

I need help
хоть кто нибудь помогите !!!

[volvo]

нет там ничего ,что мне надо =(

Как же "нет"? Вот тут, например, показывается, как добавить счетчики в быструю сортировку Хоара:
Счётчик
Это как раз то, что тебе надо -

добавить в эту программу квиксорт (quicksort) и подсчитать в ней перестан и сравнения

Счетчик перестановок - добавляется там, где есть присваивание одного элемента массива другому...

Гистограммы тоже найти?

[Гость]

если тебя не затруднит плиз , я не знаю как сделать гистограмму динамическую

[volvo]

Уточни что именно тебе надо, чтобы отображалось в гистограмме динамически?

Результаты перестановок и сравнений - это обычная гистограмма, отрисовывается один раз, после завершения ВСЕХ сортировок ...

[Гость]

мне нужно чтобы бралось три сортировки и выводились гистограммы по сравнению рядом 3 штуки и потом по перестановка тоже 3-х способов.
потом тоже самое для отсортированного массива и отсортированного по убыванию !

[Гость]

помогите хоть кто нить плз

[Гость]

народ , на помощь плз

[volvo]

Вот это устроит?

[Гость]

да , только не мог бы ты пояснить эти строчки :
b := a;
vybor(b, data[1][1], data[2][1]);
b := a;
pr_vkl(b, data[1][2], data[2][2]);
b := a;
quicksort(b, data[1][3], data[2][3]);

show_gist('perestanovki', names, data[1]);
writeln;
show_gist('sravneniya', names, data[2]);

[volvo]

не мог бы ты пояснить эти строчки :

Мог бы...

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

Для удобства отображения в виде гистограммы все количества перестановок/сравнений хранятся в двумерном массиве, первая строка - перестановки, а вторая - сравнения... Таким образом, здесь:

b := a;
// вызываем сортировку выбором, количество перестановок сохраняем
// в первой строке массива data, количество сравнений - во второй строке
vybor(b, data[1][1], data[2][1]); 
b := a;
// Аналогично, только меняется индекс
pr_vkl(b, data[1][2], data[2][2]);
b := a;
// ...
quicksort(b, data[1][3], data[2][3]);

// а потом, массив перестановок передаем функции отрисовки гистограммы ...
show_gist('perestanovki', names, data[1]);
writeln;
// ... и то же самое сделаем для массива сравнений ...
show_gist('sravneniya', names, data[2]);

Сообщение отредактировано: volvo - 5.04.2007 18:51

[Гость]

огромное спасибо