Bubble Sort

 

Bubble Sort:

Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order. This algorithm is not suitable for large data sets as its average and worst case complexity are of O (n2) where n is the number of items.

Algorithm:

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that works as follows:

1. Start by comparing the first two elements of the array.
2. If the first element is greater than the second, swap them.
3. Move to the next pair of adjacent elements and repeat the comparison and swapping process.
4. Continue this process until you reach the end of the array.
5. After the first pass, the largest element will have “bubbled up” to the end of the array.
6. Repeat steps 1-5 for the remaining elements (excluding the last one).
7. Continue this process until the entire array is sorted.

Bubble sort has a time complexity of

O(N2)

We assume list is an array of n elements. We further assume that swap function swaps the values of the given array elements.

begin BubbleSort(list)     for all elements of list       if list[i] > list[i+1]          swap(list[i], list[i+1])       end if    end for        return list     end BubbleSort15

 

Pseudocode:

 Pseudocode of BubbleSort algorithm can be written as follows :

 

func bubblesort( var a as array )     for i from 1 to N         for j from 0 to N - 1            if a[j] > a[j + 1]               swap( a[j], a[j + 1] ) end func

 

Program :

// Bubble sort in C++

#include <iostream>

using namespace std;

// perform bubble sort

void bubbleSort(int array[], int size) {

  // loop to access each array element

  for (int step = 0; step < size-1; ++step)

    // loop to compare array elements

    for (int i = 0; i < size - step-1; ++i) {

      // compare two adjacent elements

      // change > to < to sort in descending order

      if (array[i] > array[i + 1]) {

        // swapping elements if elements

        // are not in the intended order

        int temp = array[i];

        array[i] = array[i + 1];

        array[i + 1] = temp;

      }

    }

  }

}

// print array

void printArray(int array[], int size) {

  for (int i = 0; i < size; ++i) {

    cout << "  " << array[i];

  }

  cout << "\n";

}

int main() {

  int data[] = {-2, 45, 0, 11, -9};

  // find array's length

  int size = sizeof(data) / sizeof(data[0]);

 

  bubbleSort(data, size)

  cout << "Sorted Array in Ascending Order:\n"; 

  printArray(data, size);

}

Output