Есть ли только один способ реализовать алгоритм сортировки пузырьков?

Question

Я пытался реализовать свой собственный алгоритм сортировки пузырьков, не глядя на какой-либо псевдокод онлайн, но теперь, когда я успешно это сделал, мой код выглядит действительно отличным от примеров, которые я вижу в Интернете. Все они связаны с заменой переменной, которая является либо истинной, либо ложной. Моя реализация не включает это вообще, так же, как я НЕ сделал вид пузыря?

Вот пример, который я вижу на сайте:

for i = 1:n, 
swapped = false 
for j = n:i+1, 
    if a[j] < a[j-1], 
     swap a[j,j-1] 
     swapped = true 
→ invariant: a[1..i] in final position 
break if not swapped 

конец

Вот моя реализация этого:

void BubbleSort(int* a, int size) 
{ 
    while (!arraySorted(a, size)) 
    { 
     int i = 0; 
     while (i < (size-1)) 
     { 
      if (a[i] < a[i+1]) 
      { 
       i++; 
      } 
      else 
      { 
       int tmp = 0; 
       tmp = a[i+1]; 
       a[i+1] = a[i]; 
       a[i] = tmp; 
       i++; 
      } 
     } 
    } 
} 

Это делает ту же работу, но она делает это любой иначе?

Answer 1

Как отметили некоторые люди, ваша версия без флага работает, но бесполезно медленно.

Однако, если взять оригинальную версию и просто выбросить флаг (вместе с break), он все равно будет работать. Легко видеть из инварианта, который вы удобно разместили.

Версия без перерыва имеет примерно такую ​​же наихудшую производительность, как и при разрыве (наихудший вариант для массива, отсортированного в обратном порядке). Это лучше, чем исходный, если вы хотите, чтобы алгоритм был завершен в заданное время.

Википедия описывает another idea for optimization пузырьковой сортировки, которая включает выброс break.