Urejanje - skrčeno

Urejanje - skrčeno

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)

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)

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 izbiranjem

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

Urejanje z izbiranjem

  • 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

Hitro urejanje

  • Učinkovit algoritem za sortiranje

    • Razvil C.A.R. Hoare

  • Dve fazi:

    • Deljenje

      • Razdelimo, tako, da so v levem delu tabele vsi elementi <= pivot, v desnem pa vsi >= pivot.

    • Sortiranje

      • Rekurzivno uredimo levo in desno polovico

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.

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);
}
0%
0%