Sortowanie tablic.doc

Referat autorstwa Pawła Pełszyńskiego, ucznia klasy II Ti, na temat sortowania tablic w programie Pascal.

Sortowanie szybkie(ang. quicksort) – jeden z popularnych algorytmów sortowania działających na zasadzie "dziel i zwyciężaj".

PROCEDURE Quicksort (VAR A : tab; l,r: INTEGER);

   VAR

       pivot,b,i,j :  INTEGER;

   BEGIN

       IF l < r THEN

       BEGIN

           pivot := A[random(r-l) + l+1];  { losowanie elementu dzielącego }

           i := l-1;

           j := r+1;

           REPEAT

               REPEAT i := i+1 UNTIL pivot <= A[i];

               REPEAT j := j-1 UNTIL pivot >= A[j];

               b:=A[i]; A[i]:=A[j]; A[j]:=b

           UNTIL i >= j;

           A[j]:=A[i]; A[i]:=b;

           Quicksort(A,l,i-1);

           Quicksort(A,i,r)

       END

   END;

Wywoływanie dla tablicy o długości n: quicksort(tablica,1,n);.

Sortowanie przez kopcowanie

program heap_sort;

uses crt;

type

   Wsk = ^TLiczba;

   TLiczba = record

             dane        : integer;

             lewy, prawy : Wsk;

             end;

const N = 20;

var

  d         : array[1..N] of integer;

  i,j,l,poz : integer;

   korzen, tmp, poprz, akt : Wsk;

  PROCEDURE WstawTabliceDoDrzewa(k  : integer);

  begin

  l:=1;{odpowiada za przemienne wstawianie do prawej i lewej galezi}

{tworzenie drzewa}

  New(korzen); {pierwszy element}

  korzen^.dane:=d[1];

  korzen^.lewy:=nil;

  korzen^.prawy:=nil;

  for i := 2 to k do

  begin

{wstawiamy na wierzcholek}

    if d[i]>korzen^.dane then

    begin

                        tmp:=korzen;

                        New(korzen);

                  korzen^.dane:=d[i];

      if l=1 then

      begin

                    korzen^.lewy:=tmp;

                           l:=0;

                   end;

                   if l=0 then

      begin

                    korzen^.prawy:=tmp;

                           l:=1;

                   end;

      end ;

      if d[i]<=korzen^.dane then

      begin

          if l=1 then

          begin

            tmp:=korzen^.lewy;

            while d[i]<tmp^.dane do {szukam miejsca gdzie wstawic kolejny element po lewej}

            begin

                    poprz:=tmp;

              tmp:=tmp^.lewy;

            end;

            New(akt); {wstawiam element}

                  akt^.dane:=d[i];

                  akt^.lewy:=tmp;

                  akt^.prawy:=nil;

                  poprz^.lewy:=akt;

                  l:=0;

        write(i);

          end;

          if l=0 then

          begin

            tmp:=korzen^.prawy;

            while d[i]<tmp^.dane do                {szukam miejsca gdzie wstawic kolejny element po prawej}

            begin

                    poprz:=tmp;

              tmp:=tmp^.prawy;

            end;

            New(akt); {wstawiam element}

                  akt^.dane:=d[i];

                  akt^.prawy:=tmp;

                  akt^.lewy:=nil;

                  poprz^.prawy:=akt;

                  l:=1;

          end;

  end;end;

  end;{koniec procedury wstawiania do drzewa}

  PROCEDURE WstawDrzewoDoTablicy(wstawiany:Wsk);

        begin

                d[poz]:=wstawiany^.dane;

                poz:=poz+1;

                if wstawiany^.lewy<>nil then

                  WstawDrzewoDoTablicy(wstawiany^.lewy);

                if wstawiany^.prawy<>nil then

                  WstawDrzewoDoTablicy(wstawiany^.prawy);

                dispose(wstawiany);

  end;{koniec wstawiania drzewa do tablicy}

begin

  clrscr;

  writeln;

  writeln('Przed sortowaniem:'); writeln;

{wstawianie elementów losowych do tablicy}

  randomize;

  for i := 1 to N do

  begin

    d[i] := random(100); write(d[i] : 4);

  end;

  for j:=0 to N-1 do {czesc odpowiedzialna za sortowanie}

  begin

    WstawTabliceDoDrzewa(N-j); {wstawiam N-j pierwszych elementów do drzewa reszta jest juz posortowana}

    poz:=1;

    write(j);

    d[N-j]:=korzen^.dane; {wstawiam najwyzszy element z wierzcholka drzewa na poczatek posortowanej czesci tablicy}

    if korzen^.lewy<>nil then

                  WstawDrzewoDoTablicy(korzen^.lewy);{wstawiam lewa czesc drzewa z powrotem do tablicy}

                if korzen^.prawy<>nil then

                  WstawDrzewoDoTablicy(korzen^.prawy);{wstawiam prawa czesc drzewa z powrotem do tablicy}

                dispose(korzen);

  end;

end;

  writeln('Po sortowaniu:'); writeln;

  for i := 1 to N do write(d[i] : 4);

  readln;

  writeln;

  writeln('Nacisnij Enter...');

  readln;

end.

Sortowanie przez wybór

const N = 20;
var
d : array[ 1..N ] of real;
i,j,pmin : integer;
pomoc:real;
begin
randomize;
for i := 1 to N do d[ i ] := random(100)/10+1;
writeln('Przed sortowaniem:'); writeln;
for i := 1 to N do write(d[ i ] : 4:2,' ');
writeln;

for j := 1 to N - 1 do
begin
pmin := j;
for i := j + 1 to N do
if d[ i ] < d[ pmin ] then pmin := i;
pomoc := d[ pmin ]; d[ pmin ] := d[ j ]; d[ j ] := pomoc;
end;

writeln('Po sortowaniu:'); writeln;
for i := 1 to N do write(d : 4:2,' ');
writeln;
writeln('Nacisnij Enter...');
readln;
end.

 

2