Bubble Sort

Bubble Sort is an elementary sorting algorithm. It works by repeatedly exchanging adjacent elements, if necessary. When no exchanges are required, the file is sorted. 

SEQUENTIAL BUBBLESORT (A)

for i ← 1 to length [A] do

    for j ← length [A] downto i +1 do

        If A[A] < A[j-1] then

            Exchange A[j] ↔ A[j-1]

Here the number of comparison made

            1 + 2 + 3 + . . . + (n - 1) = n(n - 1)/2 = O(n2)

Clearly, the graph shows the n2 nature of the bubble sort.

In this algorithm the number of comparison is irrespective of data set i.e., input whether best or worst.

Memory Requirement:

Clearly, bubble sort does not require extra memory.

Implementation

void bubbleSort(int numbers[], int array_size)

{  int i, j, temp;

for (i = (array_size - 1); i >= 0; i--)

  {    for (j = 1; j <= i; j++)

    {   if (numbers[j-1] > numbers[j])

      {   temp = numbers[j-1];

        numbers[j-1] = numbers[j];

        numbers[j] = temp;

      }

    }

  }

}