28 Oct 2014

Insertion faster than quick and bubble



Answers:

2)Suggestion: If a list is already sorted, quicksort needs to go through all the recursive steps to get to n lists of size 1. Both of these take time. But the insertion sort will iterate though the list once and find out that it is done. This is the fastest for this case.
When the list is small, the overhead to make recursive calls and finding the pivot value, etc is much slower than the iterative process used in insertion sort.

1)Suggestion: Actual complexity of each sorting algorithm is as follows:
1.      Best - Insertion Sort: O(N ^ 2), O(N), O(N ^ 2)
2.      Average - Quick Qort: O(N ^ 2), O(N log N), O(N log N)
3.      Worst - Bubble Sort: O(N ^ 2), O(N), O(N ^ 2)



No comments:

Post a Comment