Selection Sort Algorithm in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Selection Sort on a small list

What is the output of the following selection sort code on the list [3, 1, 4, 2]?

DSA Python

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

lst = [3, 1, 4, 2]
selection_sort(lst)
print(lst)

A [4, 3, 2, 1]

B [1, 3, 2, 4]

C [3, 1, 2, 4]

D [1, 2, 3, 4]

💡 Hint

Selection sort finds the smallest element and swaps it to the front in each pass.

Selection sort repeatedly selects the smallest remaining element and places it at the current position, resulting in a sorted list.

🧠 Conceptual

intermediate

Number of swaps in Selection Sort

How many swaps does selection sort perform on a list of length n in the worst case?

A n swaps

B n * (n - 1) / 2 swaps

C n - 1 swaps

D 0 swaps

💡 Hint

Selection sort swaps only once per outer loop iteration.

Selection sort performs exactly one swap per iteration of the outer loop, so total swaps are n - 1.

🔧 Debug

advanced

Identify the error in this selection sort implementation

What error will this code produce when run on the list [5, 2, 9]?

DSA Python

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] > arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

lst = [5, 2, 9]
selection_sort(lst)
print(lst)

A The list is sorted in descending order: [9, 5, 2]

B No output, infinite loop

C IndexError due to invalid index access

D The list is sorted in ascending order: [2, 5, 9]

💡 Hint

Check the comparison operator in the inner loop.

The code uses '>' instead of '<', so it finds the maximum element each time, sorting the list in descending order.

❓ Predict Output

advanced

Selection Sort on a list with duplicates

What is the output after running selection sort on the list [4, 2, 4, 3, 2]?

DSA Python

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

lst = [4, 2, 4, 3, 2]
selection_sort(lst)
print(lst)

A [4, 4, 3, 2, 2]

B [2, 2, 3, 4, 4]

C [4, 2, 3, 2, 4]

D [2, 3, 2, 4, 4]

💡 Hint

Selection sort handles duplicates by placing equal elements in order found.

Selection sort sorts the list including duplicates, resulting in [2, 2, 3, 4, 4].

🧠 Conceptual

expert

Time complexity of selection sort in best and worst cases

What is the time complexity of selection sort in both best and worst cases?

A Best case: O(n^2), Worst case: O(n^2)

B Best case: O(n), Worst case: O(n^2)

C Best case: O(n log n), Worst case: O(n^2)

D Best case: O(n^2), Worst case: O(n log n)

💡 Hint

Selection sort always scans the entire unsorted part to find the minimum.

Selection sort always performs n*(n-1)/2 comparisons regardless of input order, so both best and worst cases are O(n^2).

Practice

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

easy

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

B. Divide the list into halves and merge sorted halves

C. Swap adjacent elements if they are in wrong order repeatedly

D. Use a pivot to partition the list into smaller parts

Solution

1. Step 1: Understand Selection Sort process

   Selection Sort works by finding the smallest element in the unsorted part and swapping it with the first unsorted element.

2. Step 2: Compare with other sorting methods

   Other options describe different algorithms: merge sort, bubble sort, and quicksort, not selection sort.

3. Final Answer:

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

4. Quick Check:

   Selection Sort = Find smallest and swap [OK]

Hint: Selection sort always picks the smallest next element [OK]

Common Mistakes:

• Confusing selection sort with bubble sort
• Thinking it divides the list like merge sort
• Mixing it up with quicksort's pivot method

2. Which of the following is the correct syntax to swap two elements a[i] and a[j] in Python during selection sort?

easy

A. temp = a[i]; a[i] = a[j]; a[j] = a[i]

B. a[i], a[j] = a[j], a[i]

C. swap(a[i], a[j])

D. a[i] = a[j]; a[j] = a[i]

Solution

1. Step 1: Identify Pythonic swap syntax

   Python allows swapping two variables in one line: a[i], a[j] = a[j], a[i].

2. Step 2: Check other options for correctness

   temp = a[i]; a[i] = a[j]; a[j] = a[i] causes data loss by overwriting without properly using temp; swap(a[i], a[j]) is invalid syntax; a[i] = a[j]; a[j] = a[i] causes both to have same value.

3. Final Answer:

   a[i], a[j] = a[j], a[i] -> Option B

4. Quick Check:

   Python swap = a[i], a[j] = a[j], a[i] [OK]

Hint: Use comma swap for clean Python element exchange [OK]

Common Mistakes:

• Using a function swap() which doesn't exist
• Assigning one element twice causing data loss
• Not using tuple unpacking for swap

3. What will be the output of the following code snippet?

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

arr = [3, 1, 4]
selection_sort(arr)
print(arr)

medium

A. [4, 3, 1]

B. [3, 1, 4]

C. [1, 4, 3]

D. [1, 3, 4]

Solution

1. Step 1: Trace first iteration of outer loop

   i=0, min_idx=0; inner loop finds smallest element from index 1 and 2. arr[1]=1 < arr[0]=3, so min_idx=1. Swap arr[0] and arr[1]: arr becomes [1, 3, 4].

2. Step 2: Trace second iteration

   i=1, min_idx=1; inner loop checks arr[2]=4 which is not less than arr[1]=3, so no swap. Array stays [1, 3, 4].

3. Final Answer:

   [1, 3, 4] -> Option D

4. Quick Check:

   Sorted array = [1, 3, 4] [OK]

Hint: Selection sort places smallest element at front each pass [OK]

Common Mistakes:

• Not swapping when min_idx changes
• Confusing indices in inner loop
• Assuming array is unchanged

4. Identify the error in the following selection sort code and choose the correct fix:

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] > arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

medium

A. Initialize min_idx to 0 instead of i

B. Swap should be done outside the outer loop

C. Change '>' to '<' in the if condition to find the smallest element

D. Use '==' instead of '>' in the if condition

Solution

1. Step 1: Analyze the if condition logic

   The code uses 'if arr[j] > arr[min_idx]' which finds the largest element, but selection sort needs the smallest.

2. Step 2: Correct the comparison operator

   Changing '>' to '<' will correctly find the smallest element to swap.

3. Final Answer:

   Change '>' to '<' in the if condition to find the smallest element -> Option C

4. Quick Check:

   Selection sort finds minimum, so use '<' [OK]

Hint: Selection sort finds minimum, so use '<' in comparison [OK]

Common Mistakes:

• Using '>' causes sorting in descending order
• Swapping outside loop breaks logic
• Wrong initialization of min_idx

5. Given a list arr = [5, 3, 8, 3, 9], how many swaps will the selection sort algorithm perform to sort this list in ascending order?

hard

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Trace selection sort swaps step-by-step

   Initial array: [5, 3, 8, 3, 9] - i=0: smallest is 3 at index 1, swap arr[0] and arr[1] -> [3, 5, 8, 3, 9] (1 swap) - i=1: smallest is 3 at index 3, swap arr[1] and arr[3] -> [3, 3, 8, 5, 9] (2 swaps) - i=2: smallest is 5 at index 3, swap arr[2] and arr[3] -> [3, 3, 5, 8, 9] (3 swaps) - i=3: smallest is 8 at index 3, no swap needed - i=4: last element, no swap needed

2. Step 2: Count total swaps

   Total swaps performed = 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Swaps counted = 3 [OK]

Hint: Count swaps only when min_idx changes and swap occurs [OK]

Common Mistakes:

• Counting swaps even when min_idx equals i
• Assuming one swap per iteration always
• Ignoring repeated elements affecting swaps