1. What is an in-place sorting algorithm?
a) It needs O(1) or O(logn) memory to create auxiliary locations
b) The input is already sorted and in-place
c) It requires additional storage
d) It requires additional space
Explanation: Auxiliary memory is required for storing the data temporarily.
2. In the following scenarios, when will you use selection sort?
a) The input is already sorted
b) A large file has to be sorted
c) Large values need to be sorted with small keys
d) Small values need to be sorted with large keys
Explanation: Selection is based on keys, hence a file with large values and small keys can be efficiently sorted with selection sort.
3. What is the worst case complexity of selection sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Explanation: Selection sort creates a sub-list, LHS of the ‘min’ element is already sorted and RHS is yet to be sorted. Starting with the first element the ‘min’ element moves towards the final element.
4. What is the advantage of selection sort over other sorting techniques?
a) It requires no additional storage space
b) It is scalable
c) It works best for inputs which are already sorted
d) It is faster than any other sorting technique
Explanation: Since selection sort is an in-place sorting algorithm, it does not require additional storage.
5. What is the average case complexity of selection sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Explanation: In the average case, even if the input is partially sorted, selection sort behaves as if the entire array is not sorted. Selection sort is insensitive to input.
6. What is the disadvantage of selection sort?
a) It requires auxiliary memory
b) It is not scalable
c) It can be used for small keys
d) It takes linear time to sort the elements
Explanation: As the input size increases, the performance of selection sort decreases.
7. The given array is arr = {3,4,5,2,1}. The number of iterations in bubble sort and selection sort respectively are __________
a) 5 and 4
b) 4 and 5
c) 2 and 4
d) 2 and 5
Explanation: Since the input array is not sorted, bubble sort takes 5 iterations and selection sort takes 4(n-1) iterations.
8. The given array is arr = {1,2,3,4,5}. (bubble sort is implemented with a flag variable)The number of iterations in selection sort and bubble sort respectively are __________
a) 5 and 4
b) 1 and 4
c) 0 and 4
d) 4 and 1
Explanation: Selection sort is insensitive to input, hence 4(n-1) iterations. Whereas bubble sort iterates only once to set the flag to 0 as the input is already sorted.
9. What is the best case complexity of selection sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Explanation: The best, average and worst case complexities of selection sort is O(n2).
(n-1) + (n-2) + (n-3) + …. + 1 = (n(n-1))/2 ~ (n2)/2.
10. What is an external sorting algorithm?
a) Algorithm that uses tape or disk during the sort
b) Algorithm that uses main memory during the sort
c) Algorithm that involves swapping
d) Algorithm that are considered ‘in place’
Explanation: As the name suggests, external sorting algorithm uses external memory like tape or disk.
Design and Analysis of Algorithms
The Ballet of Selection Sort: Sorting Made Simple
Imagine you're at a grand ball, and everyone is standing in a line. Now, Selection Sort is like the ultimate dance choreographer, arranging the dancers from the least twinkle in their shoes to the most dazzling ones. Elegant, isn't it?
In algorithmic lingo, Selection Sort works by repeatedly selecting the minimum element from the unsorted part of the array and placing it at the beginning. It's like finding the smallest star in the night sky and making it the North Star – guiding the others!
Why Choose Selection Sort in Your Algorithmic Wardrobe?
Selection Sort may not be the trendiest algorithm, but it has its perks. It's uncomplicated, like your favorite pair of jeans – easy to understand and implement. Perfect for those algorithmic situations when you want a quick and straightforward solution.
Despite its simplicity, Selection Sort's time complexity is a humble O(n^2). While it may not break the speed records, it gets the job done efficiently for small datasets. Sometimes, simplicity is the ultimate sophistication, right?
In conclusion, my fellow algorithm adventurers, Selection Sort might not wear the fanciest algorithmic cape, but it sure knows how to waltz through your data with grace. So, the next time you're in algorithmic wonderland, give Selection Sort a chance to dance its way into your heart!