Добавить комментарий
![]() |
Двойная сортировка выбором |
Попытка усовершествовать классическую сортировку выбором.
На каждом проходе будем находить не только минимальный, но и максимальный элемент.
Тогда на каждом проходе неотсортированная область будет уменьшатся на два элемента. Понадобится вдвое меньше проходов.
Но количество сравнений на каждом проходе удвоится, а количество перестановок останется неизменным.
Как результат, выигрыш получается минимальным, а при неаккуратной реализации Двойная сортировка выбором может оказаться даже медленнее обычной.
type TAI = array of integer; ... procedure DoubleSelectionSort(var A: TAI); var j : integer; minV, minI : integer; maxV, maxI : integer; left, right : integer; begin left := Low(A); right := High(A); while left<right do begin minV := A[left]; minI := left; maxV := A[right]; maxI := right; for j := left to right do begin if A[j] < minV then begin minV := A[j]; minI := j; end; if A[j] > maxV then begin maxV := A[j]; maxI := j; end; end; if minI > left then begin swap(A[left], A[minI]); if maxI = left then maxI := minI; end; if maxI < right then begin swap(A[right], A[maxI]); end; inc(left); dec(right); end; end;
Максимальная | O(N2) |
Минимальная | O(N2) |
Средняя | O(N2) |
Метки: