Introduction to Selection Sort

Estimated Time

1.5 hour

Introduction

Introduction video for Selection Sort

Prerequisites of the Experiment

This experiment requires you to have basic knowledge about :

And above all, a curiosity to learn and explore!

Overview of the Experiment

  • The aim of this experiment is to understand the Selection Sort algorithm, its Time and Space Complexity, and how it compares against other sorting algorithms.
  • The experiment features a series of modules with video lectures, interactive demonstrations, simulations, hands-on practice exercises and quizzes for self analysis.

Learning Objectives of the Experiment

In this experiment, we will learn about:

  • Given an unsorted array of numbers, generate a sorted array of numbers by applying Selection Sort
  • Demonstrate knowledge of time complexity of Selection Sort by counting the number of operations involved in each iteration.
  • Compare Selection Sort with other sorting algorithms and realise Selection Sort as a stable comparison sorting algorithm.

Experiment Modules & their Weightage

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

Pre-test of the Experiment

Estimated Time

10 minutes

Instructions for Pre-Test

  • Pretest includes questions on sorting, time complexity and space complexity.
  • If you want to revise these topics before taking the quiz, go through the Recap module first.
  • 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.

Quick look at Sorting, Time and Space Complexity

What is Sorting?

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.

Unsorted and Sorted arrays

Picture shows sorted and unsorted array.

Time and Space Complexity

  • Time complexity of an algorithm gives the measure of time taken by it to run as a function of the length of the input. Similarly, Space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input.

  • Recall that suppose our input is an array of N elements, and our algorithm iterates through the array once, time complexity will be O(N). If I run two embedded loops to traverse the array N times, time complexity will be O(N2).

A Quiz with Multiple Choice Questions

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.

Selection Sort Algorithm

Estimated Time

15 minutes

Selection Sort Concept

Video for Selection Sort

Learning Objectives of this Module

In this module, we will learn about:

  • Gain the intuition for Selection Sort
  • Learn about the Selection Sort algorithm
  • Practice the algorithm with step by step feedback
  • Perform exercises for obtaining clarity of concept
  • Test your conceptual understanding with a short quiz

Understanding the Selection Sort Algorithm

How can we sort an array?

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!

Intuition Behind the Algorithm

Image shows the basic intuition

Selection Sort Concept

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):

  • We will traverse the array from the ith index to the end and find the smallest number among these elements. Note that if there are two smallest elements of the same value, we choose the one with the lower index.
  • We will swap this smallest element with the ith element.
  • Hence at the end of the ith iteration, we have found the ith smallest number, and placed it at the ith position in the array!

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!

Selection Sort Algorithm

Selection Sort Algorithm picture

Consolidated Algorithm for Selection Sort

Given an array of N elements, run N-1 iterations.
In iteration i (1≤i≤N-1):

  • Find the smallest element with the least index, such that index≤i≤N-1.
  • Swap the smallest element found with element at index i.

Demonstration for Selection Sort

Demo : Selection Sort

Interactive artefact where user can understand how Selection Sort works

Step by Step Practice for Selection Sort

Practice : Selection Sort

Interactive artefact where user can practice the Selection Sort algorithm

Hands-on Exercise for Selection Sort

Exercise : Selection Sort

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

Revision Quiz for Selection Sort

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.

Analysis of Selection Sort

Estimated Time

10 minutes

Analysis of Selection Sort

Time complexity of Selection Sort is explained

Learning Objectives of this Module

In this module, we will be learning about :

  • Time and Space Complexity : We will learn about the running time of one iteration, and then extend it to N iterations to complete the sorting process.
  • Stable Sort : We will learn about stability of sorting algorithms. Then we will see how Selection Sort is a stable sort.
  • Comparison with other algorithms : We will compare Selection Sort with other sorting algorithms and see in which situations Selection Sort is the optimal/not optimal approach to take.

Time and Space Complexity of Selection Sort

Running Time of Selection Sort

Lets assume that we are sorting N elements of a given array using Selection Sort.

  • To complete one iteration, we traverse a part of the array (from index i to the end) exactly once (while keeping track of the smallest element encountered so far). Since the longest length we ever traverse in any given iteration is N (in the first iteration when i=1 -> from first to last element), time complexity of completing one iteration is O(N).
  • In Selection Sort, we run N iterations, each of which takes O(N) time. Hence overall time complexity becomes O(N*N).
  • Note that even if array is fully sorted initially, Selection Sort will take O(N2) time to complete, just as it will take for a reverse sorted or randomly sorted array.

Time complexity of Selection Sort

Interactive artefact where user can see how time complexity is O(n2)

Space Complexity of Selection Sort

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.

Stability of Selection Sort

What is a Stable Sort Algorithm?

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.

Stable and Unstable sort

Image shows scenarios to swap and not swap

Is Selection Sort Stable?

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.

Stability of Selection Sort

Image shows stabilty of Selection Sort

Comparison with other algorithms

Graph : Time Complexities of Sorting Algorithms

comparison

Comparison with other sorting algorithms

Algorithm Time Features
Sort Average Best Worst Space Stability
Selection Sort O(n2) O(n2) O(n2) Constant Stable
Modified Selection Sort O(n2) O(n) O(n2) Constant Stable
Selection Sort O(n2) O(n2) O(n2) Constant Stable
Insertion Sort O(n2) O(n) O(n2) 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(n2) Constant Stable

Revision Quiz for Analysis

Q1. What is the time complexity of Selection Sort?

(A) Average case O(n2))

(B) Best case O(n2)

(C) Worst case O(n2)

(D) All the above

Selection Sort in its best implementation performs N + (N-1) + (N-2) .... 1 operations which is O(n2)

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(N2)

Post Test of the Experiment

Estimated Time

10 minutes

Instructions for Quiz

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.

Post test quiz

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(n2), O(n2)

(B) O(n2), O(n)

(C) O(n2), O(nlogn)

(D) None of these

Selection Sort in its best implementation does n + (n-1) + (n-2) ... 1 steps which is O(n2)

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

Further Readings and References of the Experiment

Explore More About Selection Sort

You can explore more about Selection Sort experiment through following resources:


Useful Links : Quizzes :