Сортировка простыми вставками

Выбор из дерева

На рис.33 изображена схема "турнира с выбыванием" для ключей.

Рис.33 Турнир с выбыванием

В корень попадает наибольший ключ. Чтобы выявить второй по величине ключ, нужно выведенный ключ заменить на , тогда в корень попадает второй по величине ключ. Для этого следует изменить лишь один путь в дереве, для чего потребуется не более сравнений. Таким образом, время сортировки пропор­ционально .

Допустим, что ключи t_0…t_k-1 уже упорядочены. В упорядоченной части последовательности найдем место для t_k, на котором ключ t_k не нарушает порядка, и вставим его туда, предварительно сдвинув вправо на одну позицию ключи от места вставки до t_k. Также поступим с последующими ключами.

void InsertSort(int n, int t[]){

int i,j,k,Key;

for(k=0; k<n; k++){

Key=t[k]; // Key – очередной вставляемый ключ

// от k-1 ключа двигаемся влево в поисках первого

// ключа, который меньше Key

// совмещаем поиск места вставки со сдвигом ключей вправо

for(j=k-1; j>=0; j--){

if(t[j]<Key){

break; // нашли

}

t[j+1]=t[j];

}

// новый ключ должен быть установлен в позицию t_j+1

t[j+1]=Key;

}

}

При поиске места вставки k -го ключа необходимо пройти в среднем k/2 ключей, выполняя сравнения и сдвиги. Таким образом, порядок времени работы алгоритма опять составляет величину порядка N². Время поиска места вставки можно уменьшить до ~logN, используя дихотомию, однако количество сдвигов от этого не уменьшится.

9.2.4.6. Сортировка методом "пузырька"

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

void BubbleSort(int n, int t[]){

bool b; // признак того, что в просмотре были обмены

do {

b=false;

for(int k=0; k<n-1; k++){

if(t[k]>t[k+1]){

swap(t[k],t[k+1]);

b=true;

}

}

} while(b);

}

Метод "пузырька" носит такое название, потому что в результате одного просмотра таблицы запись с наибольшим значением ключа перемещается вверх (если считать, что в верхней части таблицы располагаются наибольшие значения ключей), то есть всплывает как пузырек воздуха в жидкости. Время работы алгоритма пропорционально N². Анализ алгоритма довольно сложен и здесь не приводится.

Быстродействие можно несколько улучшить, если просма­тривать массив не далее места последнего обмена местами в предыдущем просмотре, поскольку все ключи правее места последнего обмена уже стоят на своих окончательных местах ("всплыли"). Еще одно усовершенствование – просматривать массив ключей поочередно слева направо, а затем справа налево. Такой метод называется шейкер – сортировкой. Предложенные усовершенствования улучшают быстродействие, однако время работы остается пропорциональным N².

Дата добавления: 2014-12-08