if list is almost sorted and largest element is wrongly placed

Question

A list of integers is almost sorted with only the largest number being out of place. If this information is not known to the algorithm, then which of the following algorithms can sort the list the fastest?

• A. Bubble sort
• B. Selection sort
• C. Insertion sort
• D. Shell sort

Answer 1

If integers are nearly or almost sorted , then insertion sort is the best. 

If we race all the four algorithms, then clearly insertion sort is the winner . Insertion sort provides a O(n²) worst case algorithm that adapts to O(n) time when the data is nearly or almost sorted. 

• Bubble sort is fast and comes second bcoz insertion sort has lower overhead and even if completely sorted , bubble sort again traverses all the elements to know that no swaps are needed which has high overhead.
•  
• Shell sort is fast and comes third because it is based on insertion sort.
• Selection sort is not good for this case and is very slow .
• Merge sort, heap sort, and quick sort do not even adapt to nearly sorted data.
• Time complexity ===> 

Insertion sort --> O(n) and it will take some 1 pass 

Bubble sort -->  O(n) and it will take some 2 pass or can be more (1 for actual swapping and last pass for again checking that this time no pass occurs which is overhead) .

Shell sort ---> O(nlogn)

Selection sort --> O(n​² )...

Comments

what is the meaning overhead in terms of sorting what exactly does  these terms imply lower overhead and high overhead ?

---

@shekhar sir,

Overhead word , I have used for extra efforts done by algorithms to correctly ensure the result (here sorted output).

Take bubble sort and insertion sort in this .

Bubble sort will traverse one more time to confirm sorted even if we know it is already sorted .

---

can you write how much time does each algo (only given option) will take to accomplish this task in your answer as you have written in case of insertion sort .don't write best and worst case complexity of them only write how much time will they take for this preticular task which is given in question

---

Insertion sort --> O(n) and it will take some 1 pass 

Bubble sort -->  O(n) and it will take some 2 pass or can be more (1 for actual swapping and last pass for again checking that this time no pass occurs which is overhead) .

Shell sort ---> O(nlogn)

Selection sort --> O(n​² )...

Answer 2

Its answer is C.Insertion Sort, Property of Insertion sort is it give best case time complexity of O(n) when all elements are almost sorted.