1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Bubble Sort Algorithm for Absolute Beginners

Discussion in 'C++' started by ManzZup, Feb 23, 2012.

  1. ManzZup

    ManzZup New Member

    Joined:
    May 9, 2009
    Messages:
    278
    Likes Received:
    43
    Trophy Points:
    0
    Occupation:
    Production Manager:Software @ ZONTEK
    Location:
    Sri Lanka
    Home Page:
    I thought of starting the whole algorithm series with the most popular Sorting algorithms. Sorting as you know is a way to order a list or a sequence or elements.

    ex: Arranging set of marks to ascending order

    Arranging names to alphabetical order

    Why learn Sorting when sort() is readily available in many languages?

    It's simply because that there are instances you will see that the default sort() will hugely fail although what you need the sorting is for a very tiny part of your algorithm. (lets say to format the output). And going beyond there are instances where your own algorithm makes much sense and efficiency than the default when it comes to custom Objects made by you. So knowing to sort by hand [I mean by yourself :)] is a good practice.

    Bubble Sort



    Probably the slowest or the most inefficient of all the algorithms but on the other hand the whole process is really easy to understand and to manipulate.

    How Bubble Sort works?



    The process is simple, you keep comparing pairs of adjacent elements of the sequence, if the they are in the wrong order swap them and do this till there are no swappings to do.

    ex: Sort an array {5,3,1,4,2} using Bubble Sort
    • {5,3,1,4,2} Compare first two, as 5 > 3, they are swapped
    • {3,5,1,4,2} Again compare next two, as 5 >1, they are swapped
    • {3,1,5,4,2} Like this it keep swapping and iterate[go through] all the elements once to get this
    • {3,1,4,2,5} Now they start doing the second run, comapre 3 & 1, as 3 > 1 they are swapped
    • {1,3,4,2,5} compare 3,4 they are in correct order
    Like wise you compare till no swaps occurr while examining the whole sequence and then the function says "im done with this" and the looping stops;

    The Code



    Pseudo-code

    Code:
    S : sequence of sortable items
    N : no. of elements in S
    swapped = false
    loop while swapped == true
        swapped = false;
        for i = 1 to N-1 do
            if( S[i-1] > S[i] )
                temp = S[i-1];
                S[i-1] = S[i];
                S[i] = temp;
                swapped = true;
            end if
        end for      
    end loop
    
    Explanation:

    First we need to store the sequence in a data structure, for now in an array, we call it S;
    The number of elements of S is N. (Although many languages allow to get this as a property of array some wont, so in the problems you would usually get this number N as a input);
    • Line 4 : we declare a Boolean as swapped and assign true to let the loop below it start. If this becomes false the loop will die.
    • Then onward we loop again inside the array to check for any misplacement of the elements.
    • Line 9 : Checks for it, [Note: if the > is changed to <, the sequence will be sorted descending]
    • Line 10 - 13 : This is a simple way of swapping 2 elements in a sequence, first store one of them in a temporary variable and then change the value of the other.
    I don't think more detailed explanation is needed for this code.

    So lets go to the shooting part of the action, or the real coding part :D [I suggest you to first try coding it yourself before seeing the below code. Challenge Accepted? :D]

    Bubble Sort Implementation in C++

    Code:
    #include<iostream>
    using namespace std;
    int main()
    {
        int S[] = {30,20,50,10,65};
        int N = sizeof(S)/sizeof(int);
        bool swapped = true;
        while(swapped)
        {
            swapped = false;
            for(int i=1;i<N;i++)
            {
                if(S[i-1] > S[i])
                {
                    int tmp = S[i-1];
                    S[i-1] = S[i];
                    S[i] = tmp;
                    swapped = true;
                }
            }
        }
    }
    
    Bubble Sort Implementation in Java

    Code:
    class BubbleSort
    {
        public static void main(String args[])
        {
            int S[] = {30,20,50,10,65};
            int N = S.length;
            boolean swapped = true;
            while(swapped)
            {
                swapped = false;
                for(int i=1;i<N;i++)
                {
                    if(S[i-1] > S[i])
                    {
                        int temp = S[i-1];
                        S[i-1] = S[i];
                        S[i] = temp;
                        swapped = true;
                    }
                }
            }
        }
    }
    
    Code:
    Output : 10 20 30 60 65
    

    Efficiency or the BIG O of Bubble Sort



    So lets do a math after some action played. What we know is that this algorithm isnt really fast. How we know it? because it told it? :D

    NOPE we need to prove it slow using some math. So the math lets take some assumptions;
    1. A general CPU based functions like primary calculations, function call, condition check takes a CPU time of 1. That's from the 1x10^[big number] tasks done by a processor per second, these function required 1 single task, also indicated as accessed in O(1) . [try diving and see the time taken for it ;)]
    2. Time to access an element of an array, or most of the sequences are also equal to 1 or O(1).
    In our example we assume there are 'n' number of elements so in our first while loop we would at most have to iterate n times before quitting

    In every while loop there's a for loop, and a for loop always iterates n-1 times [we are starting from the second element]

    So if take the worst-case-scenario or the case in which the CPU will be burnt with working :D, the number of CPU calls we need to do will be n(n-1) == approx. n^2

    Therefore we denote the efficiency of this algorithm as : О(n^2)

    Now your task is to calculate the CPU calls needed to sort a array of 1x10^10 elements using bubble sort, keep doing this till I comes up with a better sorting algorithm which would reduce your worries a bit :D
     
    shabbir and pradeep like this.
  2. pradeep

    pradeep Team Leader

    Joined:
    Apr 4, 2005
    Messages:
    1,646
    Likes Received:
    86
    Trophy Points:
    0
    Occupation:
    Programmer
    Location:
    Kolkata, India
    Home Page:
    Well written, explained!
     
  3. dearvivekkumar

    dearvivekkumar New Member

    Joined:
    Feb 21, 2012
    Messages:
    29
    Likes Received:
    5
    Trophy Points:
    0
    Thanks a lot for this tutorial, When I had studied this, I was not serious at all. Thanks for brushing up the concept.

    I like to add one more line to this explanation.

    After completion of every inner loop, the last element get sorted(which is the sole of bubble sort), which the author have mentioned somewhat about this when he is calculating the efficiency.

    Code:
    for(int i=1;i<N;i++)
                {
                    if(S[i-1] > S[i])
                    {
                        int temp = S[i-1];
                        S[i-1] = S[i];
                        S[i] = temp;
                        swapped = true;
                    }
                }
    
    Also the c++ code misses the closing "{" .
     
  4. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,287
    Likes Received:
    364
    Trophy Points:
    83
    The missing } was my copy paste error when converted into indented code and is now solved. Thanks for pointing that out.
     
  5. ManzZup

    ManzZup New Member

    Joined:
    May 9, 2009
    Messages:
    278
    Likes Received:
    43
    Trophy Points:
    0
    Occupation:
    Production Manager:Software @ ZONTEK
    Location:
    Sri Lanka
    Home Page:
    @pradeep
    thanks :D
    @dearvivekkumar
    thanks for reminding it, and that put me the idea that the algorithm can be improved to save few loops :)
     
  6. ManzZup

    ManzZup New Member

    Joined:
    May 9, 2009
    Messages:
    278
    Likes Received:
    43
    Trophy Points:
    0
    Occupation:
    Production Manager:Software @ ZONTEK
    Location:
    Sri Lanka
    Home Page:
    @shabbir
    thankx alot for the editing, i could still believe that this become somewhat readable :D
     

Share This Page