Umíte pascalsky - 19.lekce ...

Umíte pascalsky?
19.lekce
 Vytisknout  
Třídění (řazení) pole

Vzestupné (nebo sestupné) uspořádání konečného počtu hodnot nazýváme třídění. Ukážeme si některé metody třídění na třídění pole celých čísel. V této lekci to bude :

A. Třídění pomocí minima - SelectSort
B. Třídění bubláním - BubbleSort

Třídění pomocí minima - SelectSort

Příklad:
Uspořádejte čísla 8 3 1 2 5 pomocí výběru minima

příklad

Značka odděluje neuspořádaný úsek (vpravo) od uspořádaného úseku pole.
Na začátku třídění je tedy u prvního prvku pole.
Projdeme celé pole, najdeme minimum (1) a vyměníme ho s prvním prvkem (8). Tím je určen 1.prvek seřazeného pole , proto posuneme značku k druhému prvku pole a pokračujeme. Projdeme neseřazenou část pole (od značky do konce pole) a opět najdeme minimum (2) a vyměníme ho s s prvkem u značky (3). Dostaneme 2.prvek seřazeného pole. Značku posuneme k třetímu prvku a pokračujeme stejným způsobem...Naposled tento postup opakujeme je-li značka u předposledního prvku - pak porovnáme předposlední a poslední prvek, menší z nich (minimum) dáme ke značce a větší na konec a celé pole bude uspořádané.

Myšlenka (hrubý algoritmus):
Pro značku od prvního do předposledního prvku pole opakujeme tuto činnost:
-najdeme minimum z neuspořádaného úseku
-vyměníme minimum s 1.prvkem neuspořádaného úseku

Tedy:
for znacka:=1 to pocet-1 do
   <najdi minimum>
   <vyměň s 1.prvkem neusp.úseku>

Nalezení minima lze upřesnit takto:

poradi:=znacka;       (nasazení minima na prvek u značky)
for ktere:=znacka+1 to pocet do
  if cisla[ktere]<cisla{poradi] then poradi:=ktere;

No a výměna minima s 1.prvkem je už triviální.
Výslednou proceduru Trideni_minimum najdete o kousek dál.


Třídění bubláním - BubbleSort

Příklad:
Uspořádejte čísla 4 8 1 4 5 2 3 postupnými výměnami.

příklad

Značka odděluje neuspořádaný úsek (vlevo) od uspořádaného úseku pole. Na začátku třídění je tedy u posledního prvku pole.
Procházíme celé pole od začátku do konce a je-li předcházející prvek větší než následující , vyměníme je. Tím se po prvním průchodu polem dostane (probublá) největší prvek na konec a je posledním prvkem uspořádaného úseku. Značku posuneme o jedno místo dopředu a procházíme podruhé neuspořádaný úsek pole (od prvního prvku do značky) a je-li předcházející prvek větší než následující , vyměníme je. Tím se uspořádaný úsek zvětší o druhý prvrk (druhý největší). Takto pokračujeme dále ... Naposled tento postup opakujeme, je-li značka u druhého prvku. Porovnáme první dva prvky a je-li třeba, vyměníme. Tím bude celé pole seřazené.


Myšlenka (hrubý algoritmus):
Pro značku od posledního zpět do druhého prvku pole opakujeme tuto činnost:
-projít zkoumaný úsek od počátku až do značky a zaměnit ty sousední prvky, které nejsou podle velikosti

Tedy:
for znacka:=pocet downto 2 do
   <projdi neusp.úsek, je-li třeba vyměň>

Procházení s eventuální výměnou lze upřesnit takto:

for ktere:=1 to znacka-1 do
  if cisla[ktere]>cisla[ktere+1] then <vyměň prvky>

No a výměna sousedních prvků je už zase triviální.
Výslednou proceduru Trideni_bublani najdete o kousek dál.


Příklad: Sestavte program Razeni, umožňující podle volby uživatele:
1) Zadat zvolený počet celých čísel
2) Seřadit pole pomocí minima
3) Seřadit pole pomocí bublání
0) Ukončit činnost
Všechny úkoly řešte užitím procedur s parametry.

Program Razeni může vypadat takto:

program Razeni;
  const Max = 50;
  type TCisla=array[1..Max] of integer;
  var cisla,serazena:TCisla;
         pocet,volba:integer;
{globální proměnné}
 
procedure Nacti_cisla(var kolik:integer;var cisilka:TCisla);
  var ktere : integer;
  begin
    writeln('Zadejte pocet cisel:');readln(kolik);
    for ktere:=1 to pocet do
        begin
           writeln('Zadej ',ktere,'. cislo:');
           readln(cisilka[ktere]);
        end;		 {zadání počtu čísel}


{načítání čísel}
  end;

procedure Tisk_cisel(kolik:integer;cisilka:TCisla);
  var ktere : integer;
  begin
    for ktere:=1 to kolik do
           write(cisilka[ktere],' ');
    writeln;
 {tisk zadaných čísel}
  end;

procedure Trideni_minimum(kolik:integer;cisla_puvodni:TCisla;var cisla_razena:TCisla);
  var znacka,ktere,poradi,pomoc:integer;
  begin
    write('Puvodni cisla:');
    Tisk_cisel(kolik,cisla_puvodni);
    cisla_razena:=cisla_puvodni;
    for znacka:=1 to kolik-1 do
      begin
        poradi:=znacka;
        for ktere:=znacka+1 to kolik do
          if cisla_razena[poradi] > cisla_razena[ktere] then poradi:=ktere;
        pomoc:=cisla_razena[znacka];
        cisla_razena[znacka]:=cisla_razena[poradi];
        cisla_razena[poradi]:=pomoc;
      end;
    write('Serazena cisla:');
    Tisk_cisel(kolik,cisla_razena);
{Tisk původních čísel}
{zkopírování pův.čísel do řazených}
{od prvního do předposl.prvku opakuj}

{nasaď minimum na značku}
{pro prvky vpravo od značky}
{zjisti pořadí minima}

{vyměň minimum s prvkem u značky}



{tisk seřazených čísel}
  end;

procedure Trideni_bublani(kolik:integer;cisla_puvodni:TCisla;var cisla_razena:TCisla);
  var znacka,ktere,pomoc:integer;
  begin
    write('Puvodni cisla:');
    Tisk_cisel(kolik,cisla_puvodni);
    cisla_razena:=cisla_puvodni;
    for znacka:=kolik downto 2 do
      for ktere:=1 to znacka-1 do
        if cisla_razena[ktere] > cisla_razena[ktere+1] then
          begin
            pomoc:=cisla_razena[ktere];
            cisla_razena[ktere]:=cisla_razena[ktere+1];
            cisla_razena[ktere+1]:=pomoc;
          end;
      write('Serazena cisla:');
      Tisk_cisel(kolik,cisla_razena);
{Tisk původních čísel}
{zkopírování pův.čísel do řazených}
{od posledního zpět k druhému prvku opakuj}
{od prvního k prvku před značkou opakuj}
{je-li následující číslo menší než předchozí}


{vyměň tato čísla}



{tisk seřazených čísel}
  end;

Begin
{Hlavní program}
 Repeat
   writeln('Program Razeni umožňuje:');
   writeln('1. Zadat cisla');
   writeln('2. Řadit pomocí minima (SelectSort)');
   writeln('3. Řadit pomocí bublání (BubleSort)');
   writeln('0. Ukoncit');
   writeln('Zadejte svoji volbu:');
   readln(volba);
   case volba of
     1: Nacti_cisla(pocet,cisla);
     2: Trideni_minimum(pocet,cisla,serazena);
     3: Trideni_bublani(pocet,cisla,serazena);
     0: writeln('Nashledanou');
   end;
 until volba = 0;
 {opakuj}
    {nabídka činností}





    {vvýběr činnosti}
    {provedení zvolené činnost}


       


End.


Domácí úkol:

    Doplňte program Razeni o volby Trideni_maximum a Lepsi_bublani. Trideni_maximum seřadí pole opakovaným vybíráním maxima (obdoba Trideni_minimum). Lepsi_bublani ukončí proces procházení a výměn sousedních prvků dřív než dojde značka k druhému prvku. Lze totiž cyklus ukončit pokud již nedojde při průchodu zkoumaným úsekem ani k jedné výměně.
Při řazení čísel 4 8 1 5 2 3 4 lze ukončit po čtyřech krocích (a ne po šesti, až dorazí značka k druhému prvku)

On-line účast na řešení úkolu

Řešit úkol Prohlídka hodnocení úkolu Dotazy,připomínky

Pomocí volby Řešit můžete (po přihlášení) odeslat vaše řešení domácího úkolu (každý úkol smíte řešit jen jednou). Volbou Hodnocení si přečtete hodnocení a komentář od vyučujícího. Dotaz nebo připomínku můžete opakovaně zasílat pomocí tlačítka Dotazy, Komunikace (na levém okraji) zobrazuje příklad možné komunikace s vyučujícím.