Добавить комментарий
![]() |
Блинная сортировка |
Алгоритм обрёл своё название, потому что может быть использован для сортировки стопки блинов...
Находим максимальный элемент. Переворачиваем стопку от верхнего до максимального. Самый большой блин оказывется наверху. Теперь переворачиваем всю стопку. Самый большой оказался внизу. Неотсортированная часть стопки уменьшилась на один элемент. Повторяем действие с неотсортированной частью.
Т.е. единственной используемой операцией над сортируемыми данными является реверс части последовательности, и переворачиваемая часть всегда с одного края.
type TAI = array of integer; ... procedure PancakeSort(var A: TAI); var i : integer; maxI : integer; // Поиск максимума в левой части массива. // right - правая граница области поиска. function GetMaxIndex(right: integer): integer; var i : integer; max : integer; begin result := Low(A); max := A[result]; for i := Low(A)+1 to right do begin if A[i] >= max then begin max := A[i]; result := i; end; end; end; // Реверс левой части массива. // right - правая граница переворачиваемой части. procedure Reverse(right: integer); var i : integer; begin for i := 0 to (right -1) div 2 do swap(A[i], A[right - i]); end; begin // Несортированная область уменьшается на 1 // на каждом шаге. for i := High(A) downto Low(A)+1 do begin // Найдём положение максимального из несортированных. maxI := GetMaxIndex(i); // Если он уже самый правый, ничего делать не нужно, // просто перейдём к следующей итерации. if maxI < i then begin // Если максимальный элемент не самый левый из несортированных, // перевернём часть массива. if maxI>0 then Reverse(maxI); // Теперь максимальный из несортированных точно самый левый. // Перевернём несортированную область. Reverse(i); // Максимальный из несортированных теперь самый правый, // несортированная область уменьшилась на 1. end; end; end;
Поскольку реверс массива - это ещё один цикл, сложность получается не очень красивой.
Максимальная | O(N3) |
Минимальная | O(N3) |
Средняя | O(N3) |
Метки: