Информатика и технология программирования

       

Обменные сортировки


Обзор алгоритмов сортировки начнем с горячо любимой автором (с методической точки зрения), но с наименее эффективной простой сортировки обменом, или сортировки МЕТОДОМ "ПУЗЫРЬКА". Суть ее заключается в следующем: производится попарное сравнение соседних элементов 0-1,1-2 и т.д. и перестановка, если пара расположена не в порядке возрастания. Просмотр повторяется до тех пор, пока перестановок больше не будет. Метод получил свое название за то, что "более весомые" элементы поднимаются в процессе сортировки к концу массива:


//------------------------------------------------------bk35-03.cpp


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


void sort(int A[], int n)
{
int i,found; // Количество сравнений


do { // Повторять просмотр...


found =0;
for (i=0; i&#60n-1; i++)
if (A[i] &#62 A[i+1]) // Сравнить соседей


{ // Переставить соседей


int cc;
cc = A[i]; A[i]=A[i+1]; A[i+1]=cc;
found++;
}
} while(found !=0); //...пока есть перестановки


}

Оценить трудоемкость алгоритма можно через среднее количество сравнений, которое равно ( n*n -n )/2.

ШЕЙКЕР-СОРТИРОВКА учитывает тот факт, что от последней перестановки до конца массива будут находиться уже упорядоченные данные, например:


шаг n 5 7 10 9 8 12 14
5 7 ***** 8 12 14
последняя перестановка 5 7 9 ***** 12 14
5 7 9 8 10 12 14
шаг n+1 ------------
упорядоченная часть

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



Содержание раздела