Selection Sort

Why did the selection sort algorithm bring a magnifying glass to the code? Because it was always looking for the smallest problems!

What is Selection Sort?

Selection Sort is a simple comparison-based sorting algorithm. It divides the input list into two parts: the sorted and unsorted regions. In each iteration, Selection Sort selects the minimum (or maximum) element from the unsorted region and moves it to the beginning of the sorted region. The process is repeated until the entire list is sorted.

How it Works

Here's a step-by-step explanation of how Selection Sort works:

1. Start with the entire list as unsorted.

2. In each iteration, find the minimum (or maximum) element in the unsorted region.

3. Swap the minimum element with the leftmost element in the unsorted region, effectively moving it to the end of the sorted region.

4. Expand the sorted region to include the newly sorted element.

5. Repeat steps 2-4 until the entire list becomes sorted.

Selection Sort minimizes the number of swaps, making it an attractive option when the cost of swapping elements is relatively high, such as in memory-constrained environments.

Selection Sort Code in Java:

public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};

        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap arr[i] and arr[minIndex]
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }

        System.out.println("Sorted array:");
        for (int value : arr) {
            System.out.print(value + " ");
        }
    }
}

Selection Sort Code in C:

#include <stdio.h>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // Swap arr[i] and arr[minIndex]
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n);

    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Time and Space Complexity Analysis

The time complexity of Selection Sort can be expressed mathematically as follows:

Let n be the number of elements in the array to be sorted.

• In each iteration of Selection Sort, it scans the unsorted region to find the minimum (or maximum) element and performs one swap operation to move it to the sorted region.

• In the first pass, Selection Sort compares (n - 1) elements to find the minimum.

• In the second pass, it compares (n - 2) elements.

• In the (n-1)-th pass, it compares 1 element.

The total number of comparisons in Selection Sort in the worst case can be calculated as the sum of the first (n-1) natural numbers, which is given by the formula:

$(1 + 2 + 3 + ... + (n-1) = \frac{n \cdot (n-1)}{2})$

So, in the worst case, the number of comparisons made by Selection Sort is approximately

$(\frac{n \cdot (n-1)}{2})$

Therefore, the worst-case time complexity of Selection Sort can be mathematically expressed as:

$$(T(n) = \frac{n \cdot (n-1)}{2} \approx \frac{n^2}{2})$$

Asymptotically, the worst-case time complexity of Selection Sort is O(n^2), which indicates that its performance degrades quadratically with the size of the input array. This makes Selection Sort inefficient for large datasets compared to more efficient sorting algorithms like Quick Sort or Merge Sort, which have better average and worst-case time complexities.

So, the time complexity of Selection sort is:

• Worst-case: O(n^2)

• Average-case: O(n^2)

• Best-case: O(n^2)

And the space complexity is : O(1) (in-place sorting, no additional memory required)

Selection Sort has a quadratic time complexity of O(n^2) in all cases, making it inefficient for large datasets. It performs a fixed number of comparisons and swaps, regardless of the initial order of the elements. While it is not the most efficient sorting algorithm for large datasets, it is simple to implement and can be useful for small datasets or when minimizing the number of swaps is critical.