Problem: Selection Sort

Difficulty: Easy
Topics: Sorting Algorithms, Iterative Methods
Companies: Commonly asked in technical interviews.

---

Problem Description

Selection sort is a sorting algorithm that iteratively selects the smallest element from the unsorted portion of the array and swaps it with the element at the beginning of the unsorted portion.

---

How Selection Sort Works

1. Initialization:

• Start with the first element as the minimum index (min_index) of the unsorted portion of the array.

2. Outer Loop:

• Iterate through the array from the beginning to the second-to-last element.
• In each iteration of this loop:
  • Set min_index to the current iterator value, assuming it is the smallest within the unsorted portion.

3. Inner Loop:

• Begin from the next element after the current iterator in the outer loop and compare it with subsequent elements:
  • If any element is found smaller than the current min_index, update min_index to this element's index.

4. Swap:

• After completing the inner loop, if min_index is different from the current iterator in the outer loop, swap the elements at min_index and the current iterator.

5. Repeat:

• Continue this process until the array is sorted.

---

Key Idea

Selection sort works by gradually building up a sorted portion of the array from left to right, ensuring that after each iteration of the outer loop, the left portion of the array is sorted correctly.

---

Time Complexity

Selection sort operates with a time complexity of 𝑂(𝑛²), making it less efficient for large datasets compared to more advanced sorting algorithms like quicksort or mergesort.

---

Example Execution

Unsorted Array:

[64, 25, 12, 22, 11]

Step-by-Step Process:

1. First Pass: Find the smallest element (11) and swap it with the first element.
   Result: [11, 25, 12, 22, 64]
2. Second Pass: Find the next smallest element (12) and swap it with the second element.
   Result: [11, 12, 25, 22, 64]
3. Third Pass: Find the next smallest element (22) and swap it with the third element.
   Result: [11, 12, 22, 25, 64]
4. Fourth Pass: The array is already sorted.

Final Sorted Array:

[11, 12, 22, 25, 64]

---

Why Use Selection Sort?

• Advantages:

  • Simple and easy to implement.
  • Works well for small datasets or arrays that are nearly sorted.

• Disadvantages:

  • Inefficient for large datasets due to its quadratic time complexity.
  • Not suitable for performance-critical applications.

---

Practical Tip

Use selection sort for educational purposes or small datasets. For larger datasets, consider more efficient algorithms like quicksort or mergesort.