why different sorting algorithms ?
why people are in need of different sorting algorithms ?
there are a lot of metrics to compare sorting algorithms on like :
- complexity ( usually it resembles the time taken in sorting ) in the best cases , worst cases & random cases as well
- memory usage < some sorting algorithms need to make a temporary locations to store data which needs more memory >
- adaptability < there are some sorting algorithms that benefits from the presorted elements even they have high complexity > it’s not reasonable to resort millions of entries when one element only is not sorted
n |
10 |
100 |
1000 |
10000 |
100000 |
10^6 |
10^7 |
10^8 |
nlogn |
10 |
200 |
3000 |
40000 |
500000 |
6 X 10^6 |
7 X 10^7 |
8 X 10^ 8 |
n^2 |
100 |
10000 |
10^6 |
10^8 |
10^10 |
10^12 |
10^15 |
10^16 |
if we used the 3 sorting algorithms above to sort 10^8 elements :
if the first algorithm of complexity n took 27 hours
the second one of complexity nlogn will take 8 times the time above 222 hours ,
But the third algorithm could take about 325114 YEARS !!!!!!!!!
before Going through different sorting algorithms , i wanted to share a Funny Video that demonstrates
3 different sorting algorithms 🙂 , it will ease explanation of them afterwards .
Bubble sort ( complexity O(n^2 ) ) :
Bubble sort | best case complexity ![]() |
average case complexity ![]() |
worst case complexity ![]() |
advantages : Tiny code size |
it’s a simple sorting algorithm to write it’s code yet it’s very complex algorithm , it could take days to sort few millions of elements
even Obama Know this 😀
it depends on 3 simple steps :
repeat those 3 steps until the array is sorted :
- loop on the array
- compare each to consecutive elements , and switch them if they are not sorted
- go to step 1
watch this video , it explains a lot ( you can skip the other kind of sorting )
you can check it’s code
void bubbleSort (Array S, length n) { boolean isSorted = true ; while(!isSorted) { // repeat until it's sorted isSorted = true; for(i = 0; i<n-1; i++) { // step one loop on the elements if(S[i] > S[i+1]) // compare each two consecutive elements { int temp = S[i]; S[i] = S[i+1]; S[i+1] = temp ; isSorted = false; // if all elements are sorted the flag wont change } } } n--; }
the best case here is when the array is already sorted or consecutive elements are only unsorted so it will be sorted by one while loop only so it has complexity n
the worst case here will occur if the array is reversed , you will need to loop in the while loop for n times so it’s complexity will be n^2
insertion sort (O(n^2)) :
Insertion sort | best case ![]() |
average case ![]() |
worst case ![]() |
so it’s a basic algorithm like sorting a pile of cards ,from left to right you pick a card and insert in into the right place then the preceding another card and so on till the pile is sorted
take a look on this video
yet another way of stupid slow sorting algorithm 😀 the only difference than before is that Obama forgot to mention it kidding 😀
actually insertion sort is faster than bubble sort when dealing with presorted elements in the array , how ??
imagine you are handling the element that already in sorted in it’s place ,
all that you need it to compare it to the largest element in the left sorted array to recognize it’s bigger than it and it’s in the right place
Merge sort ( O(nlog(n)) ):
Merge sort | Best case n log (n) | average case n log (n) | worst case n log (n) | advantages : too fast compared to n^2 complexity |
it’s considered as a fast search algorithm and least complexity , it depends on a basic rule , is that sorting and merging small arrays is too much faster than sorting large array .
it uses 3 basic rules :
- arrays of one element only are already sorted
- divide any array into two halves and so on till you have n arrays each of one element
- merging each two consecutive arrays in order // so if we need to merge those two arrays in figure we will need to compare the first elements in each array then drop down the smaller into the new array
then compare the next two selected elements and so on till the whole array is merged
take a look on this video :
so why it has complexity of nlog(n) ??? :
each level consists of n elements , merging depends on comparison of each to elements so merging each level will have complexity of O(n) and since we have log(n) levels , so merging will be repeated log(n) times
over all we will have complexity of O(nlog(n)) .
…to be continued with more Sorting algorithms ( quick sort , selection sort , heap sort , BST sort ) =)
thanks goes to :
- president Obama 😀
- wikipedia : http://en.wikipedia.org/wiki/Sorting_algorithm
- http://xoax.net/ : these Guys has a really good stuff to watch their youtube channel
- @codeGuru on twitter
- and those helpful Guys on stackoverflow.com , http://www.codeproject.com
May 31, 2011 @ 09:32:57