Selection Sort Overview

Back to: Python Data Structure and Algorithims

Selection Sort is another simple sorting algorithm. Unlike Bubble Sort, which repeatedly swaps adjacent elements, Selection Sort selects the minimum element from the unsorted portion of the list and places it at the beginning.

We’ll use the same example list as before:

---

Step 1: Understanding the Algorithm

1. Start with the first element.

   • Assume it is the minimum element (min_index = 0).

2. Compare this element with the rest of the list.

   • If a smaller element is found, update min_index to the index of that element.

3. After scanning the entire list, swap the first element with the element at min_index.

   • Now, the first element is in its correct position.

4. Move to the next element and repeat steps 1–3 for the remaining unsorted portion of the list.

5. Continue until the list is completely sorted.

---

Step 2: Step-by-Step Example

Original list: [2, 6, 5, 1, 3, 4]

Pass 1:

• Start with index 0 (value = 2), min_index = 0.

• Compare with 6 → no change.

• Compare with 5 → no change.

• Compare with 1 → update min_index = 3.

• Compare with 3, 4 → no change.

• Swap index 0 with min_index 3.

List after Pass 1: [1, 6, 5, 2, 3, 4] (1 is now sorted)

---

Pass 2:

• Start with index 1 (value = 6), min_index = 1.

• Compare with 5 → update min_index = 2.

• Compare with 2 → update min_index = 3.

• Compare with 3 → update min_index = 4.

• Compare with 4 → update min_index = 5.

• Swap index 1 with min_index 5.

List after Pass 2: [1, 2, 5, 6, 3, 4]

---

Pass 3:

• Start with index 2 (value = 5), min_index = 2.

• Compare with 6 → no change.

• Compare with 3 → update min_index = 4.

• Compare with 4 → no change.

• Swap index 2 with min_index 4.

List after Pass 3: [1, 2, 3, 6, 5, 4]

---

Pass 4:

• Start with index 3 (value = 6), min_index = 3.

• Compare with 5 → update min_index = 4.

• Compare with 4 → update min_index = 5.

• Swap index 3 with min_index 5.

List after Pass 4: [1, 2, 3, 4, 5, 6]

---

Pass 5:

• Index 4 (value = 5) and index 5 (value = 6) are already in order.

• No swaps needed.

Final sorted list: [1, 2, 3, 4, 5, 6]

---

Step 3: Key Points

• Selection Sort always selects the smallest element from the unsorted portion and moves it to its correct position.

• Unlike Bubble Sort, it performs at most one swap per pass, making it slightly more efficient in terms of swaps.

• Time Complexity: O(n²) in all cases

• Space Complexity: O(1) (in-place sorting)