Sorting techniques Quiz

Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this: 2 5 1 7 9 12 11 10. Which statement is correct?

Suppose we are sorting an array of eight integers using heapsort, and we have just finished some heapify (either maxheapify or minheapify) operations. The array now looks like this: 16 14 15 10 12 27 28. How many heapify operations have been performed on root of heap?

Which of the following sorting algorithms is the fastest for sorting small arrays?

• Quick sort

• Shell sort

• Insertion sort

• Heap sort

What is the advantage of selection sort over other sorting techniques?

• It is faster than any other sorting technique

• It is scalable

• It works best for inputs which are already sorted

• It requires no additional storage space

Shell sort algorithm is an example of?

• Bottom-up sorting

• In-place sorting

• Internal sorting

• External sorting

Answer explanation

Shell sort algorithm is an example of internal sorting as it rearranges elements within the array being sorted.

Which of the following sorting algorithm does not use recursion?

• bottom up merge sort

• merge sort

• heap sort

• quick sort

Answer explanation

Heap sort is the sorting algorithm that does not use recursion. It is based on the heap data structure and does not require recursive calls.

Quick sort uses which of the following method to implement sorting?

• partitioning

• selection

• exchanging

• merging

Answer explanation

Quick sort uses partitioning method to implement sorting by dividing the array into smaller sub-arrays based on a pivot element.

What is the best time complexity of bubble sort(optimised)?

• N^2

• NlogN

• N

• N(logN)^2

Answer explanation

The best time complexity of bubble sort(optimised) is N, as it reduces the number of comparisons and swaps by stopping the algorithm if the array becomes sorted before completing all passes.

Which of the following pair of sorting algorithms are stable?

• gnome sort and merge sort

• heap sort and merge sort

• gnome sort and quick sort

• merge sort and selection sort

Answer explanation

Heap sort and merge sort are stable sorting algorithms because they maintain the relative order of equal elements, unlike other options provided.

What is the average case running time of an insertion sort algorithm?

• O(N)

• O(N log N)

• O(log N)

• O(N2)

Answer explanation

The correct answer is O(N^2) because the average case running time of an insertion sort algorithm is quadratic, which is represented by O(N^2).