Bubble Sort

Posted by Anoop Nair on September 7, 2017 Tags: C Data Structures Sorting

What is Sorting ?

Befor we talk about bubble sort you should know what we mean by sorting here. Sortings is the rearranging of the data in an array Arr[ ] so they are in a specific order ascending or descending order. Here we will use bubble sort to arrange elements in ascending order.

Bubble Sort

It is the simplest sorting technique and in it we compare adjacent elements and swap if Arr[1] > Arr[2] and we keep comparing adjacent elements till we get Arr[n-1] < Arr[n]

The first pass which has (n-1) comparisons and sets the largest element in the last position. Similarly the second phase has (n-2) comparisons and it sets the second largest element in the second last position , and this continues till we get a pass with no swaps.

Complexity

As there are (n-1) passes in first pass and (n-2) in second and so onn we get a series for total no. of comparisons f(n) = (n-1) + (n-2) + (n-3) + ..... + 2 + 1 which equates to (n/2)(n-1) = (n^2/2) + O(n) Hence we get the complexity as O(n^2).

Example

Let the array Arr[ ] contain following values { 6, 2, 5, 1, 7}

    
      First pass --> 6 2 5 1 7 --> 2 6 5 1 7 // comparing 6 and 2 and swaping.
                     2 6 5 1 7 --> 2 5 6 1 7 // comparing 6 and 5 and swaping.
                     2 5 6 1 7 --> 2 5 1 6 7 // comparing 6 and 1 and swaping.
                     2 5 1 6 7 --> 2 5 1 6 7 // comparing 6 and 7 and not swaping as Arr[n]> Arr[n-1]

     Second pass --> 2 5 1 6 7 --> 2 5 1 6 7
                     2 5 1 6 7 --> 2 1 5 6 7
                     2 1 5 6 7 --> 2 1 5 6 7
                     2 1 5 6 7 --> 2 1 5 6 7

      Third pass --> 2 1 5 6 7 --> 1 2 5 6 7
                     1 2 5 6 7 --> 1 2 5 6 7
                     1 2 5 6 7 --> 1 2 5 6 7
                     1 2 5 6 7 --> 1 2 5 6 7

      // The array is sorted after 3 passes but the important point to note is that the loop
      // stops when there are no swaps in the whole pass. Hence there will be a fourth pass.

     Fourth pass --> 1 2 5 6 7 --> 1 2 5 6 7
                     1 2 5 6 7 --> 1 2 5 6 7
                     1 2 5 6 7 --> 1 2 5 6 7
                     1 2 5 6 7 --> 1 2 5 6 7
    
  

Bubble Sort Program in C

    
      void swap(int *a, int *b);
      void bubbleSort(int arr[], int n);

      // main driver function
      int main()
      {
          int arr[20] , i, n;
          printf("Enter the size of array \n");
          scanf("%d", &n);

          printf("Enter the values of array \n");
          for(i=0; i< n ; i++){
              scanf("%d", &arr[i]);
          }

          bubbleSort(arr, n); // function call

          printf("\n the sorted array \n");
              for(i=0; i< n; i++){
                  printf("%d \n", arr[i]);
              }
          return 0;
      }

      //bubble sort function

      void bubbleSort(int arr[], int n){
          int i, j;
          for(i=1; i< n-1; i++){
              for(j=0 ; j<= n-i-1 ; j++){
                if( arr[j] > arr[j+1]){
                  swap(&arr[j], &arr[j+1]); // Swap function call
                 }
              }
          }
      }
      // Swap function
      void swap(int *a, int *b){
          int temp;
          temp = *b ;
          *b = *a ;
          *a = temp;
      }

    
  

Output

output

Follow the following links to see learn more about sorting techniques.


COMMENTS