Algorithms

What is an Algorithm? Well, you can google for a definition.

Basic algorithm that’s too bad on analysis is Bubble sort. Sorting is always useful in case of implementing searching or eliminating duplicates. Bubble sorting is one of the easiest algorithm anyone can pick up even without a programming knowledge.

The Algorithm is implemented in the Java Language:

class BubbleSort {

public static void main(String args[]){
int []b={21,141,32,51,42,19,7,39,88,78};
int limit = b.length;
for(int i = 0; i < limit-1; i++) {
for(int j = 0; j < limit-1; j++) {
if(b[j] > b[j+1]) {
int temp = b[j];
b[j] = b[j+1];
b[j+1] = temp;
}
}
System.out.print(“Pass ” + (i+1) + “: “);
for(int k = 0; k < limit; k++) {
System.out.print(b[k] + “,”);
System.out.print(“\n”);
}
}
}

This is the rough implementation of the Bubblesort in Java. This is neither the perfect implementation nor its object oriented. But this is what, I came up with without looking at any source. Well you can still make the swap as a new method and the bubble sort too.The output printed for each pass by executing the above program.

Pass 1: 21,32,51,42,19,7,39,88,78,141,
Pass 2: 21,32,42,19,7,39,51,78,88,141,
Pass 3: 21,32,19,7,39,42,51,78,88,141,
Pass 4: 21,19,7,32,39,42,51,78,88,141,
Pass 5: 19,7,21,32,39,42,51,78,88,141,
Pass 6: 7,19,21,32,39,42,51,78,88,141,
Pass 7: 7,19,21,32,39,42,51,78,88,141,
Pass 8: 7,19,21,32,39,42,51,78,88,141,
Pass 9: 7,19,21,32,39,42,51,78,88,141,

I am sure that there is no need to explain this bubble sort. But, we shall learn two important things from this implementation. They are Big-O and Invariants. By looking at the output, you can spot the invariant somehow. Invariant means something or some condition doesn’t change for the whole execution of the algorithm.
Notice in the first pass the last element is sorted. For the second pass, the last and its previous elements are sorted. This condition is the invariant here.

Next, Big-O notation which is the asymptotic analysis of an algorithm. This is the performance indicator and it describes the efficiency of the algorithm for larger input. Let us examine this bubble sort, how many times we iterate the array and compare two values in each pass. Its 9 in the first pass and decreases by one in every pass. So its

9+8+7+6+5+4+3+2+1=45 => (n-1)+(n-2)…..+1 = n(n-1)/2

n^2/2 approximately for large n values, We also have another operation i.e swap. At max, the total swaps will be half time as the comparisons, we get N^2/4 or even N^2/2 itself. So, by ignoring the /4 and /2 we get O(N^2) as the big-o-notation for bubble sort.