Topic: Sorting | BPSC Paper-2 Computer Science Notes

 

Summary notes on topic "Sorting"

-------------------++++++++-----------

• The process of placing or rearranging a collection of elements into a particular order is known as sorting.

• Bubble sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements in case they are unordered in n-1 passes.

• In Selection Sort, the smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. The process continues for the next element in the unsorted array till the list is sorted.

• Insertion Sort places the element of a list at its suitable place in each pass. It is similar to the placing of cards at its right position while playing cards.

• Complexity analysis is performed to explain how an algorithm will perform when the input grows larger.

MCQ Qu-Ans on Topic Sorting

Qu: Which of the following is not a stable sorting algorithm?

Insertion sort
Selection sort
Bubble sort
Merge sort
All Above/None Above

Qu: Which of the following is a stable sorting algorithm?

Merge sort
Typical in-place quick sort
Heap sort
Selection sort
All Above/None Above

Qu: Which of the following is not an in-place sorting algorithm?

Selection sort
Heap sort
Quick sort
Merge sort
All Above/None Above

Qu: Running merge sort on an array of size n which is already sorted is

O(n)
O(nlogn)
O(n2)
None
All Above/None Above

Qu: The time complexity of a quick sort algorithm which makes use of median, found by an O(n) algorithm, as pivot element is

O(n2)
O(nlogn)
O(nloglogn)
O(n)
All Above/None Above

$ads={1}

Qu: Which of the following is not a noncomparison sort?

Counting sort
Bucket sort
Radix sort
Shell sort
All Above/None Above

Qu: The time complexity of heap sort in worst case is

O(logn)
O(n)
O(nlogn)
O(n2)
All Above/None Above

Qu: If the given input array is sorted or nearly sorted, which of the following algorithm gives the best performance?

Insertion sort
Selection sort
Quick sort
Merge sort
All Above/None Above

Qu: Which of the following algorithm pays the least attention to the ordering of the elements in the input list?

Insertion sort
Selection sort
Quick sort
None
All Above/None Above

Qu: Consider the situation in which assignment operation is very costly. Which of the following sorting algorithm should be performed so that the number of assignment operations is minimized in general?

Insertion sort
Selection sort
Heap sort
None
All Above/None Above

Qu: Time complexity of bubble sort in best case is

θ (n)
θ (nlogn)
θ (n2)
θ (n(logn) 2)
All Above/None Above

Qu: Given a number of elements in the range [0….n3]. which of the following sorting algorithms can sort them in O(n) time?

Counting sort
Bucket sort
Radix sort
Quick sort
All Above/None Above

Qu: Which of the following algorithms has lowest worst case time complexity?

Insertion sort
Selection sort
Quick sort
Heap sort
All Above/None Above

Qu: Which of the following sorting algorithms is/are stable

Counting sort
Bucket sort
Radix sort
All of the above
All Above/None Above

Qu: Counting sort performs …………. Numbers of comparisons between input elements.

0
n
nlogn
n2
All Above/None Above

Qu: The running time of radix sort on an array of n integers in the range [0……..n5 -1] when using base 10 representation is

θ (n)
θ (nlogn)
θ (n2)
none
All Above/None Above

Qu: The running time of radix sort on an array of n integers in the range [0……..n5 -1] when using base n representation is

θ (n)
θ (nlogn)
θ (n2)
None
All Above/None Above

$ads={2}

Qu: Which of the following sorting algorithm is in-place

Counting sort
Radix sort
Bucket sort
None
All Above/None Above

Qu: The radix sort does not work correctly if each individual digit is sorted using

Insertion sort
Counting sort
Selection sort
Bubble sort
All Above/None Above

Qu: Which of the following sorting algorithm has the running time that is least dependant on the initial ordering of the input?

Insertion sort
Quick sort
Merge sort
Selection sort
All Above/None Above

Qu: Time complexity to sort elements of binary search tree is

O(n)
O(nlogn)
O(n2)
O(n2logn)
All Above/None Above

Qu: The lower bound on the number of comparisons performed by comparison-based sorting algorithm is

Ω (1)
Ω (n)
Ω (nlogn)
Ω (n2)
All Above/None Above

Qu: Which of the following algorithm(s) can be used to sort n integers in range [1…..n3] in O(n) time?

Heap sort
Quick sort
Merge sort
Radix sort
All Above/None Above

Qu: Which of the following algorithm design technique is used in the quick sort algorithm?

Dynamic programming
Backtracking
Divide-and-conquer
Greedy method
All Above/None Above

Qu: Merge sort uses

Divide-and-conquer
Backtracking
Heuristic approach
Greedy approach
All Above/None Above

Qu: For merging two sorted lists of size m and n into sorted list of size m+n, we require comparisons of

O(m)
O(n)
O(m+n)
O(logm + logn)
All Above/None Above

Qu: A sorting technique is called stable if it

Takes O(nlogn) times
Maintains the relative order of occurrence of non-distinct elements
Uses divide-and-conquer paradigm
Takes O(n) space
All Above/None Above

Qu: In a heap with n elements with the smallest element at the root, the seventh smallest element can be found in time

θ (nlogn)
θ (n)
θ (logn)
θ (1)
All Above/None Above

Qu: What would be the worst case time complexity of the insertion sort algorithm, if the inputs are restricted to permutation of 1…..n with at most n inversion?

θ (n2)
θ (nlogn)
θ (n1.5)
θ (n)
All Above/None Above

Qu: In a binary max heap containing n numbers, the smallest element can be found in time

θ (n)
θ (logn)
θ (loglogn)
θ (1)
All Above/None Above