4 votes 4 votes 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 ? Bubble sort Selection sort Quick sort Insertion sort Algorithms ugcnetcse-dec2014-paper2 algorithms data-structures sorting + – makhdoom ghaya asked Jul 21, 2016 • recategorized Jul 6, 2022 by Lakshman Bhaiya makhdoom ghaya 6.4k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes 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 ) Answer Insertion sort sh!va answered Jul 21, 2016 • edited Jul 22, 2016 by sh!va sh!va comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes 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 quicksort, heapsort, or merge sort. However, insertion sort provides several advantages: Simple implementation: Bentley shows a three-line C version, and a five-line optimized version[1]: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 Sanjay Sharma answered Jul 22, 2016 Sanjay Sharma comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes 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. Minakshi Boruah answered Nov 3, 2017 Minakshi Boruah comment Share Follow See all 0 reply Please log in or register to add a comment.