The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Sorting

Problem :-
Implement the Bubble sort algorithm.

Solution :-
This algorithm works by repeatedly iterating over the array elements, comparing each of the adjacent elements and swapping them if necessary. The iteration through the list continues until no swaps are required which indicates that the list is sorted.Complexity of the algorithm is O(n2).
We implement an optimized version of Bubble sort which is based on an observation that 'n'th pass through the array finds the 'n'th largest element in the list and puts it into its final position in the array.
Consider the following array { 7, 2, 5, 3, 4 }. Let's see how Bubble sort technique works :-

First Pass :-
{ 7, 2, 5, 3, 4 } -> { 2, 7, 5, 3, 4 } ( Swap 2 & 7 since 7 > 2 )
{ 2, 7, 5, 3, 4 } -> { 2, 5, 7, 3, 4 } ( Swap 5 & 7 since 7 > 5 )
{ 2, 5, 7, 3, 4 } -> { 2, 5, 3, 7, 4 } ( Swap 3 & 7 since 7 > 3 )
{ 2, 5, 3, 7, 4 } -> { 2, 5, 3, 4, 7 } ( Swap 4 & 7 since 7 > 4 )
Element 7 is placed in its final position in the sorted array.

Second Pass :-
{ 2, 5, 3, 4, 7 } -> { 2, 5, 3, 4, 7 } ( No swapping since 2 < 5 )
{ 2, 5, 3, 4, 7 } -> { 2, 3, 5, 4, 7 } ( Swap 3 & 5 since 5 > 3 )
{ 2, 3, 5, 4, 7 } -> { 2, 3, 4, 5, 7 } ( Swap 4 & 5 since 5 > 4 )
Element 5 is placed in its final position in the sorted array.

Third Pass :-
{ 2, 3, 4, 5, 7 } -> { 2, 3, 4, 5, 7 } ( No swapping since 2 < 3 )
{ 2, 3, 4, 5, 7 } -> { 2, 3, 4, 5, 7 } ( No swapping since 3 < 4 )
Element 4 is placed in its final position in the sorted array.

Fourth Pass :-
{ 2, 3, 4, 5, 7 } -> { 2, 3, 4, 5, 7 } ( No swapping since 2 < 3 )
Element 3 is placed in its final position in the sorted array.

Finally, after four passes, the array is sorted. We could optimize the algorithm further by exiting after the Third Pass in which there were no swaps. In general, we can exit early once we see a pass with no swaps.

#include<iostream>
using namespace std;

// Display the Array
void displayArray(int arr[], int size) {
   int i;
   for (i=0;i<size;i++) {
      cout<<arr[i]<<" ";
   }
}

// swap elements in the array
void swap(int arr[],int idx1,int idx2) {
   int temp;
   temp = arr[idx1];
   arr[idx1] = arr[idx2];
   arr[idx2] = temp;
}

// bubble sort
void bubbleSort(int arr[], int size) {
   int i,j;
   for (i=0;i<(size-1);i++) {
      for (j=0;j<(size-i-1);j++) {
         if (arr[j] > arr[j+1]) {
            swap(arr,j,j+1);
         }
      }
   }
}

// main
int main() {
   int arr[] = {7,4,5,2,3,19,11,6,9,12,8};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"\nOriginal Array :: ";
   displayArray(arr,size);
   bubbleSort(arr,size);
   cout<<"\nSorted Array   :: ";
   displayArray(arr,size);
   cout<<endl;
   return 0;
}

Back | Next

All problems on Sorting
* Implement the Bubble Sort algorithm
* Implement the Selection Sort algorithm
* Implement the Insertion Sort algorithm
* Implement the Merge Sort algorithm
* Implement the Quick Sort algorithm