DAA — пузырьковая сортировка

Bubble Sort — это элементарный алгоритм сортировки, который работает путем многократного обмена смежными элементами, если это необходимо. Когда обмены не требуются, файл сортируется.

Это самый простой метод среди всех алгоритмов сортировки.

Algorithm: Sequential-Bubble-Sort (A) 
fori← 1 to length [A] do 
for j ← length [A] down-to i +1 do 
   if A[A] < A[j - 1] then 
      Exchange A[j] ↔ A[j-1] 

Реализация

voidbubbleSort(int numbers[], intarray_size) { 
   inti, j, temp; 
   for (i = (array_size - 1); i >= 0; i--) 
   for (j = 1; j <= i; j++) 
      if (numbers[j - 1] > numbers[j]) { 
         temp = numbers[j-1]; 
         numbers[j - 1] = numbers[j]; 
         numbers[j] = temp; 
      } 
} 

Анализ

Здесь количество сравнений

1 + 2 + 3 + … + ( n — 1) = n ( n — 1) / 2 = O ( n ² )

Ясно, что график показывает характер n ² типа пузырьков.

В этом алгоритме число сравнений не зависит от набора данных, т. Е. Находятся ли предоставленные входные элементы в отсортированном порядке или в обратном порядке или в случайном порядке.

Требование к памяти

Из алгоритма, изложенного выше, ясно, что сортировка пузырьков не требует дополнительной памяти.

пример

Несортированный список:

1- ^я итерация:

5> 2 своп

5> 1 своп

5> 4 своп

5> 3 своп

5 <7 без обмена

Своп 7> 6

2- ^я итерация:

2> 1 своп

2 <4 без обмена

Своп 4> 3

4 <5 без обмена

5 <6 без обмена

Нет изменений в 3- ^й , 4- ^й , 5- ^й и 6- ^й итерации.

В заключение,

отсортированный список