1.5 hour
Introduction video for Selection Sort
This experiment requires you to have basic knowledge about :
And above all, a curiosity to learn and explore!
In this experiment, we will learn about:
Module | Weightage | Expectation |
---|---|---|
Pre-test | 15% | Solve All Questions |
Selection Sort | 35% | Understand the Selection sort algorithm |
Analysis | 25% | Understand the time and space complexity |
Post-test | 25% | Solve all Questions |
10 minutes
Given a list of random numbers, sorting means ordering the numbers in either ascending or descending order. By default, we sort numbers in an ascending order.
Picture shows sorted and unsorted array.
Q1. Which of these best describes an array?
(A) A data structure that shows a hierarchical behavior
(B) Container of objects of similar types
(C) Container of objects of mixed types
(D) All of the mentioned
An array is a data structure, which can store a fixed-size collection of elements of the same data type.
Q2. What is the complexity of insertion at any point in an array?
(A) O(N)
(B) O(N^2)
(C) O(NLogN)
(D) None of these
Taking a general example,inserting into the middle of an array, you have to shift all the elements after that element, so the complexity for insertion in that case is O(n). Worst case would be when you have to insert at the starting of the array,you will need to move n elements
Q3. What does it mean when we say that an algorithm X is asymptotically more efficient than Y?
(A) X will always be a better choice for small inputs
(B) X will always be a better choice for large inputs
(C) Y will always be a better choice for small inputs
(D) X will always be a better choice for all inputs
Performance could be similar for small inputs, but definitely better for larger inputs
Q4. int a = 0, b = 0;
for (i = 0; i < N; i++) {
a = a + rand();
}
for (j = 0; j < M; j++) {
b = b + rand();
}
What is the time and space complexity for the above code?
(A) O(N * M) time, O(1) space
(B) O(N + M) time, O(N + M) space
(C) O(N + M) time, O(1) space
(D) O(N * M) time, O(N + M) space
The first loop runs for O(n) time, second loop runs for O(m). Constant extra space is used for 2 variables a and b, hence O(1) space.
15 minutes
Video for Selection Sort
In this module, we will learn about:
In Selection Sort, we take the simplest, most intuitive approach to sort an array. Choose the smallest number, place it in the first position. Then choose the next smallest number out of the remaining elements, and place it in the second position and so on till the end!
Image shows the basic intuition
Now that we have understood
the basic intuition behind
this algorithm, let's see
how we can perform it in a
systematic way :
We will perform N-1
iterations on the array (N
is the number of elements in
the array). In iteration i
(1≤i≤N-1):
In the (N-1)^{th} iteration, we will place the (N-1)^{th} smallest element, which is the 2nd largest element in the array, at the second last position. This will leave us with one element which would already be at its correct place.This completes our sorting!
Given an array of N elements,
run N-1 iterations.
In iteration i (1≤i≤N-1):
Interactive artefact where user can understand how Selection Sort works
Interactive artefact where user can practice the Selection Sort algorithm
Interactive artefact where user can generate questions and solve them, and then check the answers. Ideas : find Kth largest/smallest element using Selection Sort etc
Q1. Maximum number of comparisons required for one iteration on an array of size 5?
(A) 4
(B) 5
(C) 3
(D) 6
Maximum number of
comparisons will occur
in the first iteration
To find the minimum
in the whole list,
you do a comparison
with each element,
hence 5
Q2. Which element reaches its correct position at the end of the 1st iteration?
(A) Smallest element
(B) Largest element
(C) Middle element
(D) No element
Selection Sort chooses the minimum(in the list) and replaces it with the first number in its 1st iteration
Q3. When do we swap two elements in Selection Sort?
(A) At the start of an iteration
(B) At the end of an iterations
(C) As soon as we find a minimum to update
(D) Middle of the iteration
In one iteration, Selection Sort finds the minimum in the current list and then swaps it with the first element of that window.
10 minutes
Time complexity of Selection Sort is explained
In this module, we will be learning about :
Lets assume that we are sorting N elements of a given array using Selection Sort.
Interactive artefact where user can see how time complexity is O(n2)
While swapping two elements, we need some extra space to store temporary values. Other than that, the sorting can be done in-place. Hence space complexity is O(1) or constant space.
A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input unsorted array. For example, look at the picture below. The unsorted array has two elements with value 23. Note the order of both these elements in the stable and unstable sorted arrays.
Image shows scenarios to swap and not swap
Yes, Selection Sort is a stable sorting algorithm. When looking for the smallest element, we choose the element with lower index incase there are two or more equal elements that are the smallest elements in the array. This makes sure that we preserve the relative ordering between equal elements.
Look at the picture below and keep and eye out for the ordering of 23 and 23*. Note how the original order of these elements is retained throughout the sorting process. The relative positioning of 23 and 23* does not change in the sorted output.
Image shows stabilty of Selection Sort
comparison
Algorithm | Time | Features | |||
---|---|---|---|---|---|
Sort | Average | Best | Worst | Space | Stability |
Selection Sort | O(n^{2}) | O(n^{2}) | O(n^{2}) | Constant | Stable |
Modified Selection Sort | O(n^{2}) | O(n) | O(n^{2}) | Constant | Stable |
Selection Sort | O(n^{2}) | O(n^{2}) | O(n^{2}) | Constant | Stable |
Insertion Sort | O(n^{2}) | O(n) | O(n^{2}) | Constant | Stable |
Heap Sort | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | Constant | Unstable |
Merge Sort | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | Depends | Stable |
Quick Sort | O(n*log(n)) | O(n*log(n)) | O(n^{2}) | Constant | Stable |
Q1. What is the time complexity of Selection Sort?
(A) Average case O(n^{2}))
(B) Best case O(n^{2})
(C) Worst case O(n^{2})
(D) All the above
Selection Sort in its best implementation performs N + (N-1) + (N-2) .... 1 operations which is O(n^{2})
Q2. Is Selection Sort stable?
(A) Yes
(B) No
(C) Depends
(D) Can't say
Selection Sort is stable as explained earlier.
Q3. Compare best case time complexities of Selection Sort and Bubble Sort
(A) Equal
(B) Bubble sort is better
(C) Selection Sort is better
(D) Unequal
Bubble sort: Best case O(N) Selection Sort: Best case O(N^{2})
10 minutes
Post Test includes questions on entire experiment concepts. Read the questions in the quiz section and select the correct option from the ones provided. Please note that some questions may have more than one correct response.
Q1. Which among the following is an advantage of Selection Sort over other sorting algorithms?
(A) Faster than others
(B) It does not require additional storage spaces
(C) Very efficient
(D) Suitable for long lists
Selection Sort is an in-place sort, so it doesn't require any additional storage space.
Q2. What is the average and best case time complexity of Selection Sort?
(A) O(n^{2}), O(n^{2})
(B) O(n^{2}), O(n)
(C) O(n^{2}), O(nlogn)
(D) None of these
Selection Sort in its best implementation does n + (n-1) + (n-2) ... 1 steps which is O(n^{2})
Q3. Given array = {11,12,13,10,9}. Number of iterations required by Bubble Sort and Selection Sort are?
(A) 5,4
(B) 4,4
(C) 4,6
(D) 5,5
Bubble Sort: The array will be sorted at the end of the 4th iteration but one more iteration will be run and on finding no swaps the sort will terminate. So, 4+1 = 5
Selection Sort always takes "N-1" iterations
Q4. What are the correct intermediate steps when you perform Selection Sort on [2, 7, -3, 5]?
(A) [-3, 2, 7, 5] -> [-3, 2, 5, 7]
(B) [-3, 7, 2, 5] -> [-3, 2, 7, 5] -> [-3, 2, 5, 7]
(C) [-3, 7, 5, 2] -> [-3, 2, 5, 7]
(D) [-3, 7, 2, 5] -> [-3, 5, 2, 7] -> [-3, 2, 5, 7]
Find the minimum in each window and swap with the first element in that window
Q5. Predict the structure of Selection Sort?
(A) One Loop
(B) Two loops
(C) Two lops in a loop
(D) Loop inside a loop
Selection Sort
involves finding the
minimum out of the
given list O(N) times
This requires nested
loops
You can explore more about Selection Sort experiment through following resources: