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

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

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


каждого соответствует его ключу. В этом случае при каждом проходе один пузырек как бы поднимается до уровня, соответствующего его весу (рис. 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-п)/2,


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

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