Selection Sort

Selection sort is a simple comparison-based sorting algorithm that repeatedly selects the minimum (or maximum) element from an unsorted portion of a list or array and places it at the beginning of the sorted portion. It continues this process until the entire list is sorted. Selection sort is not the most efficient sorting algorithm for large lists but is easy to understand and implement.

Here’s a step-by-step explanation of how selection sort works:

  1. Initialization: Start with an unsorted list of elements.
  2. Find the minimum element: Search through the unsorted portion of the list to find the minimum (or maximum) element. To do this, you iterate through the unsorted portion, comparing each element with the current minimum (or maximum) found so far. If you find an element smaller (for sorting in ascending order) than the current minimum (or larger for descending order), update the minimum (or maximum) to the new value.
  3. Swap the minimum element: After finding the minimum (or maximum) element in the unsorted portion, swap it with the leftmost element in the unsorted portion. This effectively moves the minimum (or maximum) element to its correct position in the sorted portion.
  4. Expand the sorted portion: Increment the index of the sorted portion, effectively expanding it by one element, and shrink the unsorted portion by one element.
  5. Repeat steps 2-4: Continue these steps (finding the minimum, swapping, and expanding the sorted portion) until the entire list is sorted.
  6. Termination: The algorithm terminates when the unsorted portion becomes empty, and the sorted portion contains all the elements in sorted order.

The selection sort algorithm has efficiently sorted the list by repeatedly finding the minimum element and swapping it with the leftmost unsorted element.

Understanding Selection Sort with an Example

Example-1 – Unsorted List: [64, 25, 12, 22, 11]

  1. Step 1 – Find the minimum: Initially, the first element, 64, is considered as the minimum.
    • Current Minimum: 64
    • Unsorted List: [64, 25, 12, 22, 11]
  2. Step 2 – Compare and find the minimum: Compare the current minimum with the next element, 25. Since 25 is smaller than 64, update the minimum to 25.
    • Current Minimum: 25
    • Unsorted List: [64, 25, 12, 22, 11]
  3. Step 3 – Continue searching: Continue comparing the current minimum (25) with the remaining elements. 12 is smaller than 25, so update the minimum to 12.
    • Current Minimum: 12
    • Unsorted List: [64, 25, 12, 22, 11]
  4. Step 4 – Swap minimum with the first element: Swap the minimum element (12) with the first element (64). This places the minimum in its correct sorted position at the beginning of the list.
    • Sorted Portion: [12]
    • Unsorted List: [25, 64, 22, 11]
  5. Step 5 – Repeat Steps 1-4: Repeat the process for the remaining unsorted portion of the list.
    • Current Minimum: 11
    • Unsorted List: [25, 64, 22, (11)]
    • Swap the minimum element (11) with the first element in the remaining unsorted portion.
    • Sorted Portion: [12, 11]
    • Unsorted List: [25, 64, 22]
  6. Repeat Steps 1-5: Continue the process until the entire list is sorted.
    • Current Minimum: 22
    • Unsorted List: [25, 64, (22)]
    • Swap the minimum element (22) with the first element in the remaining unsorted portion.
    • Sorted Portion: [12, 11, 22]
    • Unsorted List: [25, 64]
    • Current Minimum: 25
    • Unsorted List: [25, (64)]
    • Swap the minimum element (25) with the first element in the remaining unsorted portion.
    • Sorted Portion: [12, 11, 22, 25]
    • Unsorted List: [64]
  7. Final Step: The unsorted portion is now empty, and the entire list is sorted in ascending order.
    • Sorted List: [12, 11, 22, 25, 64]

Selection sort has a time complexity of O(n^2), where n is the number of elements in the list. It is not the most efficient sorting algorithm for large lists but is simple to understand and implement.

Example-2  Unsorted List: [23, 5, 78, 2, 12, 56, 9]

Step 1:

  • Current Minimum: 2
  • Swap 2 with the first element (23 moves to the second position).

Step 2:

  • Current Minimum: 5
  • Swap 5 with the second element (23 moves to the third position).

Step 3:

  • Current Minimum: 9
  • Swap 9 with the fourth element (23 moves to the fifth position).

Step 4:

  • Current Minimum: 12
  • Swap 12 with the fifth element (23 moves to the sixth position).

Step 5:

  • Current Minimum: 23
  • Swap 23 with itself (no change).

Step 6:

  • Current Minimum: 56
  • Swap 56 with the seventh element (23 moves to the seventh position).

Step 7 (Final Step):

  • Current Minimum: 78
  • Swap 78 with itself (no change).

Now, the entire list is sorted in ascending order:

Sorted List: [2, 5, 9, 12, 23, 56, 78]

Python Code – Selection Sort

Selection sort has a time complexity of O(n^2), where n is the number of elements in the list. This makes it inefficient for large lists, especially when compared to more advanced sorting algorithms like merge sort or quicksort, which have better average-case time complexities. However, selection sort has the advantage of being easy to understand and implement, making it useful for educational purposes and for sorting small lists.