Цикличная сортировка
Возьмём элемент. Найдём для него подходящее место в массиве. Поместим элемент в найденное место, а элемент, который занимал нужное нам место, извлечём и поищем нововое расположение теперь для него... Продолжаем, пока на найдётся элемент, который нужно положить на место того, с которого мы начали. Круг замкнулся.
Повторим такие циклы для каждого элемента массива слева направо.
На i-й итерации все элементы левее i-го уже стоят на своих местах. Анализировать нужно только тех, кто правее i-й позиции.
А чтобы определить правильное место, элемента, достаточно посчитать, сколько элементов меньше него (на сколько позиций правее он должен быть).
type TAI = array of integer; ... procedure CycleSort(var A: TAI); var i: integer; buf: integer; // Буфер для элемента, которому мы ищем место. // Один шаг алгоритма. // StartPos - Начальная позиция в массиве. // Всё что левее, уже отсортировано. // Buffer - значение элемента, которому ищем место. // Функция найдёт новое место в массиве A для значения Buffer и поместит // его туда, а ранее находившийся там элемент вернёт в Buffer. // First - признак первого прохода в итерации. Если элемент уже стоит на своём месте, // дальнейшие действия не нужны и можно сразу переходить к следующей итерации. function Step(StartPos: integer; var Buffer: integer; First: boolean): integer; var j: integer; begin // Ищем правильное место для значения Buffer result := StartPos; for j := StartPos+1 to High(A) do if A[j] < Buffer then inc(result); // Если элемент уже на правильном месте на первом шаге в итерации, // мы закончили. if First and (result = StartPos) then Exit; // Если в выбранном месте находятся дубликаты элемента Buffer, // разместимся сразу после них. while Buffer = A[result] do inc(result); // Обменяем значения Buffer и выбранного элемента. swap(Buffer, A[result]); end; begin // Для всех элементов массива. for i := Low(A) to High(A)-1 do begin // Отложим текущий элемент в буфер. buf := A[i]; // Если элемент в буфере не на своём месте, if Step(i, buf, true) <> i then // продолжаем цикл пока очередной элемент не окажется на месте // стартового элемента этой итерации. while Step(i, buf, false) <> i do ; end; end;
Большое количество сравнений обычно делает этот алгоритм не слишком эффективным. Его область применения - задачи в которых велика стоимость записи в массив. Количество перестановок в этом алгоритме минимально.
Максимальная | O(N2) |
Минимальная | O(N2) |
Средняя | O(N2) |
- Войдите или зарегистрируйтесь, чтобы отправлять комментарии