Ciklično sortiranje

Ciklično sortiranje

Namena sortiranje Struktura podataka Niz Vremenska kompl. O(n²) Memorijska kompl. O(n) Stabilan ne

Ciklično sortiranje predstavlja nestabilni, in-place algoritam za sortiranje, pripada grupi sortiranja poredjenjem i optimalan je u smislu ukupnog broja upisivanja u niz. Zasniva se na ideji da se permutacija koju treba sortirati može podeliti na cikluse. Zatim rotiramo cikluse da bi dobili sortiran niz. Vremenska složenost algoritma je O(n²).

Za razliku od skoro svakog drugog sortiranja, ovde se elementi nikada ne upisuju negde u nizu samo da bi bili sklonjeni sa puta. Svaka vrednost je upisana ili nula puta, ako je već na svom mestu, ili tačno jednom, na svoju poziciju. Ovim se postiže minimalan broj upisivanja za kompletno in-place sortiranje. Minimizacija broja pisanja veoma je korisna kada je zapisivanje podataka skupo, npr na EEPROM-u ili fleš memoriji gde svako zapisivanje smanjuje životni vek memorije.

Algoritam

Ovaj algoritam pronalazi cikluse i rotira ih, i na kraju daje sortiran rezultat. Napomena: Opseg (a,b) sadrži brojeve od a do b-1.

# Sort an array in place and return the number of writes.
def cycleSort(array):
  writes = 0
  
  # Loop through the array to find cycles to rotate.
  for cycleStart in range(0, len(array) - 1):
    item = array[cycleStart]
    
    # Find where to put the item.
    pos = cycleStart
    for i in range(cycleStart + 1, len(array)):
      if array[i] < item:
        pos += 1
    
    # If the item is already there, this is not a cycle.
    if pos == cycleStart:
      continue
    
    # Otherwise, put the item there or right after any duplicates.
    while item == array[pos]:
      pos += 1
    array[pos], item = item, array[pos]
    writes += 1
    
    # Rotate the rest of the cycle.
    while pos != cycleStart:
      
      # Find where to put the item.
      pos = cycleStart
      for i in range(cycleStart + 1, len(array)):
        if array[i] < item:
          pos += 1
      
      # Put the item there or right after any duplicates.
      while item == array[pos]:
        pos += 1
      array[pos], item = item, array[pos]
      writes += 1
  
  return writes

Specijalni slučejevi

Kada niz sadrži samo ponovljene vrednosti iz relativno malog opsega brojeva, može se napraviti savršena heš funkcija konstantnog vremena koja značajno ubrzava pronalaženje mesta na koje treba postaviti element, podižući efikasnost sa O(n²) na O(n+k) gde je k broj adresa heš tabele. Na kraju je niz sortiran po redosledu heširanja, pa je važno izabrati dobru heš funkciju koja će niz sortirati na potreban način.

Pre sortiranja treba napraviti histogram, koji će beležiti broj pojavljivanja svakog heša u nizu. Zatim napraviti tabelu koja će sadržati kumulativne sume svakog ulaza histograma. Ta tabela će sadržati poziciju svakog elementa u nizu. Zatim se pravo mesto svakog elementa može pronaći heširanjem (u konstantnom vremenu) i pomoću tabele, umesto linearnom pretragom.

Literatura

• Musser, David (1997). „Introspective Sorting and Selection Algorithms”. Software: Practice and Experience. Wiley. 27 (8): 983—993. doi:10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#. 
• Niklaus Wirth. "Algorithms and Data Structures". Prentice-Hall, Inc., 1985. ISBN 0-13-022005-1.

Spoljašnje veze

• "Cycle-Sort: A Linear Sorting Method", The Computer Journal (1990) 33 (4): 365-367.
• Original source of unrestricted variant