Методы сортировок

Методы сортировок описывают способ реализации перестановки записей (ключей):

1. Если записи небольшие, то можно осуществить их физическое переразмещение в памяти

2. Создать специальную таблицу, описывающую перестановку элементов, и обеспечивающую доступ к элементам, не двигая их так, чтобы в соответствии с упорядоченностью ключей. Перестановка P[i]=j массив перестановок P означает или реализует следующее: i-тая запись займет в ходе перестановки j-тое место. Ki (i=1..n)  Result[p[j]] = R[j]

3. Если записи длинные, а ключи короткие, то для повышения скорости сортировки ключи можно вынести в таблицу ключей – сортировка ключей

4. Если сопутствующая информация и/или ключи занимают много байт памяти, то можно составить новую таблицу адресов, которая указывает на записи. Создаем ссылки и переразмещаем

5. В каждую запись добавляется специальное поле связи, образующее связанный список. Тогда сортировка заключается в изменении этих полей связи так (не переразмещая сами записи), чтобы линейный порядок обхода образовывал упорядоченную последовательность

Типы сортировок

Типы сортировок: внутренняя и внешняя.

Внутренняя предполагает хранение всех записей (исходных результирующих и т.д.) в оперативной памяти, причем в любой момент времени доступен любой элемент.

Внешняя сортировка – данные хранятся на внешнем медленном носителе, а в памяти хранится их подмножество, после операции, над которым данные помещаются обратно на внешнее ЗУ и считывается следующая порция данных.

Критерии оценки сортировок

1. Сравнить по количеству выполняемых операций.

2. Количество сравнений ключей

Заметим, что максимально возможное количество сравнений происходит в случае, когда каждый ключ сравнивается с каждым другим (попарное сравнение) N сравнений. Однако в бинарном поиске, где тоже сравнение, число сравнение равно log₂ N. Так как нам надо расположить N ключей, то можно предположить, что трудоемкость сортировки (при условии времени доступа за O(1) ограниченным диапазоном).

N log₂ N ≤ Ө сортировка ≤ N²

При этом наихудшее время N² имеют алгоритмы, которые нерационально сравнивать. К таким алгоритмам относят пузырек, простую вставку, простой выбор.

Простые схемы сортировок

∑ j=1

Пузырек For i:=1 to n-1 do For j:=n downto i-1 do begin If K[j]<K[j-1] then R[j]  R[j-1]

Простая вставка R[1] – на месте For i:=2 to N do begin j:=i-1; R:=R[i]; while((j>0)and(k[j]<K)) do begin R[j++] R[j]; j--; end; R[j+1]:=R End;

Простой выбор For i:=1 to N do begin nmin:=j; min:=K[j]; for(i:=j+1) to N do IF K[j]<min then begin Min:=K[j]; Nmin:=j; End; R[i]  R[min]; End;

F(n)= ∑_i=1ⁿ ∑_j=1ⁿ 1=1+2+3+....+n = n/2(n+-1)=(n²+-n)/2

0(f(n))=max { n²/2; n/2 } = n²

Заметим, что наибольшее время будет затрачено в том случае, если кроме сравнений (попарных) будет выполнена максимальное количество обменов (сдвигов) записей. Это произойдет в случае пузырька, если самый минимальный элемент занял самое крайнее правое положение , а заодно итерацию внешнего цикла он смещается максимум на одну позицию влево. Улучшится ли время сортировки, если элементы сдвигать не на одну позицию, «скачками» перепрыгивая некоторые позиции, исключая промежуточные переприсваивания, сдвиги и т.д.