Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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;
}           }
like image 868
Tamer Shlash Avatar asked Dec 03 '10 17:12

Tamer Shlash


People also ask

Which one is better bubble sort or selection sort?

Selection sort performs a smaller number of swaps compared to bubble sort; therefore, even though both sorting methods are of O(N2), selection sort performs faster and more efficiently!

Which sorting algorithm is best?

Quicksort is one of the most efficient sorting algorithms, and this makes of it one of the most used as well. The first thing to do is to select a pivot number, this number will separate the data, on its left are the numbers smaller than it and the greater numbers on the right.

What is the best case efficiency of bubble sort in the improvised version?

What is the best case efficiency of bubble sort in the improvised version? Explanation: Some iterations can be skipped if the list is sorted, hence efficiency improves to O(n). 10.

Which algorithm is better for sorting between bubble sort and quicksort?

Given that average case for Bubble Sort is the worst case for Quick Sort, it is safe to say that Quick Sort is the superior sorting algorithm. For short arrays (under 1,000 elements), the benefits of Quick Sort are minimal, and might be outweighed by it's complexity, if the goal is readability.


2 Answers

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);
}
like image 165
Steve Blackwell Avatar answered Nov 07 '22 14:11

Steve Blackwell


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.

like image 1
Alain Avatar answered Nov 07 '22 15:11

Alain