Bubble Sort

The bubble sort is one of the simplest sorting algorithms, but not one of the most efficient. It puts a list into increasing order by successively comparing adjacent elements, interchanging them if they are in the wrong order.

Complexity

The bubble sort uses (n-1)n/2 comparisons, so it has (-) (n²) worst-case complexity in terms of the number of comparisons used.

Algorithm

Procedure BubbleSort (num ₁,……num _n )

for i = 1 to n - 1

for j = 1 to n - i

if num _j > num _j+1, then interchange num _j  and num _j+1


{num _j,... num _n  is in increasing order}

Source Code

#include <iostream.h>

int BubbleSort(int [], int);

int main()
{
const int NUMEL = 10;
int nums[NUMEL] = {22,5,67,98,45,32,101,99,73,10};
int i, moves;

moves = BubbleSort(nums, NUMEL);

cout << "The sorted list, in ascending order, is:\n";
for (i = 0; i < NUMEL; ++i)
cout << " " <<nums[i];

cout << '\n' << moves << " were made to sort this list\n";

return 0;
}

int BubbleSort(int num[], int numel)
{
    int i, j, grade, moves = 0;

    for ( i = 0; i < (numel - 1); i++)
        {
         for(j = 1; j < numel; j++)
          {

             if (num[j] < num[j-1])
             {
                    grade = num[j];
                    num[j] = num[j-1];
                    num[j-1] = grade;
                    moves++;
              }
            }
         }

return moves;
}