Selection Sort Algorithm in DSA C#

Mental Model

Selection sort finds the smallest item and puts it at the start, then repeats for the rest.

Analogy: Imagine picking the smallest apple from a basket and placing it in a new row, then picking the next smallest from the remaining apples, and so on.

Unsorted array:
[7] -> [3] -> [5] -> [2] -> [4]
Sorted part: []
Unsorted part: [7] -> [3] -> [5] -> [2] -> [4]

Dry Run Walkthrough

Input: array: [7, 3, 5, 2, 4]

Goal: Sort the array in ascending order using selection sort

Step 1: Find smallest from entire array and swap with first element

[2] -> [3] -> [5] -> [7] -> [4]

Why: We put the smallest number 2 at the start to begin the sorted part

Step 2: Find smallest from remaining array (index 1 to end) and swap with element at index 1

[2] -> [3] -> [5] -> [7] -> [4]

Why: 3 is already smallest in the unsorted part, so no swap needed

Step 3: Find smallest from remaining array (index 2 to end) and swap with element at index 2

[2] -> [3] -> [4] -> [7] -> [5]

Why: 4 is smallest in unsorted part, swap with 5

Step 4: Find smallest from remaining array (index 3 to end) and swap with element at index 3

[2] -> [3] -> [4] -> [5] -> [7]

Why: 5 is smallest in unsorted part, swap with 7

Step 5: Last element is now sorted, no action needed

[2] -> [3] -> [4] -> [5] -> [7]

Why: Only one element left, array is fully sorted

Result:

Sorted array:
[2] -> [3] -> [4] -> [5] -> [7]

Annotated Code

DSA C#

using System;

class SelectionSort {
    public static void Sort(int[] arr) {
        int n = arr.Length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            // Find index of smallest element in unsorted part
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap smallest found with element at i
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void PrintArray(int[] arr) {
        for (int i = 0; i < arr.Length; i++) {
            Console.Write(arr[i]);
            if (i != arr.Length - 1) Console.Write(" -> ");
        }
        Console.WriteLine();
    }

    static void Main() {
        int[] array = {7, 3, 5, 2, 4};
        Console.WriteLine("Original array:");
        PrintArray(array);
        Sort(array);
        Console.WriteLine("Sorted array:");
        PrintArray(array);
    }
}

for (int i = 0; i < n - 1; i++) {

iterate over each position to place the correct smallest element

int minIndex = i;

assume current position holds smallest element initially

for (int j = i + 1; j < n; j++) {

search the unsorted part for a smaller element

if (arr[j] < arr[minIndex]) { minIndex = j; }

update minIndex when a smaller element is found

int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp;

swap smallest found element with element at current position

Output

Original array:

7 -> 3 -> 5 -> 2 -> 4

Sorted array:

2 -> 3 -> 4 -> 5 -> 7

Complexity Analysis

Time: O(n^2) because for each element we scan the rest to find the smallest

Space: O(1) because sorting is done in place without extra arrays

vs Alternative: Compared to bubble sort, selection sort does fewer swaps but same number of comparisons

Edge Cases

empty array

no operations, array remains empty

DSA C#

for (int i = 0; i < n - 1; i++) {

array with one element

no swaps needed, array stays same

DSA C#

for (int i = 0; i < n - 1; i++) {

array with all elements equal

no swaps needed, array stays same

DSA C#

if (arr[j] < arr[minIndex]) { minIndex = j; }

When to Use This Pattern

When you need a simple, easy-to-understand sorting method that works by repeatedly selecting the smallest item, use selection sort.

Common Mistakes

Mistake: Swapping elements inside the inner loop instead of after finding the smallest
Fix: Only swap once per outer loop iteration after finding the minimum index

Mistake: Not updating minIndex when a smaller element is found
Fix: Update minIndex inside the inner loop when a smaller element is found

Summary

Selection sort repeatedly finds the smallest element and moves it to the front.

Use it when you want a simple sorting method and the array size is small.

The key insight is to select the smallest element in the unsorted part and swap it once per iteration.

Practice

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

easy

A. Divide the list into halves and sort each half separately

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

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

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

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

   Unlike divide and conquer or adjacent swaps, selection sort directly selects the minimum each time.

3. Final Answer:

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

4. Quick Check:

   Selection sort = find minimum repeatedly [OK]

Hint: Selection sort picks smallest element each pass [OK]

Common Mistakes:

• Confusing selection sort with bubble sort
• Thinking it divides the list like merge sort
• Assuming it uses a pivot like quicksort

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

easy

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

B. arr[i] = arr[minIndex]; arr[minIndex] = arr[i];

C. temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp;

D. swap(arr[i], arr[minIndex]);

Solution

1. Step 1: Understand swapping in C#

   C# does not support tuple unpacking or direct swap functions; we use a temporary variable to swap values.

2. Step 2: Check each option

   temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; uses a temp variable correctly. arr[i] = arr[minIndex]; arr[minIndex] = arr[i]; overwrites arr[i] before assigning arr[minIndex]. swap(arr[i], arr[minIndex]); is invalid syntax. arr[i], arr[minIndex] = arr[minIndex], arr[i]; is Python style, not C#.

3. Final Answer:

   temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; -> Option C

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 a temp variable
• Using Python or other language syntax
• Overwriting one element before saving it

3. What will be the output of the following C# code snippet after applying selection sort?

int[] arr = {64, 25, 12, 22, 11};
// Apply selection sort here
for (int i = 0; i < arr.Length - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < arr.Length; j++) {
        if (arr[j] < arr[minIndex]) {
            minIndex = j;
        }
    }
    int temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
}
Console.WriteLine(string.Join(", ", arr));

medium

A. 11, 12, 22, 25, 64

B. 64, 25, 12, 22, 11

C. 25, 12, 22, 11, 64

D. 11, 22, 12, 25, 64

Solution

1. Step 1: Trace the selection sort iterations

   First pass finds 11 (smallest) and swaps with 64. Array: [11, 25, 12, 22, 64]. Second pass finds 12 and swaps with 25. Array: [11, 12, 25, 22, 64]. Third pass finds 22 and swaps with 25. Array: [11, 12, 22, 25, 64]. Fourth pass finds 25 (already in place). Final sorted array is [11, 12, 22, 25, 64].

2. Step 2: Confirm final output

   The printed output is the sorted array joined by commas.

3. Final Answer:

   11, 12, 22, 25, 64 -> Option A

4. Quick Check:

   Selection sort output = sorted array [OK]

Hint: Selection sort outputs sorted array ascending [OK]

Common Mistakes:

• Not swapping correctly during iterations
• Confusing indexes and swapping wrong elements
• Assuming original array stays unchanged

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

int[] arr = {3, 1, 4, 2};
for (int i = 0; i < arr.Length; i++) {
    int minIndex = i;
    for (int j = i + 1; j < arr.Length; j++) {
        if (arr[j] > arr[minIndex]) {
            minIndex = j;
        }
    }
    int temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
}

medium

A. Change 'if (arr[j] > arr[minIndex])' to 'if (arr[j] < arr[minIndex])'

B. Change outer loop to 'for (int i = 0; i < arr.Length - 1; i++)'

C. Remove the swap code inside the loop

D. Initialize minIndex to 0 instead of i

Solution

1. Step 1: Analyze the comparison condition

   The code uses 'arr[j] > arr[minIndex]' which finds the maximum instead of minimum, so it sorts in descending order, not ascending.

2. Step 2: Correct the comparison for ascending order

   Changing the condition to 'arr[j] < arr[minIndex]' finds the minimum element as required by selection sort.

3. Final Answer:

   Change 'if (arr[j] > arr[minIndex])' to 'if (arr[j] < arr[minIndex])' -> Option A

4. Quick Check:

   Comparison must find minimum element [OK]

Hint: Use '<' to find minimum in selection sort [OK]

Common Mistakes:

• Using '>' instead of '<' in inner loop
• Looping one extra time causing index errors
• Not swapping elements properly

5. Given an array int[] arr = {5, 3, 8, 6, 2, 7, 4, 1}, how many swaps will the selection sort algorithm perform to sort it in ascending order?

hard

A. 6

B. 5

C. 7

D. 8

Solution

1. Step 1: Understand swap count in selection sort

   Selection sort swaps once per outer loop iteration if the minimum is not already at the current position.

2. Step 2: Count swaps for given array

   Array length is 8, so outer loop runs 7 times (0 to 6). Each iteration finds minimum and swaps if needed. Here, minimum is at current index in one iteration, so total swaps are 5.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Swaps = number of times minimum is not at current index [OK]

Hint: Selection sort swaps at most n-1 times, but only when needed [OK]

Common Mistakes:

• Counting swaps as number of elements
• Assuming swaps happen every iteration
• Confusing swaps with comparisons