Начнем день с повторения алгоритмов и сегодня у нас в гостях.

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

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

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

По памяти - O(1), по времени - O(n^2)

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

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
                  }
            }
      }
}

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