Skip to main content
Practice

Understanding Selection Sort

1. Setting Up Loops​

Two nested loops are used. The outer loop determines the number of passes through the array, while the inner loop compares elements to find the minimum value.

Setting Up Loops
for i in range(n):
  for j in range(i + 1, n):

2. Finding and Swapping the Minimum Value​

In the inner loop, find the minimum value and swap it with the value at the current position.

Finding and Swapping the Minimum Value
if arr[j] < arr[min_index]:
  min_index = j # Store the index of the minimum value

arr[i], arr[min_index] = arr[min_index], arr[i] # Swap the minimum value with the current position

Time Complexity of Selection Sort​

  1. Worst, Best, and Average-Case Time Complexity: All O(n^2)

    • Selection sort searches the entire remaining array for the smallest (or largest) element for each current position. When the array size is n, this requires n-1 comparisons for the first element, n-2 for the second, and so on, totaling ((n-1) + (n-2) + ... + 1) comparisons, which equates to n(n-1)/2 comparisons.

    When expressed in big O notation, the time complexity is O(n^2).

    • The time complexity of selection sort remains constant regardless of the initial ordering of the input data. Whether the array is already sorted, in reverse order, or randomly arranged, the time complexity does not change.

Want to learn more?

Join CodeFriends Plus membership or enroll in a course to start your journey.