Selection Sort – Sorting Algorithm

Selection Sort

Selection Sort is a simple but inefficient sorting algorithm. It works by repeatedly finding the smallest (or largest) element in the unsorted portion of the array and swapping it with the first element of the unsorted portion.

---

1. How It Works

1. Treat the first element as the starting point of the unsorted portion.
2. Find the smallest element in the unsorted portion.
3. Swap it with the first element of the unsorted portion.
4. Move the starting point of the unsorted portion to the next element.
5. Repeat until all elements are sorted.

---

2. Characteristics

• Time Complexity:
  • Best/Average/Worst case: O(n^2)
• Space Complexity:
  • Requires almost no additional memory: O(1)
• Unstable Sort:
  • Does not preserve the relative order of equal elements.

---

3. Example Process

Array: [64, 25, 12, 22, 11]

1. First Pass:
   • Find the smallest element: 11.
   • Swap 11 with 64 → [11, 25, 12, 22, 64].
2. Second Pass:
   • Find the smallest element: 12.
   • Swap 12 with 25 → [11, 12, 25, 22, 64].
3. Third Pass:
   • Find the smallest element: 22.
   • Swap 22 with 25 → [11, 12, 22, 25, 64].
4. Fourth Pass:
   • Find the smallest element: 25.
   • Swap 25 with itself → [11, 12, 22, 25, 64].
5. Final Pass:
   • Array is fully sorted.

---

4. Advantages and Disadvantages

Advantages:

• Simple and easy to understand.
• Requires no additional memory for sorting.

Disadvantages:

• Time complexity is O(n^2), making it inefficient for large datasets.
• It is not a stable sort, meaning the relative order of equal elements is not guaranteed.

---

5. Java Implementation

import java.util.Arrays;

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;

        // Loop through all array elements
        for (int i = 0; i < n - 1; i++) {
            // Find the minimum element in the unsorted part
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // Swap the found minimum element with the first element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        System.out.println("Original Array: " + Arrays.toString(arr));

        selectionSort(arr);

        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
}

---

6. Python Implementation

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Find the index of the smallest element in the unsorted part
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        
        # Swap the smallest element with the first element of the unsorted part
        arr[i], arr[min_index] = arr[min_index], arr[i]

# Example usage
if __name__ == "__main__":
    arr = [64, 25, 12, 22, 11]
    print("Original Array:", arr)

    selection_sort(arr)

    print("Sorted Array:", arr)

---

7. Optimizations

• Avoid Unnecessary Swaps: Skip the swap if the minimum element is already in its correct position.
• Loop Termination: Terminate early if no swaps are needed in a pass (though rare in selection sort).

---

8. Applications

Selection Sort is useful in scenarios where:

• The dataset is small.
• Additional memory usage needs to be minimized.

Although Selection Sort is simple and educational, it is rarely used in practical applications due to its inefficiency. For better performance, algorithms like Merge Sort or Quick Sort are preferred.