Urejanje

Urejanje

Avtor: Matija Lokar

Več o projektu...

O urejanju

  • Kaj urejamo

  • Kje so podatki

    • datoteke
    • notranji pomnilnik

  • Različne metode

    • če vemo za maksimalni podatek: urejanje s koši
    • vstavljanje, izbiranje, urejanje z mehurčki, urejanje s kopicami, hitro urejanje, zlivanje, ...

Urejanje podatkov v tabeli

  • Vsi podatki gredo v notranji pomnilnik
  • Shranjeni so v tabeli (podatek[])
  • Na koncu jih želimo imeti v isti tabeli
  • Ne želimo tratiti dodatnega prostora
(urejanje_2.png)

Časovna in prostorska zahtevnost

  • Kaj štejemo

  • Pogosto odločilni faktor primerjave:

    • števila
    • zapisi/strukture/objekti
    • slike

  • Včasih zahtevna zamenjava

    • zapisi/strukture/objekti
    • slike

Lastnosti dobrega algoritma za urejanje

  • pravilnost
  • hitrost

  • stabilnost - urejenih elementov ne zamenjuje

    • več ključev
    • Npr: uredi podatke po abecedi: če je priimek enak, po imenu

  • naravnost - urejene elemente naj uredi hitro

    • morda predpriprava (če ne zahteva preveč časa)

Dobra obravnava različnih algoritmov in prikazi delovanja:

http://web.engr.oregonstate.edu/~minoura/cs162/demos.html

Enostavna urejanja

  • Preprosta zasnova
  • Ne najbolj učinkoviti
  • Časovna zahtevnost (poznamo urejanje s kopicami, ki zahteva , čemu tile?)
  • Primerni za majhne tabele, (Enostavna koda odtehta slabo učinkovitost)
  • Urejanje z vstavljanjem (insertion sort), urejanje z izbiranjem (selection sort), urejanje z mehurčki (bubble sort)

Učinkovita urejanja

  • Bolj komplicirana zgradba
  • Časovna zahtevnost
  • Primerni za velike tabele
  • Ne nujno stabilni
  • Urejanje s kopicami (heap sort), hitro urejanje (quick sort), urejanje z zlivanjem (merge sort)

Enostavna urejanja

Urejanje z vstavljanjem, izbiranjem ali mehurčki

  • Uporabimo, ko je majhen

  • Enostavnost kode odtehta neučinkovitost!

    (urejanje_6.png)

Urejanje z vstavljanjem

Karte:

  • V roki imamo nekaj urejenih kart
  • Vzamemo novo karto
  • Naredimo prostor zanjo
  • Vtaknemo na ustrezno mesto

Urejanje z vstavljanjem

Demo:
http://max.cs.kzoo.edu/~abrady/java/sorting/InsertionSort.html

http://al.ei.tuat.ac.jp/~sekisita/isort-e.html

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/sorting.html

http://www.cs.brockport.edu/cs/java/apps/sorters/insertsortaniminp.html

http://cs.smith.edu/%7Ethiebaut/java/sort/demo.html

http://blackcat.brynmawr.edu/~spoonen/JavaProject/sorter.html

Urejanje z vstavljanjem

  • dva dela: urejeni del / neurejeni del
  • 2 5 11 : 7 * * * * * *
  • 2 5 7 11 : 9 * * * * *
  • …
  • vzemi prvi element iz neurejenega dela in ga vstavi na pravo mesto v urejeni del
  • na začetku je urejeni del prvi element
  • končamo, ko izčrpamo neurejeni del

Urejanje z vstavljanjem

  • na vrsti je a-ti elt.
  • pogledamo a-1 tega
  • če je ta manjši od njega, ta-1 prestavimo za eno mesto nazaj
  • pogledamo a-2 ega
  • …

Urejanje z vstavljanjem

    t = tabela[a];
    int b = a - 1; // do kam so ze urejeni
    while ((b >= 0) && (t < tabela[b]))
    { // kam spada a-ti
      tabela[b + 1] = tabela[b];
      // prestavimo večjega nazaj
      b = b - 1;
    }
    tabela[b + 1] = t;
      // a-tega zapišemo na pravo mesto

Urejanje z vstavljanjem

public static void Vstavljanje(int[] tabela) {
   // urejanje z vstavljanjem * urejamo cela stevila

  int koliko = tabela.Length;
  for (int a = 1; a < koliko;  a++)  {
    t = tabela[a];
    int b = a - 1; // do kam so ze urejeni
    while ((b >= 0) && (t < tabela[b])) {
      // kam spada a-ti
      tabela[b + 1] = tabela[b]; // prestavljamo
      b = b - 1;
    }
    tabela[b + 1] = t;
  }
}

Urejanje z izbiranjem

  • poišči najmanjšega
  • zamenjaj s prvim
  • od 2 do n poišči najmanjšega
  • zamenjaj z drugim
  • ...

Demo

http://al.ei.tuat.ac.jp/~sekisita/ssort-e.html

http://www.cs.adfa.oz.au/teaching/studinfo/ada/Searching/selection_sort.html

http://www.cs.ust.hk/faculty/tcpong/cs102/summer96/aids/select.html

http://www.cs.orst.edu/~minoura/cs162/javaProgs/sort/SelectSort.html

http://www.student.seas.gwu.edu/~idsv/idsv.html

http://www1.mmu.edu.my/%7Emukund/dsal/SSort.html

Urejanje z vstavljanjem

  • dva dela: urejeni del / neurejeni del
  • 2 5 6 : 17 13 9 12
  • 2 5 6 9 : 13 17 12
  • …
  • vzemi prvi element iz neurejenega dela in ga zamenjaj z najmanjšim elementom iz neurejenega dela. Urejen del se poveča za ena.
  • na začetku je urejeni del prazen
  • končamo, ko izčrpamo neurejeni del

Poišči najmanjšega

private static int  PoisciNajmanjsega (int[] tab,
                                       int   odKje,
                                       int   doKam)
// poisce indeks najmanjsega v tabeli
// tab od od_kje do doKam
{
  int i_najm = odKje; // indeks trenutno najmanjsega
  for (int i = odKje + 1; i <= doKam; i++)  {
     if (tab[i] < tab[i_najm])
         i_najm = i;
  }
  return i_najm;
}

Končni program

public static void  UrejanjeIzbira (int[] tabela)
// urejanje z izbiranjem * urejamo cela stevila
{
  int kjeNajm; // indeks najmanjsega
  int koliko = tabela.Length;
  for (int a = 0; a < koliko – 1; a++)
  { kjeNajm = PoisciNajmanjsega(tabela, a, koliko - 1);
    // zamenjamo
    t = tabela[a];
    tabela[a] = tabela[kjeNajm];
    tabela[kjeNajm] = t;
  }
}

Urejanje z mehurčki

  • vzamemo zadnji element in ga primerjamo s svojim predhodnikom:

    • če je predhodnik manjši, potem sta elementa v pravem vrstem redu in zgrabimo predhodnika
    • če predhodnik ni manjši, ju zamenjamo
  • ...
  • najlažji element splava na površje
  • plavanje - zamenjave

Urejanje z mehurčki

  • 3 4 2 1 5

    • 3 4 2 1 5
    • 3 4 1 2 5
    • 3 1 4 2 5

  • 1 3 4 2 5

    • 1 3 4 2 5
    • 1 3 2 4 5

  • 1 2 3 4 5

    • 1 2 3 4 5
  • 1 2 3 4 5

Urejanje z mehurčki

Demo:

http://max.cs.kzoo.edu/~abrady/java/sorting/BubbleSort.html

http://al.ei.tuat.ac.jp/~sekisita/bsort-e.html

http://www.cs.orst.edu/~minoura/cs261/javaProgs/sort/BubbleSort.html

http://www.cs.brockport.edu/cs/java/apps/sorters/bubblesort.html

http://www.cs.brockport.edu/cs/java/apps/sorters/bubblesorteffaniminp.html

http://cs.smith.edu/%7Ethiebaut/java/sort/demo.html

http://blackcat.brynmawr.edu/~spoonen/JavaProject/sorter.html

http://weed.cs.curtin.edu.au/units/cp501/notes/simplebubblesort1.html

Hitro urejanje

  • Učinkovit algoritem za sortiranje

    • Razvil C.A.R. Hoare
  • Primer algoritma Deli in Vladaj

  • Dve fazi:

    • Deljenje

      • Deli delo na pol

    • Sortiranje

      • Vladaj polovicam!

Hitro urejanje

Deljenje

  • Izberi delilni element (pivot)

  • Poišči mesto za delilni element tako, da

    • so vsi elementi na levi manjši
    • vsi elementi na desni so večji
(urejanje_23.png)

Hitro urejanje

Vladaj

  • Uporabi (rekurzija!) isti algoritem na obeh polovicah
(urejanje_24.png)

Hitro urejanje

  • Izberi si delilni element (x)

  • razdeli na dva dela

    • <=x
    • >=x
  • z istim postopkom uredi oba dela
  • 9, 11, 7, 5, 8, 4, 36
  • Delilni element (9)
  • Preuredimo: 9, 4, 7, 5, 8, 11, 36
  • Uredimo oba dela: 4, 5, 7, 8, 9, 11, 36
  • Združevanje ni potrebno!

Hitro urejanje - algoritem

HU(a,dno,vrh) {
if (dno < vrh) // problem ni majhen
  s = preuredi(a, dno, vrh);
  // s – mesto, kjer se tabela razdeli
  HU(a,dno,s-1); //s-ti (ki je potem pivot)
                 //je že prav   HU(a,s+1,vrh);
}

Kako učinkovito preurediti tabelo

  • Dokler so na levi elementi manjši ali enaki pivotu – OK

  • Prvi, ki je z leve večji

    • Napačen?
    • Ni nujno – vsekakor pa je kandidat za to, da "stoji" narobe
  • Dokler so na desni večji ali enaki pivotu – OK

  • Prvi, ki je z desne manjši

    • Napačen?
    • Ni nujno – vsekakor pa je kandidat za to, da "stoji" narobe

  • Kdaj sta kandidata "prava"

    • Če je večji levo od manjšega
    • Zamenjamo!

Na http://pages.stern.nyu.edu/~panos/java/Quicksort/ si lahko "v živo" ogledate urejanje na poljubnih podatkih.

Preurejanje

(urejanje_28.png)

Preureditev

(urejanje_29.png)

Koda

public static int Premeci(int[] a, int levo, int desno) {
  // preuredi tabelo a od levo do desno
  int pivot = a[levo];
  int manjsi = levo, vecji = desno;
  while (manjsi < vecji) { // dokler se indeksa ne prekrižata
      while (manjsi < vecji && a[manjsi] <= pivot) // iščemo večjega
         manjsi = manjsi + 1;
      while (manjsi < vecji && a[vecji] >= pivot) // iščemo manjšega
         vecji = vecji - 1;

      if (manjsi < vecji) { // če se nista indeksa prekrižala
         int t = a[manjsi];
         a[manjsi] = a[vecji];
         a[vecji] = t;
      }
  }
  if (a[manjsi] > pivot)  manjsi = manjsi - 1;
  a[levo] = a[manjsi]; // prenesemo še pivotni element
  a[manjsi] = pivot;
  return manjsi; // kje je meja med deloma
}

Urejanje z zlivanjem

  • Tabelo razdelimo na pol
  • Uredimo obe polovici
  • Združevanje – zlivanje podatkov (iz obeh delov vzamemo manjšega)

9, 11, 7, 5, 8, 4, 36

  • Na pol: 9, 11, 7, 5, 8, 4, 36
  • Uredimo oba dela: 5, 7, 9, 11, 4, 8, 36
  • Združimo: 4, 5, 7, 8, 9, 11, 36

Urejanje z zlivanjem - algoritem

uredi z zlivanjem(a,dno,vrh) {
if dno < vrh
  s = (dno + vrh) / 2;
  uredi z zlivanjem(a,dno,s);
  uredi z zlivanjem(a,s+1,vrh);
  zlij(a,dno,s,vrh);
}

Demo

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/qsort.html

http://www.cs.hope.edu/~alganim/animator/Animator.html

http://www.research.compaq.com/SRC/JCAT/jdk10/sorting/index.html

http://www.student.seas.gwu.edu/~idsv/idsv.html

http://www.cs.orst.edu/~minoura/cs162/javaProgs/sort/QuickSort.html

http://loki.cs.brown.edu:8081/webdsa/slides/ch10/QuickSort/

http://www.cs.usask.ca/research/research_groups/aries/projects/applets/tutorials/sorting/quick/2-1.shtml

Zlivanje

  • Zlijemo po dva in dva v urejene pare
  • Pare zlijemo v četverčke, ...
  • Tabelo razdelimo na dva dela
  • Vsak del uredimo
  • Zlijemo urejena dela

  • V primerjavi s QS

    • Manj dela z delitvijo
    • Več dela z združevanjem

Povezave

http://www2.ics.hawaii.edu/~qizhang/ics665/mergesort.html

http://www.cs.utoronto.ca/~neto/teaching/238/16/mergesort.html

http://www.cs.utoronto.ca/~neto/teaching/238/21/mergesort21.html

http://www.cs.hope.edu/~alganim/animator/Animator.html

http://www.student.seas.gwu.edu/~idsv/idsv.html (poskusi sam!)

http://www.cs.brockport.edu/cs/java/apps/sorters/mergesort_bfaniminp.html(potenca 2 - pari, 4ke, ...)

http://www.cs.brockport.edu/cs/java/apps/sorters/mergesort_df.htmlz delitvijo na pol / pol /pol ...

http://www.geocities.com/SiliconValley/Program/2864/File/Merge1/mergesort.html

Urejanje z zlivanjem

  • Tudi DiV algoritem
  • preprosto deljenje (/2)
  • zlivanje je združevanje

Urejanje z zlivanjem - algoritem

uredi z zlivanjem(a,dno,vrh) {
if dno < vrh
  s = (dno + vrh) / 2;
  uredi z zlivanjem(a,dno,s);
  uredi z zlivanjem(a,s+1,vrh);
  zlij(a,dno,s,vrh);
}

Zlivanje – demo

(zlivanje_0.png)

Zlivanje – korak 1

(zlivanje_1.png)

Zlivanje – korak 2

(zlivanje_2.png)

Zlivanje – korak 3

(zlivanje_3.png)

Zlivanje – korak 4

(zlivanje_4.png)

Zlivanje – korak 5

(zlivanje_5.png)

Zlivanje – korak 6

(zlivanje_6.png)

Zlivanje – korak 7

(zlivanje_7.png)
0%
0%