Cycle sort

Cycle sort
Cycle sort
Example of cycle sort sorting a list of random numbers.

Example of cycle sort sorting a list of random numbers.
Class Sorting algorithm
Data structure Array
Worst case performance Θ(n2)
Best case performance Θ(n2)
Average case performance Θ(n2)
Worst case space complexity Θ(n) total, Θ(1) auxiliary

Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array, unlike any other in-place sorting algorithm. It is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result.

Unlike nearly every other sort, items are never written elsewhere in the array simply to push them out of the way of the action. Each value is either written zero times, if it's already in its correct position, or written one time to its correct position. This matches the minimal number of overwrites required for a completed in-place sort.

Minimizing the number of writes is useful when making writes to some huge data set is very expensive, such as with EEPROMs or Flash memory where each write reduces the lifespan of the memory.

Algorithm

The following algorithm finds cycles and rotates them, giving a sorted result. Note that range(a, b) goes from a to 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

Specific-situation optimizations

When the array contains only duplicates of a relatively small number of items, a constant-time perfect hash function can greatly speed up finding where to put an item1, turning the sort from Θ(n2) time to Θ(n + k) time, where k is the total number of hashes. The array ends up sorted in the order of the hashes, so choosing a hash function that gives you the right ordering is important.

Before the sort, create a histogram, sorted by hash, counting the number of occurrences of each hash in the array. Then create a table with the cumulative sum of each entry in the histogram. The cumulative sum table will then contain the position in the array of each element. The proper place of elements can then be found by a constant-time hashing and cumulative sum table lookup rather than a linear search.

External links

^ "Cycle-Sort: A Linear Sorting Method", The Computer Journal (1990) 33 (4): 365-367.


Wikimedia Foundation. 2010.

См. также в других словарях:

  • Cycle Soufre-iode — Le cycle iode soufre (cycle IS ou S I en anglais) est une série de processus thermochimiques utilisée pour la production d hydrogène. Il consiste en trois réactions chimiques dont le réactif net est l eau et dont les produits nets sont de l… …   Wikipédia en Français

  • Cycle soufre-iode — Le cycle iode soufre (cycle IS ou S I en anglais) est une série de processus thermochimiques utilisée pour la production d hydrogène. Il consiste en trois réactions chimiques dont le réactif net est l eau et dont les produits nets sont de l… …   Wikipédia en Français

  • Cycle De Thongor — Le Cycle de Thongor est un cycle de six romans de fantasy écrits par Lin Carter entre 1965 et 1970. Il retrace les aventures du barbare Thongor à travers la Lémurie, un continent imaginaire censé dater d il y a un demi million d années. Les deux… …   Wikipédia en Français

  • Cycle de thongor — Le Cycle de Thongor est un cycle de six romans de fantasy écrits par Lin Carter entre 1965 et 1970. Il retrace les aventures du barbare Thongor à travers la Lémurie, un continent imaginaire censé dater d il y a un demi million d années. Les deux… …   Wikipédia en Français

  • Cycle De L'Assassin Royal — Le cycle de l Assassin royal (The Farseer Trilogy et The Tawny Man) est une série de romans de Robin Hobb, parue entre 1996 et 2004, et qui se déroule dans un monde médiéval fantastique. Cette série de treize romans dans sa version française[1]… …   Wikipédia en Français

  • Cycle de l'Assassin Royal — Le cycle de l Assassin royal (The Farseer Trilogy et The Tawny Man) est une série de romans de Robin Hobb, parue entre 1996 et 2004, et qui se déroule dans un monde médiéval fantastique. Cette série de treize romans dans sa version française[1]… …   Wikipédia en Français

  • Cycle de l'assassin royal — Le cycle de l Assassin royal (The Farseer Trilogy et The Tawny Man) est une série de romans de Robin Hobb, parue entre 1996 et 2004, et qui se déroule dans un monde médiéval fantastique. Cette série de treize romans dans sa version française[1]… …   Wikipédia en Français

  • Cycle De La Compagnie Noire — Pour les articles homonymes, voir Compagnie noire. Le Cycle de la Compagnie noire est une série de romans de fantasy écrite par Glen Cook. L ambiance sombre et dénuée de tout manichéisme les fait souvent classer dans la catégorie dark fantasy.… …   Wikipédia en Français

  • Cycle de la Compagnie Noire — Pour les articles homonymes, voir Compagnie noire. Le Cycle de la Compagnie noire est une série de romans de fantasy écrite par Glen Cook. L ambiance sombre et dénuée de tout manichéisme les fait souvent classer dans la catégorie dark fantasy.… …   Wikipédia en Français

  • Cycle de la compagnie noire — Pour les articles homonymes, voir Compagnie noire. Le Cycle de la Compagnie noire est une série de romans de fantasy écrite par Glen Cook. L ambiance sombre et dénuée de tout manichéisme les fait souvent classer dans la catégorie dark fantasy.… …   Wikipédia en Français


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»