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 moves it to the beginning, sorting the list step by step.

beginner

How many passes does Selection Sort make over the array?

Selection Sort makes n-1 passes over 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 worst case?

The worst-case time complexity of Selection Sort is O(n²), because it uses two nested loops to find the minimum element for each position.

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.

beginner

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

Find the smallest element (10) and swap it with the first element (29). The array becomes [10, 29, 14, 37, 13].

What does Selection Sort do in each pass?

A Finds the smallest element and swaps it to the front

B Swaps adjacent elements if they are in wrong order

C Divides the array into halves and sorts each

D Builds a heap and extracts the max element

Selection Sort finds the smallest element in the unsorted part and swaps it to the front in each pass.

What is the space complexity of Selection Sort?

A O(n)

B O(1)

C O(log n)

D O(n²)

Selection Sort sorts the array in place using only a few extra variables, so space complexity is O(1).

How many comparisons does Selection Sort make in total for an array of size n?

A n² log n

B n log n

C n

D n(n-1)/2

Selection Sort makes about n(n-1)/2 comparisons because it compares each element with all others in the unsorted part.

Which of these is true about Selection Sort?

A It is unstable by default

B It is stable by default

C It requires extra memory for sorting

D It is the fastest sorting algorithm

Selection Sort is unstable because swapping can change the relative order of equal elements.

After the first pass of Selection Sort on [5, 3, 8, 4, 2], what is the array?

A [2, 3, 4, 5, 8]

B [3, 5, 8, 4, 2]

C [2, 3, 8, 4, 5]

D [5, 3, 8, 4, 2]

The smallest element 2 is swapped with the first element 5, resulting in [2, 3, 8, 4, 5].

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

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

Describe the time and space complexity of Selection Sort and why it is considered inefficient for large data.

Consider how many comparisons happen as the list grows.

Practice

1. What is the main idea behind the Selection Sort Algorithm?

easy

A. Divide the list and merge sorted parts

B. Swap adjacent elements if they are in wrong order

C. Repeatedly find the smallest element and move it to the front

D. Insert elements into their correct position one by one

Solution

1. Step 1: Understand selection sort process

   Selection sort finds the smallest element in the unsorted part and swaps it with the first unsorted element.

2. Step 2: Compare with other sorting methods

   Unlike bubble sort (swapping adjacent) or merge sort (divide and conquer), selection sort selects the minimum each time.

3. Final Answer:

   Repeatedly find the smallest element and move it to the front -> Option C

4. Quick Check:

   Selection sort = find minimum and swap [OK]

Hint: Selection sort picks smallest and swaps front [OK]

Common Mistakes:

• Confusing selection sort with bubble sort
• Thinking it sorts by inserting elements
• Believing it divides and merges lists

2. Which of the following is the correct syntax to swap two elements arr[i] and arr[min_idx] in C during selection sort?

easy

A. arr[i], arr[min_idx] = arr[min_idx], arr[i];

B. temp = arr[i]; arr[i] = arr[min_idx]; arr[min_idx] = temp;

C. swap(arr[i], arr[min_idx]);

D. arr[i] = arr[min_idx]; arr[min_idx] = arr[i];

Solution

1. Step 1: Understand swapping in C

   C does not have built-in swap; we use a temporary variable to hold one value during swap.

2. Step 2: Check each option

   temp = arr[i]; arr[i] = arr[min_idx]; arr[min_idx] = temp; uses a temp variable correctly. arr[i] = arr[min_idx]; arr[min_idx] = arr[i]; overwrites arr[i] before saving. swap(arr[i], arr[min_idx]); is invalid syntax in C. arr[i], arr[min_idx] = arr[min_idx], arr[i]; is Python syntax, not C.

3. Final Answer:

   temp = arr[i]; arr[i] = arr[min_idx]; arr[min_idx] = temp; -> Option B

4. Quick Check:

   Use temp variable to swap in C [OK]

Hint: Use temp variable to swap in C [OK]

Common Mistakes:

• Trying to swap without temp variable
• Using Python or other language syntax
• Overwriting values before saving

3. What will be the output array after the first pass of selection sort on arr = {29, 10, 14, 37, 13}?

medium

A. {10, 29, 14, 37, 13}

B. {29, 10, 14, 37, 13}

C. {13, 10, 14, 37, 29}

D. {10, 14, 29, 37, 13}

Solution

1. Step 1: Find minimum in entire array

   Minimum element is 10 at index 1.

2. Step 2: Swap minimum with first element

   Swap 29 (index 0) with 10 (index 1). Array becomes {10, 29, 14, 37, 13}.

3. Final Answer:

   {10, 29, 14, 37, 13} -> Option A

4. Quick Check:

   First pass swaps smallest to front [OK]

Hint: First pass swaps smallest element to front [OK]

Common Mistakes:

• Not swapping after finding minimum
• Swapping with wrong index
• Confusing first pass with full sort

4. Identify the error in this selection sort snippet and choose the fix:

for (int i = 0; i < n; i++) {
  int min_idx = i;
  for (int j = i + 1; j < n; j++) {
    if (arr[j] < arr[min_idx])
      min_idx = j;
  }
  arr[i] = arr[min_idx];
  arr[min_idx] = arr[i];
}

medium

A. Swap lines overwrite values; use a temp variable to swap

B. Change inner loop to start from j = 0

C. Remove inner loop; selection sort doesn't need it

D. Use arr[min_idx] = arr[j] instead of arr[min_idx] = arr[i]

Solution

1. Step 1: Analyze swap lines

   Lines arr[i] = arr[min_idx]; arr[min_idx] = arr[i]; overwrite arr[min_idx] with arr[i] after first assignment, losing original value.

2. Step 2: Correct swap method

   Use a temporary variable to hold arr[i], then assign arr[i] = arr[min_idx], then arr[min_idx] = temp to swap correctly.

3. Final Answer:

   Swap lines overwrite values; use a temp variable to swap -> Option A

4. Quick Check:

   Swap needs temp variable to avoid overwrite [OK]

Hint: Use temp variable to swap, not direct assignments [OK]

Common Mistakes:

• Swapping without temp variable
• Changing loop start incorrectly
• Removing necessary inner loop

5. Given the array arr = {64, 25, 12, 22, 11}, after fully sorting it using selection sort, what is the final sorted array?

hard

A. {64, 25, 12, 22, 11}

B. {11, 22, 12, 25, 64}

C. {25, 11, 12, 22, 64}

D. {11, 12, 22, 25, 64}

Solution

1. Step 1: Perform selection sort passes

   Pass 1: min=11, swap with 64 -> {11,25,12,22,64}
   Pass 2: min=12, swap with 25 -> {11,12,25,22,64}
   Pass 3: min=22, swap with 25 -> {11,12,22,25,64}
   Pass 4: min=25, no swap needed -> {11,12,22,25,64}

2. Step 2: Confirm final sorted array

   After all passes, array is sorted ascending: {11, 12, 22, 25, 64}.

3. Final Answer:

   {11, 12, 22, 25, 64} -> Option D

4. Quick Check:

   Selection sort fully sorts ascending [OK]

Hint: Selection sort sorts ascending by swapping minimum each pass [OK]

Common Mistakes:

• Stopping after first pass
• Not swapping correctly
• Mixing up element positions