Sorting
Q1.
Consider the following array.\begin{array}{|l|l|l|l|l|l|l|l|} \hline 23&32&45&69&72&73&89&97 \\ \hline\end{array} Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?Q2.
Of the following sort algorithms, which has execution time that is least dependant on initial ordering of the input?Q3.
An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is _________.Q4.
Of the following sorting algorithms, which has a running time that is least dependent on the initial ordering of the input?Q5.
The number of swappings needed to sort the numbers 8 , 22, 7, 9, 31, 5, 13 in ascending order using bubble sort isQ6.
Which one of the following in-place sorting algorithms needs the minimum number of swaps?Q7.
Given two sorted list of size m and n respectively. The number of comparisons needed the worst case by the merge sort algorithm will be:Q9.
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE? I. Quicksort runs in \Theta (n^{2}) time II. Bubblesort runs in \Theta (n^{2}) time III. Merge sort runs in \Theta (n) time IV. Insertion sort runs in \Theta (n) timeQ10.
The worst case running times of Insertion sort, Mergesort and Quicksort, respectively, are: