Цикличная сортировка

Основные применения метода цикличной сортировки:
- Ограниченные ресурсы - когда массивы или структуры данных хранятся на устройствах с ограниченными ресурсами.
- Частично отсортированные данные - в таких сценариях временная сложность может быть значительно снижена, поскольку многие элементы могут оказаться уже на своих местах.
- Ограниченные ресурсы - циклическая сортировка выполняется без использования дополнительной памяти.

Алгоритм:
1.    Для каждого элемента массива ищем правильную позицию для вставки этого элемента.
2.    Когда мы находим правильную позицию, проверяем, не находимся ли мы уже в начале цикла. Если да, завершаем текущий цикл.
3.    Вставляем элемент на правильную позицию.
4.    Переходим к следующему элементу и повторяем процесс.
5.    Повторяем процесс до тех пор, пока не отсортируем все элементы.

Пример задачи: Отсортировать массив целых чисел с использованием цикличной сортировки.
 

package main
 
import "fmt"
 
func cycleSort(arr []int) {
      length := len(arr)
 
      for cycleStart := 0; cycleStart < length-1; cycleStart++ {
            item := arr[cycleStart]
            pos := cycleStart
 
            // Находим правильную позицию для текущего элемента
            for i := cycleStart + 1; i < length; i++ {
                  if arr[i] < item {
                        pos++
                  }
            }
 
            // Если текущая позиция совпадает с началом цикла, значит, элемент уже на своем месте
            if pos == cycleStart {
                  continue
            }
 
            // Пропускаем дубликаты
            for item == arr[pos] {
                  pos++
            }
 
            // Перемещаем элемент на его правильную позицию
            if pos != cycleStart {
                  item, arr[pos] = arr[pos], item
            }
 
            // Перемещаем оставшиеся элементы в текущий цикл
            for pos != cycleStart {
                  pos = cycleStart
                  for i := cycleStart + 1; i < length; i++ {
                        if arr[i] < item {
                              pos++
                        }
                  }
 
                  for item == arr[pos] {
                        pos++
                  }
 
                  if item != arr[pos] {
                        item, arr[pos] = arr[pos], item
                  }
            }
      }
}

#ПовторяемАлгосы