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

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. Резюме: «обменная сортировка» представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора; фактически в пузырьковой сортировке нет ничего ценного, кроме привлекательного названия. Далее мы рассмотрим улучшенные методы сортировки.