Selection Sort Algorithm in DSA Python - Execution Trace

Concept Flow - Selection Sort Algorithm

Start with unsorted array

↓

Set i = 0 (start index)

↓

Find min element from i to end

↓

Swap min element with element at i

↓

Increment i

↓

Is i < array length - 1?

No→Sorted array done

↩Back to find min element

Selection sort repeatedly finds the smallest element in the unsorted part and swaps it to the front, moving the boundary of sorted and unsorted parts forward.

Execution Sample

DSA Python

arr = [64, 25, 12, 22, 11]
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]

Sorts the array by selecting the minimum element from the unsorted part and swapping it with the first unsorted element.

Execution Table

Step	Operation	Current i	Current j	min_idx	Array State	Swap Occurred
1	Initialize i=0	0	-	0	[64, 25, 12, 22, 11]	No
2	Compare arr[j]=25 < arr[min_idx]=64	0	1	1	[64, 25, 12, 22, 11]	No
3	Compare arr[j]=12 < arr[min_idx]=25	0	2	2	[64, 25, 12, 22, 11]	No
4	Compare arr[j]=22 < arr[min_idx]=12	0	3	2	[64, 25, 12, 22, 11]	No
5	Compare arr[j]=11 < arr[min_idx]=12	0	4	4	[64, 25, 12, 22, 11]	No
6	Swap arr[i]=64 with arr[min_idx]=11	0	-	4	[11, 25, 12, 22, 64]	Yes
7	Initialize i=1	1	-	1	[11, 25, 12, 22, 64]	No
8	Compare arr[j]=12 < arr[min_idx]=25	1	2	2	[11, 25, 12, 22, 64]	No
9	Compare arr[j]=22 < arr[min_idx]=12	1	3	2	[11, 25, 12, 22, 64]	No
10	Compare arr[j]=64 < arr[min_idx]=12	1	4	2	[11, 25, 12, 22, 64]	No
11	Swap arr[i]=25 with arr[min_idx]=12	1	-	2	[11, 12, 25, 22, 64]	Yes
12	Initialize i=2	2	-	2	[11, 12, 25, 22, 64]	No
13	Compare arr[j]=22 < arr[min_idx]=25	2	3	3	[11, 12, 25, 22, 64]	No
14	Compare arr[j]=64 < arr[min_idx]=22	2	4	3	[11, 12, 25, 22, 64]	No
15	Swap arr[i]=25 with arr[min_idx]=22	2	-	3	[11, 12, 22, 25, 64]	Yes
16	Initialize i=3	3	-	3	[11, 12, 22, 25, 64]	No
17	Compare arr[j]=64 < arr[min_idx]=25	3	4	3	[11, 12, 22, 25, 64]	No
18	Swap arr[i]=25 with arr[min_idx]=25	3	-	3	[11, 12, 22, 25, 64]	Yes (same element)
19	Initialize i=4	4	-	4	[11, 12, 22, 25, 64]	No
20	No inner loop (j from 5 to end empty)	4	-	4	[11, 12, 22, 25, 64]	No
21	Swap arr[i]=64 with arr[min_idx]=64	4	-	4	[11, 12, 22, 25, 64]	Yes (same element)
22	i=5 equals array length, sorting done	-	-	-	[11, 12, 22, 25, 64]	No

💡 i reaches array length, no more elements to sort

Variable Tracker

Variable	Start	After Step 6	After Step 11	After Step 15	After Step 18	After Step 21	Final
i	0	1	2	3	4	5	5
min_idx	0	4	2	3	3	4	4
Array	[64, 25, 12, 22, 11]	[11, 25, 12, 22, 64]	[11, 12, 25, 22, 64]	[11, 12, 22, 25, 64]	[11, 12, 22, 25, 64]	[11, 12, 22, 25, 64]	[11, 12, 22, 25, 64]

Key Moments - 3 Insights

Why do we swap even when min_idx is the same as i?

In steps 18 and 21, swapping the element with itself happens because the minimum element is already at position i. This is harmless and keeps the code simple, as shown in execution_table rows 18 and 21.

Why does the inner loop start from i+1, not from 0?

Because elements before i are already sorted, the inner loop only checks the unsorted part from i+1 to end. This is shown in the execution_table where j starts from i+1 each time.

When does the sorting stop?

Sorting stops when i reaches the array length, meaning all elements have been placed correctly. This is shown in the last row of execution_table where i=5 equals array length.

Visual Quiz - 3 Questions

Look at the execution_table at Step 6, what is the array state after the swap?

A [25, 11, 12, 22, 64]

B [64, 25, 12, 22, 11]

C [11, 25, 12, 22, 64]

D [11, 12, 25, 22, 64]

💡 Hint

Check the 'Array State' column at Step 6 in execution_table

At which step does min_idx first change from 0 to another value?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'min_idx' column in execution_table rows 2 to 5

If the array was already sorted, how would the 'Swap Occurred' column change?

A All swaps would be 'No'

B Swaps would still occur but with same elements

C Swaps would occur only at the last step

D Swaps would be replaced by comparisons

💡 Hint

Refer to steps 18 and 21 where swaps happen with the same element

Concept Snapshot

Selection Sort Algorithm:
- Loop i from 0 to n-1
- Find min element index from i to end
- Swap min element with element at i
- Sorted part grows from left
- Time: O(n²), Space: O(1)
- Simple but inefficient for large arrays

Full Transcript

Selection sort works by dividing the array into a sorted and unsorted part. It repeatedly finds the smallest element in the unsorted part and swaps it with the first unsorted element. This process continues until the entire array is sorted. The code uses two loops: the outer loop moves the boundary of the sorted part, and the inner loop finds the minimum element in the unsorted part. Swapping occurs even if the minimum element is already in place, which simplifies the code. The sorting stops when the outer loop reaches the end of the array. This method is easy to understand but has a time complexity of O(n squared), making it inefficient for large arrays.

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