The following pseudocode, which has a worst-case timing of $$O(n^2)$$, is what type of classical sort algorithm? 

A.  Bubble sort
B.  Insertion sort
C.  Merge sort
D.  Quick sort

1 Answer

DEMETRIOS LAMBROPOULOS

Updated on December 30th, 2020

We can remove Merge sort from possible options because the worst-case time complexity is O(n log n)

Quick-sort is a divide and conquer sorting algorithm with a worst-case time complexity of O(n2), however it works by choosing a pivot and partitioning the remaining elements into two sub-arrays which from the algorithm above does not and therefore can be removed from possible choices. 

Iteration sort has the following algorithm:

1 ) Iterate through the n elements of the array

2 ) Compare the element at the current index to the previous index

3 ) If the current element is less than the element at the previous index, compare the element to previous elements. All elements greater than the element of interest will be moved up by 1 index to make room to swap the element.

Observing this algorithm, we see that this is not what happens above and therefore can say that the answer is A. Bubble Sort.

Copyright © 2024 Savvy Engineer