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 
let’s take a look how complexity could be a big deal : 
if we have 3 sorting algorithms  n , nlogn , n^2  

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  !!!!!!!!! 

Complexity Chart

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 \mathcal{} n  average case complexity \mathcal{} n^2 worst case complexity  \mathcal{} n^2 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 : 

  1. loop on the array 
  2. compare each to consecutive elements , and switch them if they are not sorted 
  3. 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  \mathcal{} n  average case \mathcal{} n^2  worst case   \mathcal{} n^2

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  )  =)

click here for part two 

thanks goes to :

Advertisements