More

    [ALGORITHM] BUBBLE SORT

    Sorting is an algorithm that arranges the elements of a list in a certain order. Sorting algorithms can be recursive as well as non-recursive. Recursion is the process of repeating items in a self-similar way. For instance, calling the same method again and again until some condition is met.

    Bubble sort is a simple sorting algorithm. Although the algorithm is simple, most of the other sorting algorithms are more efficient for large lists. The only significant advantage that bubble sort has over most other implementations, even quicksort, is its ability to detect that the list is sorted when used along with a flag to detect swaps. But it is still worth to have a look and it is part of many academic syllabuses for computer science engineering courses. First we will see the traditional bubble sort and then the newver version that uses a flag to detect already sorted lists.

    In bubble sort we start at the beginning of the array, compare first two elements and swap them if the first is greater than second. Now we compare second and third and so on till the end of the array. After this iteration, the largest element will be at the right most side. In the second iteration we will iterate from beginning till (n-1)th element and second largest will be in (n-1) th location. We will have to do a total of (n-1) iterations.  When (n-1) elements are sorted last element will be already sorted.

    ALGORITHM FOR BUBBLE SORT (TRADITIONAL):

    public static void bubbleSort(int arr[], int size)

    {

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

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

         if(arr[j] > arr[j+1])

           swap(arr,j,j+1)

         }

       }

     }

    public static void swap (int arr[], int j, int k){

     int temp=arr[j];

     arr[j]=arr[k];

     arr[k]=temp;

    }

    Performance:

    Best case, average case and worst case takes 0(n2) as both loops are always iterated. We can however improve this algorithm using a flag. When there is no swap during an iteration, we can assume that the array is sorted and stop sorting. This will bring the best case to 0(n). This is the only significant advantage of bubble sort – It can detect whether the input list is already sorted or not.

    ALGORITHM FOR IMPROVED BUBBLE SORT USING FLAG:

    public static void bSort(int arr[], int size){

      Boolean swapped=true;

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

        swapped =false;

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

           if(arr[j] > arr [j+1]){

              swap (arr, j, j+1 );

             swapped=true;

          }

        }

      }

    }

    If there was atleast one swap, swapped will become true. Else swapped will remain false and the sorting ends.

    Every time you learn an algorithm, the best approach to understand it is to try it out using a pen and paper. Take a sample input; go through each step and iteration writing down all variable values. After each of the iterations, you will understand more and more. 

    Recent Articles

    OAUTH – FREQUENTLY ASKED QUESTIONS FOR INTERVIEWS AND SELF EVALUATION

    Why is refresh token needed when you have access token? Access tokens are usually short-lived and refresh tokens are...

    SUMO LOGIC VIDEOS AND TUTORIALS

    Sumo Logic Basics - Part 1 of 2 (link is external) (Sep 29, 2016)Sumo Logic Basics - Part 2 of 2...

    GIT – USEFUL COMMANDS

    Discard all local changes, but save them for possible re-use later:  git stash Discarding local changes...

    DISTRIBUTED COMPUTING – RECORDED LECTURES (BITS)

    Module 1 - INTRODUCTION Recorded Lecture - 1.1 Introduction Part I – Definition

    BOOK REVIEW GUIDELINES FOR COOKBOOKS

    Whenever you add reviews for the book, please follow below rules. Write issues in an excel.Create an excel...

    Related Stories

    Leave A Reply

    Please enter your comment!
    Please enter your name here

    Stay on op - Ge the daily news in your inbox