Code In Action

Selection Sort :      Selection Sort is an elementary sorting algorithm with O(n^2) running time in worst case. A Real Life Example Illustrating Selection Sort :     Consider you have a pile of electricity bills for the past year, and you want to arrange them in ascending order from staring from January. One approach might be to look through the pile until you find the bill for January and pull that out. Then look through the remaining pile until you find the bill for February and add that behind January. Proceed through the ever-shrinking pile of bills to select next one until you are done. This is the inspiration for our Selection Sort. How Selection Sort Works ?      Just like all elementary sorting algorithms , Selection Sort also contains a double for loop. For every i th iteration of outer for loop, Selection Sort "selects" smallest element in the array, places it into position i. In other words, Selection sort finds ...

Bubble Sort :     Bubble Sort is an elementary sorting algorithm with O(n^2) worst case running time complexity. Bubble Sort is often taught to the novice programmers in introductory Computer Science courses. How Bubble Sort Works?     Bubble Sort consists of a simple double for loop. The first iteration of the inner for loop moves through the array / list from bottom to top i.e from index 0 to index n-1, comparing adjacent keys. If the index at 'i' is greater than the index at 'i+1', then the two values are swapped. Once the highest element encountered this process will cause it to "bubble' up to the top of the array. The second pass through the array repeats this process.     How ever because we know that the highest value is reached to the top of the array on the 1st pass, there is no need to compare top two elements on the second pass. Like wise, each succeeding pass through the array compares adjacent elements, looking at o...

    Mergesort is implemented by John Von Neumann in 1945. Even though very old, it is still used all the time in practice because this is one of the methods of choice for sorting. Mergesort is also preferred for sorting linked lists. First i will start the discussion with an example, Let's see. Consider you have a sheet of paper. First tear the paper into 2 pieces by making the sheet into half, then tear the 2 pieces into 4 pieces, do this for up to some extent. Now give a number to each piece of paper. Take half of the pieces in one hand, another half to another hand and arrange them in order from lowest to highest. Now we will see, How to sort these numbered pieces in ascending order. Compare top sheets of two piles and place the less valued piece on the desk. Now the number of sheets is 1 less than total number of sheets before. By continuing this procedure, you'll end up in the following situations a. No pieces left in both hands b. some piece...

Insertion Sort :     Insertion Sort is an elementary sorting algorithm. It is easy to understand and implement, but is unacceptably slow when there are multiple records to sort. A Real Life Example Illustrating Insertion Sort :     Imagine you have a stack of electricity bills from the past two years & you wish to sort them by date. A fairly natural way to do this might be look at the first two bills & put them in ascending order. Then take the third bill & put it into the right order with respect to the first two & so on. As you take each bill, you would add it to the sorted pile that you have already made. This naturally intuitive process is the inspiration for Insertion Sort. How Insertion Sort Works ?      Insertion Sort starts iteration from second element of the input array/ list. In each iteration the current element is compared with its previous element & swaps, if the previous element is greater tha...