4,813 views

You have to sort a list $L$, consisting of a sorted list followed by a few ‘random’ elements. Which of the following sorting method would be most suitable for such a task ?

1. Bubble sort
2. Selection sort
3. Quick sort
4. Insertion sort

From given description, the list is "almost sorted".

• A.Bubble sort: sorted array as input is best case for this sort. Best case Complexity is O ( n 2 )
• B. Selection sort: sorted array as input is best case for this sort. Best case Complexity is O ( n 2 )
• C. Quick sort: sorted array as input is worst case for this sort. Worst case Complexity is O ( n 2 )
• D. Insertion sort: sorted array as input is best case for this sort. Best case Complexity is O ( n )

by

since list is almost sorted followed  only few random elements  these elements will easily and quickly take their position(or inserted in the list) one after another by insertion sort as there is least no of shifting is needed

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksortheapsort, or merge sort. However, insertion sort provides several advantages:

• Simple implementation: Bentley shows a three-line C version, and a five-line optimized version:116
• Efficient for (quite) small data sets, much like other quadratic sorting algorithms
• More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort
• Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(nk) when each element in the input is no more than k places away from its sorted position
• Stable; i.e., does not change the relative order of elements with equal keys
• In-place; i.e., only requires a constant amount O(1) of additional memory space
• Online; i.e., can sort a list as it receives it

Nobody explained it correctly every1 just gave roundabout answer (theory etc ) sh!va gave the fact but why the fact is that only insertion sort does not only in place but also when it's sorting it's not concerned with what is at right of the element being sorted only it sees left which by god's grace on the algo will be perfectly sorted(see the match to the question). i.e. it's local in it's approach. That also full portion of the loop not like in inner loop & again going out on out ward loop or something means half/portion of algorithm saved.

1
5,630 views