Selection Sort Algorithm in DSA C++ - Time & Space Complexity

Time Complexity: Selection Sort Algorithm

O(n²)

Understanding Time Complexity

We want to understand how the time taken by Selection Sort changes as the list size grows.

How does the number of steps increase when sorting bigger lists?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void selectionSort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    std::swap(arr[i], arr[minIndex]);
  }
}
    

This code sorts an array by repeatedly finding the smallest element and moving it to the front.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing elements inside the inner loop.
• How many times: The inner loop runs fewer times each pass, but overall about n*(n-1)/2 times.

How Execution Grows With Input

As the list size grows, the number of comparisons grows roughly with the square of the size.

Input Size (n)	Approx. Comparisons
10	45
100	4,950
1000	499,500

Pattern observation: Doubling the input size roughly quadruples the work.

Final Time Complexity

Time Complexity: O(n²)

This means the time to sort grows quickly as the list gets bigger, roughly proportional to the square of the list size.

Common Mistake

[X] Wrong: "Selection Sort gets faster if the list is already sorted."

[OK] Correct: Selection Sort always compares elements the same way, so it takes the same time regardless of initial order.

Interview Connect

Understanding Selection Sort's time complexity helps you compare it with faster sorting methods and shows your grasp of algorithm efficiency.

Self-Check

"What if we changed the inner loop to stop early when no smaller element is found? How would the time complexity change?"