WorksheetsSorting algorithms I
Total questions: 21
Worksheet time: 12mins
What is meant by an in-place sorting algorithm?
The input is already sorted and in-place
It requires additional storage
It needs O(1) memory to create auxiliary locations
It requires additional space
Which of the following is an in-place sorting algorithm?
Selection sort
Insertion sort
Bubble sort
All
Which of the following sorting algorithms is best used when the array is nearly sorted to begin with?
Selection sort
Insertion sort
Bubble sort
None of the above
What is the worst case complexity of selection sort?
O(nlogn)
O(logn)
O(n)
O(𝐧𝟐)
Select the appropriate code that performs selection sort.
What is the average case complexity of selection sort?
O(nlogn)
O(logn)
O(n)
O(𝐧𝟐)
What is the disadvantage of selection sort?
What is the disadvantage of selection sort?
It is not scalable
It can be used for small keys
It takes linear time to sort the elements
How many passes does an insertion sorting algorithm consist of?
N
N-1
N+1
N2
What is the average case complexity of an insertion sort?
O(nlogn)
O(logn)
O(n)
O(𝐧𝟐)
Any algorithm that sorts by exchanging adjacent elements require O(N2) on average.
True
False
What is the running time of an insertion sort algorithm if the input is presorted?
O(n2)
O(nlogn)
O(n)
O(logn)
What will be the number of passes to sort the elements using insertion sort?
14, 12,16, 6, 3, 10
6
5
7
1
For the following question, how will the array elements look like after second pass?
34, 8, 64, 51, 32, 21
8, 21, 32, 34, 51, 64
8, 32, 34, 51, 64, 21
8, 34, 51, 64, 32, 21
8, 34, 64, 51, 32, 21
For the best case input, the running time of an insertion sort algorithm is?
Linear
Binary
Quadratic
Depends on the input
Which of the following examples represent the worst case input for an insertion sort?
Array in sorted order
Array sorted in reverse order
Normal unsorted array
Large array
What is the worst case complexity of bubble sort?
O(nlogn)
O(logn)
O(n)
O(𝐧𝟐)
Select the appropriate code that performs bubble sort.
What is the average case complexity of bubble sort?
O(nlogn)
O(logn)
O(n)
O(𝐧𝟐)
The given array is arr = {1, 2, 4, 3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array?
4
2
1
0
The given array is arr = {3,4,5,2,1}. The number of iterations in bubble sort and selection sort respectively are:
5 and 4
4 and 5
2 and 4
2 and 5
What is the advantage of selection sort, insertion sort and bubble sort over other sorting algorithms?
They are scalable
They do not require additional storage space
They work best for inputs which are already sorted
They are faster than any other sorting techniques
