Sorting Algorithms

Today's post talks of various sorting algortihms already in place to sort unsorted sequence of numbers or infact any list where based on some logic the entities can be compared. To name a few that are commonly heard:





Insertion Sort


Bubble Sort


Quick Sort


Selection Sort


Heap Sort


Merge Sort


Bucket Sort


Radix Sort





Wikipedia provides a good insight into various sorting algorithms.


http://en.wikipedia.org/wiki/sorting_algorithm





Another good reference is available in Data Structures and Algorithms book by Bruno R. Preiss.

Inserion sort implies a linear search starting from either left or right direction and inserting the element at a sorted position w.r.t. all the elements from the sorted direction

and it continues as:

4 7 11 13 15 17 35 45 12 19 3 22

4 7 11 13 15 17 35 45 12 19 3 22

4 7 11 12 13 15 17 35 45 19 3 22

4 7 11 12 13 15 17 19 35 45 3 22

3 4 7 11 12 13 15 17 19 35 45 22

3 4 7 11 12 13 15 17 19 22 35 45

While insertion sort looks easy to implement, its disdvantage is large running time for big unsorted arrays.Check out his interesting animation to understand the disadvange more precisely:

http://www.sorting-algorithms.com/insertion-sort

One good thing about insertion sort is that it does not need any scratch space apart from the sequence being sorted

2 . Bubble Sort

Check out the same animation to figure out the difference yourself:

http://www.sorting-algorithms.com/bubble-sort

3. Merge Sort

Merge Sort needs space in which to merge the elements of its sub-lists.

4. Quick Sort

Quick Sort simply swaps elements around to get them on the correct side of the pivot, as a result equal elements may not be in the same relative order as they were when the sort began.

Again check out the same animation for quick sort to figure out the difference yourself:

http://www.sorting-algorithms.com/quick-sort

Quiz:

1. Can recursion algorithm be effectively applied to insertion sort?

2. How do computers sort data internally?

3. Should bubble sort be taught to beginners?

4. Is quick sort a stable sort?

5. http://www.funtrivia.com/playquiz/quiz2710061f06f18.html