Umíte pascalsky - 20.lekce ...

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

Třídění pole je vhodné téma na procvičování tvorby algoritmů. Proto se ještš dnešní lekci věnujeme dalším metodám třídění. Dnes si ukážeme:

A. Třídění vsouváním (zatřiďováním) - InsertSort
B. Schellovo třídění - ShellSort

Třídění vsouváním (zatřiďováním) - InsertSort

Toto je jeden z logicky nejpřirozenějších způsobů třídění. Postupně zasouváme (zatřiďujeme) prvky na místa, kam podle velikosti patří.
Ukážeme si tuto metodu na příkladě:

Příklad:
Uspořádejte čísla 8  3  1  2  2 zatřiďováním.

příklad

Začneme od druhého prvku (3). Porovnáním s prvním prvkem (8) zjistíme, že patří před něj. Trojku vyjmeme, osmičku posuneme o jedno místo doprava a na uvolněné místo vložíme trojku. Přejdeme na třetí prvek (1). Porovnáním s prvním prvkem (3) zjistíme, že patří před něj. Jedničku vyjmeme, posuneme úsek čísel 3 8 o jedno místo doprava a na uvolněné místo vložíme jedničku. Takto pokračujeme dále ... Naposled tento postup opakujeme pro poslední prvek (2). Porovnáváním tohoto prvku s prvky od začátku pole zjistíme, kam podle velikosti patří (na místo prvku s pořadím index, tedy 2), prvek vyjmeme, úsek před ním (od něj až po místo kam patří - index) posuneme o jedno místo doprava a na uvoněné místo vložíme tento prvek. Tím bude celé pole seřazené.


Myšlenka (hrubý algoritmus):

Od druhého do posledního prvku pole opakujeme tuto činnost:
- najdeme místo v předchozím úseku, kam tento prvek podle velikosti patří
- vyjmeme tento prvek
- posuneme předchozí prvky (až k místu kam patří) o jedno místo doprava
- vložime prvek na uvolněné místo

Upřesníme jednotlivé kroky:

příklad

najdeme místo - aktuální prvek (cisla[ktery]) opakovaně porovnáváme s prvky od začátku pole. Je-li aktualní prvek větší než první, porovnáváme s druhý prvkem atd., až dojdeme k prvku (cisla[index]), který už není menší než aktuální prvek. Na toto místo patří - udává proměnná index.

vyjmeme prvek - zkopírujeme si ho do pomocné proměnné (prvek)

posuneme předchozí prvky (až k místu kam patří) - asi nejobtížnější část. Prvky úseku cisla[index] ... cisla[ktery-1] posouváme postupně od konce o jedno místo doprava. Tedy opakovaně pro proměnnou kde od ktery zpět do index+1 provádíme přiřazení cisla[kde]:=cisla[kde-1]. Tím se nám uvolní místo po prvku cisla[index]

vložíme prvek na uvolněné místo - představuje definování nové hodnoty cisla[index] pomocí proměnné prvek

Výslednou proceduru Trideni_vsouvani najdete o kousek dál.


Schellovo třídění - ShellSort

Třídění probubláváním (postupnými výměnami) lze výrazně urychlit tím, že budeme vždy procházet celé pole a nebudeme porovnávat sousední prvky, ale prvky vzdálené o hodnotu krok , tedy cisla[ktere] a cisla[ktere+krok] a to tak dlouho, dokud bude docházet k nějakým výměnám.
Pro krok platí:
počáteční krok . . . krok = (1 + pocet) div 2
následující krok . . . krok = (krok + 1) div 2
Naposledy se uvedené výměny provádí pro krok=1 a po jejich realizaci bude pole uspořádané.

Příklad:
Uspořádejte čísla 39  57  63  13  24  95  73  15 pomocí Shellova třídění:

příklad


Myšlenka (hrubý algoritmus):
Bude za domácí úkol.

Příklad: Doplňte program Razeni o volbu řazení zatřiďováním.

Program Razeni (pouze s dnešní procedurou Trideni_vsouvani) 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_vsouvani(kolik:integer;cisla_puvodni:TCisla;var cisla_razena:TCisla);
  var prvek,ktere,kde,index:integer;
  begin
    write('Puvodni cisla:');
    Tisk_cisel(kolik,cisla_puvodni);
    cisla_razena:=cisla_puvodni;
    for ktere:=2 to kolik do
      begin
        index:=1;
        while cisla[ktere]>cisla_razena[index] do
          index:=index+1;
        prvek:=cisla_razena[ktere];
        for kde:=ktere downto index+1 do
          cisla_razena[kde]:=cisla_razena[kde-1];
        cisla_razena[index]:=prvek;
      end;
    write('Serazena cisla:');
    Tisk_cisel(kolik,cisla_razena);
{tisk původních čísel}
{zkopírování pův.čísel do řazených}

{od druhého do posledního prvku opakuj}
{začni od začátku
{posouvej se na další prvek dokud je zatřiďovaný větší}
{vyjmi (zkopíruj) prvek}

{posuň předchozí prvky doprava}
{vlož zatřiďovaný prvek}

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

Begin
{Hlavní program}
 Repeat
   writeln('Program Razeni umožňuje:');
   writeln('1. Zadat cisla');
   writeln('2. Řadit pomocí zatřiďování (InsertSort)');
   writeln('0. Ukoncit');
   writeln('Zadejte svoji volbu:');
   readln(volba);
   case volba of
     1: Nacti_cisla(pocet,cisla);
     2: Trideni_vsouvani(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 volbu Trideni_shell pro seřazení pole Shellovou metodou.

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.