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;

- 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 ;)]
- 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