Циклично сортирање

С Википедије, слободне енциклопедије
Циклично сортирање
Намена сортирање
Структура података Низ
Временска компл. O(n²)
Меморијска компл. O(n)
Стабилан не

Циклично сортирање представља нестабилни, ин-плаце алгоритам за сортирање, припада групи сортирања поредјењем и оптималан је у смислу укупног броја уписивања у низ. Заснива се на идеји да се пермутација коју треба сортирати може поделити на циклусе. Затим ротирамо циклусе да би добили сортиран низ. Временска сложеност алгоритма је О(н²).

За разлику од скоро сваког другог сортирања, овде се елементи никада не уписују негде у низу само да би били склоњени са пута. Свака вредност је уписана или нула пута, ако је већ на свом месту, или тачно једном, на своју позицију. Овим се постиже минималан број уписивања за комплетно ин-плаце сортирање. Минимизација броја писања веома је корисна када је записивање података скупо, нпр на ЕЕПРОМ-у или флеш меморији где свако записивање смањује животни век меморије.

Алгоритам[уреди | уреди извор]

Овај алгоритам проналази циклусе и ротира их, и на крају даје сортиран резултат. Напомена: Опсег (а,б) садржи бројеве од а до б-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

Специјални случејеви[уреди | уреди извор]

Када низ садржи само поновљене вредности из релативно малог опсега бројева, може се направити савршена хеш функција константног времена која значајно убрзава проналажење места на које треба поставити елемент, подижући ефикасност са О(n²) на О(n+k) где је k број адреса хеш табеле. На крају је низ сортиран по редоследу хеширања, па је важно изабрати добру хеш функцију која ће низ сортирати на потребан начин.

Пре сортирања треба направити хистограм, који ће бележити број појављивања сваког хеша у низу. Затим направити табелу која ће садржати кумулативне суме сваког улаза хистограма. Та табела ће садржати позицију сваког елемента у низу. Затим се право место сваког елемента може пронаћи хеширањем (у константном времену) и помоћу табеле, уместо линеарном претрагом.

Литература[уреди | уреди извор]

Спољашње везе[уреди | уреди извор]

Преузето из „https://sr.wikipedia.org/w/index.php?title=Ciklično_sortiranje&oldid=26735745”