Selection Sort Algorithm in DSA C++ - 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.

beginner

How many passes does Selection Sort make through the array?

Selection Sort makes n-1 passes through an array of n elements, because after placing n-1 elements, the last one is already sorted.

intermediate

What is the time complexity of Selection Sort in the best, average, and worst cases?

Selection Sort has a time complexity of O(n²) in all cases because it always compares each element with the rest, regardless of initial order.

beginner

Does Selection Sort require extra memory for sorting?

No, Selection Sort is an in-place sorting algorithm, meaning it sorts the array without needing extra memory beyond a few variables.

intermediate

Why is Selection Sort not efficient for large datasets?

Because Selection Sort always does n² comparisons, it becomes slow for large datasets compared to faster algorithms like Quick Sort or Merge Sort.

What does Selection Sort do in each pass?

A Divides the array into halves and sorts each half

B Swaps adjacent elements if they are in the wrong order

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

D Uses a pivot to partition the array

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

How many swaps does Selection Sort perform in the worst case?

A n-1 swaps

B n² swaps

C 0 swaps

D n swaps

Selection Sort performs exactly n-1 swaps because it swaps once per pass after finding the minimum.

Which of these is true about Selection Sort's space complexity?

A It sorts in-place using constant extra space

B It requires extra space proportional to n

C It needs a temporary array to store sorted elements

D It uses recursion and stack space

Selection Sort sorts the array in-place and uses only a few variables, so it has constant extra space.

What is the best case time complexity of Selection Sort?

A O(n log n)

B O(n)

C O(log n)

D O(n²)

Selection Sort always does n² comparisons, so its best case time complexity is O(n²).

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

A Bubble Sort

B Quick Sort

C Selection Sort

D Insertion Sort

Quick Sort is generally faster than Selection Sort for large arrays due to better average time complexity.

Explain step-by-step how Selection Sort sorts the array [4, 2, 7, 1].

Think about how the smallest number moves to the front each time.

Describe why Selection Sort is considered an in-place sorting algorithm and what that means for memory use.

Focus on how the array is changed directly.