CODEWITHSUNDEEP
c++algorithmbubble-sort
Tamer Shlash
Tamer Shlash

Reputation: 9523

Which one is the real Bubble Sort, and which one is better?

I had an argument with a friend about the real bubble sort of the following two algorithms, and about which one is better, no mention which one is mine, I just want to hear your answers on these two questions about those two algorithms (written in c++)

1-which one is the real bubble sort?
2-which one is better?

here are the two algorithms :

// 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;
}           }

Upvotes: 5

Views: 4253

Answers (3)

Steve Blackwell
Steve Blackwell

Reputation: 5924

Number Two is closer to the real one. All comparisons should be between adjacent elements.

But the real bubble sort would take a while loop instead of an outer for loop, and the while loop would execute again only if elements had to be swapped on the last pass, like this:

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);
}

Upvotes: 12

Zac Howland
Zac Howland

Reputation: 15870

The answer to question #2: Neither is "better". Both are O(n^2) sort algorithms (which are terrible). Other than an introduction to sorting algorithms, Bubble Sort is useless.

Upvotes: 1

Alain
Alain

Reputation: 27250

The pseudocode for the nested loop bubble sort is:

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

This means that the first is closest because the inner loop only iterates over elements after i. The second method you showed has an inner loop which iterates over all elements, even though elements before i have already been sorted, so there's no need to waste time on them.

That means the first method is also better.

Upvotes: 1

Related Questions