Algorithms for Complete Beginners : Bubble Sort

Part 2 : Bubble Sort

Part 1 : Introduction and Data Structures

Hey again,
         Okay then here i promised the action and i ready to put you up to it. 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 to learn Sorting when the xxx.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

Image from wikipedia : Bubble sort in action

    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;

Pseudo-code

1. S : sequence of sortable items
2. N : no. of elements in S
4. swapped = false
6. loop while swapped == true
7.        swapped = false;
8.        for i = 1 to N-1 do
9.               if( S[i-1] > S[i] )
10.                      temp = S[i-1];
11.                      S[i-1] = S[i];
12.                      S[i] = temp;
13.                      swapped = true;
14.               end if
15.        end for      
16. 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 think much more bllaaed explanation isn't need for this one.
So lets go to the shoooting 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++

1. #include<iostream>
3. using namespace std;
5. int main(){
6.     int S[] = {30,20,50,10,65};
7.     int N = sizeof(S)/sizeof(int);
8.     bool swapped = true;
9.     while(swapped){
10.             swapped = false;
11.             for(int i=1;i<N;i++){
12.                    if(S[i-1] > S[i]){
13.                        int tmp = S[i-1];
14.                        S[i-1] = S[i];
15.                        S[i] = tmp;
16.                        swapped = true;
17.                   }
18.             }
19.     }
20.     //This part isnt in the algorithm, just to print the output
21.     for(int i=0;i<N;i++){
22.             cout << S[i] << " ";
23.     }
24. }

Bubble Sort Implementation in Java

1. class BubbleSort{
2.         public static void main(String args[]){
3.                 int S[] = {30,20,50,10,65};
4.                 int N = S.length;
5.                
6.                 boolean swapped = true;
7.                 while(swapped){
8.                         swapped = false;
9.                         for(int i=1;i<N;i++){
10.                                 if(S[i-1] > S[i]){
11.                                         int temp = S[i-1];
12.                                         S[i-1] = S[i];
13.                                         S[i] = temp;
14.                                         swapped = true;
15.                                 }
16.                         }
17.                 }
18.                
19.                 for(int x:S){
20.                         System.out.print(x + " ");
21.                 }
22.         }
23. }

Output : 10 20 30 60 65


Efficiency or the BIG O ::

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<sup>2


Therefore we denote the efficiency of this algorithm as :</sup> О(n²)

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