Сортировка парными вставками
Модификация сортировки вставками.
Будем забирать в буфер не по одному, а по два элемента. Сначала ищем место вставки для максимального из них. Поскольку второй меньше, место для него можно искать не во всей сортированной области, а начиная с места вставки предыдущего.
type TAI = array of integer; ... procedure PairedInsertionSort(var A: TAI); var i, j: integer; buf: integer; // Вставка одного элемента. function Insertion(Index, aValue, aShift: integer): integer; begin while (Index >= Low(A)) and (A[Index] > aValue) do begin A[Index+aShift] := A[Index]; dec(Index); end; A[Index+aShift] := aValue; result := Index; end; begin i := Low(A); while i<High(A) do begin // Обработка пары в зависимости от того, // кто из них больше. if A[i] > A[i+1] then begin buf := A[i+1]; Insertion(Insertion(i-1, A[i], +2), buf, +1); end else begin buf := A[i]; Insertion(Insertion(i-1, A[i+1], +2), buf, +1); end; inc(i, 2); end; // Если количество элементов нечётно, // обработаем оставшийся. if i=High(A) then Insertion(i-1, A[i], +1); end;
Максимальная | O(N2) |
Минимальная | O(N) |
Средняя | O(N2) |
Метки:
- Войдите или зарегистрируйтесь, чтобы отправлять комментарии