Gnome sort

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Gnome sort je algoritem za urejanje podatkov. Algoritem primerja dva sosednja podatka v tabeli. V primeru, da je podatek z indeksom a[i] večji od podatka z indeksom a[i+1], zamenja njuni vrednosti. Nato pregleda predhodni par podatkov (torej a[i-1] in a[i]) in ju v primeru, če nista urejena, zamenja. Ta postopek nadaljuje, dokler ne naleti na par, ki je že urejen. (Po potrebi do a[0]!) Nato nadaljuje pregledovanje podatkov, od tistega indeksa, kjer je ostal pri zadnji zamenjavi vrednosti, torej a[i+1]. Ko pride s pregledom do konca tabele, je tabela urejena. Časovna zahtevnost je O(n2). Izkazalo se je, da je v praksi algoritem tako hiter kot navadno vstavljanje oz. urejanje z vstavljanjem.

Algoritem

 function gnomeSort(a[0..size-1]) {
    // uredimo tabelo a
    i := 1 //kje primerjamo elemente
    j := 2 // do kam smo pregledali tabelo
    while i ≤ size - 1
      if a[i-1] ≤ a[i] // sosednja elementa sta urejena
          i := j // do j je načeloma vse v redu
          j := j + 1 
      else
          swap a[i-1] and a[i] 
          i := i - 1 //gremo nazaj, dokler ne bo vse v redu
          if i = 0
            i := 1
   }

Primer

Slikovna predstavitev delovanja algoritma na primeru 3, 5, 8, 7, 10, 1, 4!

Povezave

Osebna orodja