Какой из них является настоящим Bubble Sort, а какой лучше?

Question

У меня был спор с другом о реальном типе пузырьков следующих двух алгоритмов, и о том, какой из них лучше, не говоря уже о том, какой из них мой, я просто хочу услышать ваши ответы на эти два вопроса об этих двух алгоритмах(написано на С ++)

1 - какой из них является настоящей пузырьковой сортировкой?
2 - какой из них лучше?

вот два алгоритма:

// Number one :
void BubbleSort(int Arr[], int size)
{   for (int i=0;i<size-1;i++)
        for (int j=i+1;j<size;j++)
            if (Arr[i]>Arr[j])
            {   int temp = Arr[i];
                Arr[i] = Arr[j];
                Arr[j] = temp;
}           }

// Number two : 
void BubbleSort(int Arr[], int size)
{   for (int i=0;i<size-1;i++)
        for (int j=0;j<size-1;j++)
            if (Arr[j]>Arr[j+1])
            {   int temp = Arr[j];
                Arr[j] = Arr[j+1];
                Arr[j+1] = temp;
}           }

Answer 1

Номер два ближе к реальному. Все сравнения должны быть между смежными элементами.

Но настоящая пузырьковая сортировка будет использовать цикл while вместо внешнего цикла for, и цикл while будет выполняться снова, только если элементы должны были поменяться местами на последнем проходе, например:

void BubbleSort(int Arr[], int size) 
{   
    bool swapped;
    do {
        swapped = false;
        for (int j=0;j<size-1;j++)
            if (Arr[j]>Arr[j+1]) {
                int temp = Arr[j];
                Arr[j] = Arr[j+1];
                Arr[j+1] = temp;
                swapped = true;
            }
    } while (swapped);
}

Answer 2

Ответ на вопрос № 2: Ни один из них не «лучше». Оба являются O (n ^ 2) алгоритмами сортировки (которые ужасны). Bubble Sort бесполезен, кроме введения в алгоритмы сортировки.

Answer 3

Псевдокод для пузырьковой сортировки с вложенным циклом:

procedure bubbleSort( A : list of sortable items ) 
  n := length(A)-1
  for(i=0; i<= n; i++) 
     for(j=n; j>i; j--) 
        if A[j-1] > A[j] then
           swap (A[j-1], A[j])
        end if
     end for
  end for
end procedure

Это означает, что первый является ближайшим, поскольку внутренний цикл выполняет итерации только по элементам после i.Второй метод, который вы показали, имеет внутренний цикл, который выполняет итерации по всем элементам, даже если элементы уже отсортированы, поэтому не нужно тратить на них время.

Это означает, что первый метод также лучше.