Friday, August 19, 2016

bubble sort vs insertion sort

In Bubble sort , at every iteration you find a largest number and push it to bottom (Bubble out larger number) 
In Insertion sort you have two regions one sorted and another unsorted. 
At Every Iteration you pick up an element from unsorted region and insert at proper location in Sorted region. 

Insertion Sort and Bubble sort both have Worst Case O(N^2).
But if the array is mostly sorted Insertion Sort will perform better. 

Insertion sort is often used with Quick sort: In Quick Sort after some level of recursion (When array is mostly sorted) Insertion sort is used.

For more: 
https://www.quora.com/In-laymans-terms-what-is-the-difference-between-a-bubble-sort-and-an-insert-sort

No comments:

Post a Comment