Оптимизация реализации сортировки цикла - PullRequest
Новая
       15

Оптимизация реализации сортировки цикла

1 голос
/ 04 октября 2010

Циклическая сортировка - это сортировка на месте, основанная на идее, что сортируемая перестановка может быть разложена на циклы. Если вы вращаете каждый цикл на одну позицию, массив будет отсортирован. Это может быть легко закодировано, так что число записей в массив является теоретическим минимумом, необходимым для любой сортировки на месте (что хорошо для больших наборов данных, например, на флэш-накопителях, где вы хотите минимизировать количество записей устройство).

Существуют ли способы улучшить время выполнения кода в Википедии , сохраняя при этом сортировку на месте и поддерживая оптимальное количество записей, или это лучшее, что может быть?

Вот реализация (обратите внимание, что range(a, b) идет от a до 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

1 Ответ

3 голосов
/ 04 октября 2010

Дорогая часть этого алгоритма - выяснить, куда идет каждый предмет.В остальном это просто применение перестановки один цикл за раз.Этот код берет O (n ^ 2), чтобы выяснить, куда идут элементы, и O (n), чтобы фактически переместить их.

Если вы хотите использовать некоторое временное хранилище (скажем, DRAM вместо flash,Вы могли бы сделать это намного быстрее, используя временный массив указателей, сортируя их, а затем используя результат для перемещения фактических данных.Вот как вы сортируете большие записи, когда стоимость их многократного перемещения непомерно высока.

Если вам не разрешено иметь O (n lg (n)) бит вспомогательного хранилища, я думаю, что вы могли быповезло.Просто запись, какую перестановку сделать, требует log (n!) = O (n lg (n)) битов памяти.Так что вам нужно будет вычислять перестановку постепенно (как делает циклSort), и я не вижу способа сделать это дешево.

...