COMPUTER SCIENCE AND ENGINEERING
DATA STRUCTURES
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
Only one pass
|
|
|
Two passes
|
|
|
Several passes-until the data is fully ordered
|
|
|
None of the above
|
Detailed explanation-1: -How many passes does an insertion sort algorithm consist of? Explanation: An insertion algorithm consists of N-1 passes when an array of N elements is given.
Detailed explanation-2: -Insertion sort requires n – 1 pass to sort an array of n elements. In each pass we insert the current element at the appropriate place so that the elements in the current range is in order. In each pass we have k comparisons, where k is the pass number.
Detailed explanation-3: -If the input array is already in sorted order, insertion sort compares O ( n ) O(n) O(n) elements and performs no swaps (in the Python code above, the inner loop is never triggered). Therefore, in the best case, insertion sort runs in O ( n ) O(n) O(n) time.
Detailed explanation-4: -The worst-case (and average-case) complexity of the insertion sort algorithm is O(n²). Meaning that, in the worst case, the time taken to sort a list is proportional to the square of the number of elements in the list. The best-case time complexity of insertion sort algorithm is O(n) time complexity.
Detailed explanation-5: -A bubble sort algorithm goes through a list of data a number of times, comparing two items that are side by side to see which is out of order. It will keep going through the list of data until all the data is sorted into order. Each time the algorithm goes through the list it is called a ‘pass’.