I'm comparing insertion sort with a quicksort. I've figured out why the qsort is slower on an almost sorted array but I cant figure out why the insersion sort is so much quicker, surely it still has to compare nearly as many elements in the array?
- Provide more info about your insertion sort. Does it have a check to stop iterating once the array is sorted?Ivaylo Strandjev– Ivaylo Strandjev2012-04-22 12:48:40 +00:00Commented Apr 22, 2012 at 12:48
Add a comment |
5 Answers
The reason that insertion sort is faster on sorted or nearly-sorted arrays is that when it's inserting elements into the sorted portion of the array, it barely has to move any elements at all. For example, if the sorted portion of the array is 1 2 and the next element is 3, it only has to do one comparison -- 2 < 3 -- to determine that it doesn't need to move 3 at all. As a result, insertion sort on an already-sorted array is linear-time, since it only needs to do one comparison per element.
Comments
It depends on several factors. Insertion sort will be more efficient that quick sort on small data sets. It also depends on your backing list implementation (LinkedList or ArrayList). Lastly, it also depends on whether there is any kind of ordering to the input data. For example, if your input data is already sorted in the opposite order and you use a LinkedList, the insertion sort will be blazing fast.
Comments
Quicksort has its worst case (O(n^2) time complexity) on already sorted arrays (see quicksort entry on Wikipedia).
Depending on the choice of the pivot element, this can be alleviated somewhat, but at the same time, the best case for insertion sort is exactly the pre-sorted case (it has O(n) time complexity for such inputs), so it is going to beat quicksort for this particular use case.
Comments
Insertion Sort algorithm runs in a linear time on an sorted array, because for a sorted array , Insertion sort has to do only one comparison , that is for the previous element , as a result Insertion sorting on sorted array has to move linearly , getting to complexity as - O(n). As Compared to Quick Sort where complexity is O(n2)
Comments
Sorted inputs are best case for insertion sort (O(n)) and worst case for quick sort (O(n^2)).
It all has to do with complexity which is determined by number of key comparison which is the basic operation in both algorithm.
So when you see the algorithm of both you find that in insertion sort you only have n comparison as when we insert an element we only compare with left element and its done. On the other hand in case of quick sort u have to keep comparing your pivot element to all your left element and your array kind of decrease by a constant one factor leading to approx n^2 comparison.
