Selection Sort Algorithm in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Selection Sort algorithm?

Selection Sort repeatedly finds the smallest element from the unsorted part and swaps it with the first unsorted element, growing the sorted part step by step.

intermediate

In Selection Sort, how many times do we swap elements in the worst case?

Selection Sort swaps elements exactly (n-1) times, where n is the number of elements, because it swaps once per pass.

beginner

Show the state of the array after the first pass of Selection Sort on [29, 10, 14, 37, 13].

After first pass, the smallest element 10 is swapped with 29: [10, 29, 14, 37, 13]

intermediate

What is the time complexity of Selection Sort and why?

Selection Sort has time complexity O(n²) because it uses two nested loops: one to select each element and one to find the minimum in the unsorted part.

intermediate

Why is Selection Sort not efficient for large datasets?

Because Selection Sort always does n² comparisons regardless of the initial order, making it slow for large lists compared to faster algorithms like Quick Sort or Merge Sort.

What does Selection Sort do in each pass?

A Finds the smallest element and swaps it with the first unsorted element

B Swaps adjacent elements if they are in wrong order

C Divides the list into halves and sorts each half

D Uses a pivot to partition the list

Selection Sort finds the smallest element in the unsorted part and swaps it with the first unsorted element in each pass.

How many passes does Selection Sort make for an array of size n?

A n

B log n

C n/2

D n-1

Selection Sort makes n-1 passes because after sorting n-1 elements, the last element is already in place.

What is the best case time complexity of Selection Sort?

A O(n²)

B O(n log n)

C O(n)

D O(log n)

Selection Sort always performs O(n²) comparisons regardless of input order.

Which of these is true about Selection Sort swaps?

A It swaps elements multiple times per pass

B It swaps only once per pass

C It never swaps elements

D It swaps only if the array is already sorted

Selection Sort swaps the smallest found element with the first unsorted element once per pass.

Which sorting algorithm is generally faster than Selection Sort for large datasets?

A Bubble Sort

B Insertion Sort

C Quick Sort

D Selection Sort

Quick Sort is generally faster with average time complexity O(n log n), better than Selection Sort's O(n²).

Explain how Selection Sort works step-by-step on a small array.

Think about how you would sort playing cards by picking the smallest card each time.

Describe the advantages and disadvantages of Selection Sort.

Consider when you might want to use it despite its slowness.