Функция сортировки прямым обменом

Сортировка с помощью прямого обмена

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

каждого соответствует его ключу. В этом случае при каждом проходе один пузырек как бы поднимается до уровня, соответствующего его весу (рис. 3.4). Такой метод известен под именем «пузырьковая сортировка» [1, 3, 9, 10, 13].

void bubbleSort(int numbers[], int array_size

{

int i, j, temp;

for(i = 0; i < array size; i++

for (j {

^array size - 1); j > i; j--

if(numbers[j-1] > numbers[j

{

temp = numbers[j-1]; numbers[j-1] = numbers[j]; numbers[j] = temp;

i = 0 i = 1 i = 2 i = 3 1 = 4 i = 5 i = 6 i = 7

l*f

Щ

Щ

ED3

[iji]

DPI

DPI

rffl

В

~И

l_U

HLt*_l

l_I»a

|[il

■

г^^СРЧ

У- \rM

KifJ

Eir-Л

1S|

— *»gg1

F^l

Рд

«

J 55

Ц

LiZfl

E

Рис. З.4. Пример сортировки

Анализ алгоритма [3]. Число сравнений в алгоритме прямого обмена

С = (п²-п)/2,

а минимальное, среднее и максимальное число перемещений элементов равно со отв етств енно

М_тЫ = О, Мер = 3(п² - п)/2, М_тах = 3(п²-п)/4. Резюме: «обменная сортировка» представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора; фактически в пузырьковой сортировке нет ничего ценного, кроме привлекательного названия. Далее мы рассмотрим улучшенные методы сортировки.

Дата добавления: 2014-11-29