Визуализация
Данные: Случайные
Легенда цветов
Как работает сортировка циклами
Идея алгоритма. Для каждого элемента подсчитываем, сколько значений в массиве меньше него - это и есть его целевая позиция. Ставим элемент на место, вытесняя тот, кто там стоял, и повторяем, пока цикл не замкнется. Каждый элемент записывается ровно один раз.
Что такое цикл перестановки. Элемент a[0] должен встать, скажем, на позицию 3. Тот, кто стоял на позиции 3, в свою очередь, должен встать на позицию 5. И так далее, пока цепочка не вернется к позиции 0. Эта цепочка и есть цикл.
Минимум записей. Каждый элемент записывается в массив ровно один раз - сразу на свое финальное место. Ни одна другая сортировка сравнением не может сделать меньше записей. Это важно, когда запись дорогая - например, во flash-память с ограниченным ресурсом перезаписи.
- Случайные - обычный случай, O(n²) сравнений, но записей не более n.
- В обратном порядке - максимум циклов, но записей по-прежнему не более n.
- Почти отсортированные - мало циклов, мало записей.
- С повторами - дубли обрабатываются корректно: при совпадении значений позиция сдвигается.
- Одинаковые - все элементы уже на месте, записей ноль.
Синонимы названия. Сортировка циклами, цикличная сортировка, Cycle Sort.
Сложность алгоритма
Сложность - это оценка того, как быстро растет потребление ресурса при росте длины массива n. Ресурса у алгоритма два, поэтому и оценки две: по времени и по памяти. Обе записывают через O-нотацию - у нас есть отдельная анимация о том, как читать такие записи.
По времени
Показывает, как растет число операций (здесь это сравнения и записи) при росте n. Лейбл "Сложность" под визуализацией - время, которое получилось фактически на ваших данных.
| Случай | Время | Комментарий |
|---|---|---|
| Все случаи | O(n²) | Квадратичное число сравнений, но записей не более n - оптимально |
По памяти
Показывает, сколько дополнительной памяти нужно алгоритму. Сам входной массив в эту оценку не входит: дополнительной считается память сверх него.
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Дополнительная память | O(1) | Сортировка на месте: хватает одной временной переменной для обмена, сколько бы элементов ни было |
Устойчивость алгоритма
Устойчивой называется сортировка, которая не меняет взаимный порядок равных элементов. Пример: сортируем учеников по оценке, а внутри одной оценки они уже стояли по алфавиту. Устойчивая сортировка сохранит алфавитный порядок внутри каждой оценки, неустойчивая - может перемешать.
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Устойчивость | Нет | При отправке элемента на его целевую позицию он может перепрыгнуть через равные ему элементы. Алгоритм неустойчив. |
Примеры реализации циклической сортировки (Cycle Sort)
Код на C
void cycle_sort(int arr[], int n) {
// Проходим по массиву, чтобы найти цикл для каждого элемента
for (int cs = 0; cs < n - 1; cs++) {
int item = arr[cs]; // Сохраняем текущий элемент
int pos = cs; // Ищем позицию, куда нужно поставить item
// Считаем количество элементов, строго меньших item
for (int i = cs + 1; i < n; i++)
if (arr[i] < item) pos++;
// Если элемент уже на своей позиции - пропускаем
if (pos == cs) continue;
// Пропускаем дубликаты: если на позиции pos уже стоит item, сдвигаемся дальше
while (item == arr[pos]) pos++;
// Ставим элемент на его законное место и забираем тот, что там стоял
if (pos != cs) {
int temp = item;
item = arr[pos];
arr[pos] = temp;
}
// Продолжаем двигаться по циклу перестановки, пока не вернемся в начало (cs)
while (pos != cs) {
pos = cs;
// Снова подсчитываем элементы, чтобы найти место для нового item
for (int i = cs + 1; i < n; i++)
if (arr[i] < item) pos++;
// Снова пропускаем дубликаты
while (item == arr[pos]) pos++;
// Ставим элемент на место и забираем вытесненный
if (item != arr[pos]) {
int temp = item;
item = arr[pos];
arr[pos] = temp;
}
}
}
}Код на Python
def cycle_sort(arr):
n = len(arr)
# Итерация по каждому элементу массива
for cs in range(n - 1):
item = arr[cs] # Элемент, для которого будем искать правильную позицию
pos = cs
# Подсчитываем, сколько элементов справа меньше нашего item
for i in range(cs + 1, n):
if arr[i] < item:
pos += 1
# Если элемент уже находится на своем месте
if pos == cs:
continue
# Пропускаем одинаковые значения (дубликаты), сдвигая позицию
while item == arr[pos]:
pos += 1
# Меняем элементы местами. item теперь хранит вытесненный элемент
arr[pos], item = item, arr[pos]
# Пока цикл не замкнется (не вернемся к начальному индексу cs)
while pos != cs:
pos = cs
# Ищем новую позицию для вытесненного элемента
for i in range(cs + 1, n):
if arr[i] < item:
pos += 1
# Игнорируем дубликаты
while item == arr[pos]:
pos += 1
# Ставим вытесненный элемент на его место, а новый вытесненный забираем в item
arr[pos], item = item, arr[pos]
return arrКод на JavaScript
function cycleSort(arr) {
const n = arr.length;
// Проходим по каждому индексу массива
for (let cs = 0; cs < n - 1; cs++) {
let item = arr[cs]; // Запоминаем элемент, который начнет цикл
let pos = cs;
// Считаем все элементы, которые меньше item. Это даст нам правильный индекс для item
for (let i = cs + 1; i < n; i++) {
if (arr[i] < item) pos++;
}
// Если элемент уже на месте, переходим к следующему
if (pos === cs) continue;
// Обработка дубликатов: сдвигаем индекс вправо, если значение уже совпадает
while (item === arr[pos]) pos++;
// Выполняем первую замену (одну запись в массив)
if (pos !== cs) {
let temp = item;
item = arr[pos];
arr[pos] = temp;
}
// Замыкаем цикл перестановки: продолжаем искать места для вытесненных элементов
while (pos !== cs) {
pos = cs;
// Ищем позицию для вытесненного элемента
for (let i = cs + 1; i < n; i++) {
if (arr[i] < item) pos++;
}
// Снова пропускаем возможные дубликаты
while (item === arr[pos]) pos++;
// Если мы не записываем элемент сам в себя - выполняем обмен
if (item !== arr[pos]) {
let temp = item;
item = arr[pos];
arr[pos] = temp;
}
}
}
return arr;
}Хотите разобрать тему глубже? В нашем бесплатном курсе есть урок про сортировку выбором и циклическую сортировку - с подробной теорией, задачами и проверочными вопросами.