sortowanie.doc

program projekt_aisd;

{Sortowanie przez wstawianie}

uses dos,crt;

var

h1, m1, s1, hund1 : word;

h2, m2, s2, hund2 : word;

       tab:array[1..100] of char;

       tab1:array[1..100] of char;

       i:longint;

       z:char;

       x,y,u,menu,kz,kr,spr,liczby,oblicz:integer;

       porownanie,zamiana,ile,zla_ilosc:integer;

procedure losowanie;

  begin

    textcolor(10);

    randomize;

    zla_ilosc:=0;

    repeat

    writeln;

    if zla_ilosc>0 then

    writeln('Podales zla ilosc!!!');

    write('Podaj ile mam wylosowac znakow(max 100): ');

    readln(ile);

    zla_ilosc:=zla_ilosc+1;

    until ile<=100;

    for x:=1 to ile do

     begin

      repeat

       liczby:=random(256);

       tab1[x]:=chr(liczby);

      until (liczby>32)  ;

     end;

     writeln;

     write('Wylosowane znaki to: ');

     for x:=1 to ile do

       write(tab1[x],' ');

     readln;

     textcolor(7);

  end;

procedure zamianatablic;

begin

  for x:=1 to ile do

   begin

    tab[x]:=tab1[x];

   end;

end;

procedure sortowanie_do_czas;

begin

     for x:=ile-1 downto 1 do

      begin

       z:=tab[x];

       y:=x+1;

       while (y<=ile) and (z>tab[y]) do

        begin

         tab[y-1]:=tab[y];

         tab[y]:=z;

         y:=y+1;

        end;

       tab[y-1]:=z;

      end;

  end;

procedure czas;

begin

  gettime(h1, m1, s1, hund1);

  for i:=1 to 1000000 do

   begin

    sortowanie_do_czas;

   end;

  gettime(h2, m2, s2, hund2);

  gotoxy(1,6);

  write('Czas sortowania :');

  if hund2<hund1 then

   begin

    gotoxy(28,6);

    write(hund2+100-hund1,'ms');

    s2:=s2-1;

   end

   else

    begin

     gotoxy(28,6);

     write(hund2-hund1,'ms');

    end;

  if s2<s1 then

   begin

    gotoxy(25,6);

    write(s2+60-s1,',');

    m2:=m2-1;

   end

  else

   begin

    gotoxy(25,6);

    write(s2-s1,',');

   end;

  if m2<m1 then

   begin

    gotoxy(22,6);

    write(m2+60-m1,':');

    h2:=h2-1;

   end

  else

   begin

    gotoxy(22,6);

    write(m2-m1,':');

   end;

  if h2<h1 then

   begin

    gotoxy(19,6);

    write(h2+24-h1,':');

   end

  else

   begin

    gotoxy(19,6);

    write(h2-h1,':');

   end;

writeln;

end;

procedure kolor;

begin

  for u:=1 to ile do

   begin

    if u=kr then

     begin

      textcolor(10);

      write(tab[u],' ');

      textcolor(7);

     end

     else

     if u=kz then

     begin

      textcolor(5);

      write(tab[u],' ');

      textcolor(7);

     end

     else

    write(tab[u],' ');

   end;

   readln;

end;

procedure sort_wstawianie;

begin

   porownanie:=0;

   zamiana:=0;

     for x:=ile-1 downto 1 do

      begin

       z:=tab[x];

       kr:=x;

       y:=x+1;

       kz:=y;

       while (y<=ile) and (z>tab[y]) do

        begin

           porownanie:=porownanie+1;

           kolor;

         tab[y-1]:=tab[y];

         tab[y]:=z;

         kr:=y;

         kz:=y-1;

           kolor;

           zamiana:=zamiana+1;

         spr:=1;

         y:=y+1;

         kz:=y;

        end;

       tab[y-1]:=z;

       kr:=y-1;

       if spr=0 then

        begin

           kolor;

           porownanie:=porownanie+1;

        end;

       spr:=0;

      end;

       writeln;

       textcolor(10);

       writeln('Tak wygladaja posortowane znaki');

       writeln;

       for x:=1 to ile do

       write(tab[x],' ');

       textcolor(7);

       readln;

  end;

procedure zlozonosc;

begin

clrscr;

  textcolor(10);

  writeln;

  writeln('Program wykonal ',porownanie,' porownan');

  writeln;

  writeln('Program wykonal ',zamiana,' zamian');

  writeln;

  zamianatablic;

  czas;

  writeln;

  oblicz:=1;

  for x:=2 to ile-1 do

      oblicz:=oblicz+x;

  writeln('Pesymistyczna zlozonosc obliczeniowa wynosi ',oblicz);

  writeln;

  writeln('                                                    2');

  writeln('Wyraza sie wzorem: 1/2n(n-1), co mozemy zapisac: O(n )');

  writeln;

  writeln;

  writeln('Srednia zlozonosc obliczeniowa wynosi ',oblicz);

  writeln;

  writeln('                                                    2');

  writeln('Wyraza sie wzorem: 1/2n(n-1), co mozemy zapisac: O(n )');

  writeln;

  writeln;

  writeln('Zlozonosc obliczeniowa optymistyczna wynosi: ');

  writeln;

  writeln('Wyraza sie wzorem:           , co mozemy zapisac: O(n log n)');

  readln;

  textcolor(7);

end;

begin

  repeat

    clrscr;

    textcolor(10);

    writeln('########## MENU ##########');

    writeln;

    writeln('       1. Losowanie znakow');

    writeln('       2. Sortowanie');

    writeln('       3. Porownania,zamiany,czas i zlozonosc');

    writeln('       4. Koniec');

    writeln;

    write  ('Podaj numer pozycji: ');

    readln(menu);

    textcolor(7);

     if menu=1 then

       begin

       losowanie;

       end

     else;

     if menu=2 then

       begin

       zamianatablic;

       sort_wstawianie;

       end

     else;

     if menu=3 then

       begin

       zlozonosc;

       end

     else;

  until menu=4;

end.