Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/articles/cpp-tutorials/)
-   -   Bubble Sort Algorithm for Absolute Beginners (http://www.go4expert.com/articles/bubble-sort-algorithm-absolute-beginners-t27883/)

ManzZup 23Feb2012 22:33

Bubble Sort Algorithm for Absolute Beginners
 
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: Cpp

#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: java

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

pradeep 24Feb2012 10:21

Re: Bubble Sort Algorithm for Absolute Beginners
 
Well written, explained!

dearvivekkumar 24Feb2012 11:57

Re: Bubble Sort Algorithm for Absolute Beginners
 
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 "{" .

shabbir 24Feb2012 15:39

Re: Bubble Sort Algorithm for Absolute Beginners
 
The missing } was my copy paste error when converted into indented code and is now solved. Thanks for pointing that out.

ManzZup 24Feb2012 21:17

Re: Bubble Sort Algorithm for Absolute Beginners
 
@pradeep
thanks :D
@dearvivekkumar
thanks for reminding it, and that put me the idea that the algorithm can be improved to save few loops :)

ManzZup 24Feb2012 22:50

Re: Bubble Sort Algorithm for Absolute Beginners
 
@shabbir
thankx alot for the editing, i could still believe that this become somewhat readable :D


All times are GMT +5.5. The time now is 03:14.