Sorting Algorithm
Selection Sort Algorithm

Selection Sort Algorithm

Selection Sort is a simple and intuitive comparison-based sorting algorithm. It divides the input list into two parts: the sorted subarray and the unsorted subarray. The algorithm selects the smallest (or largest) element from the unsorted subarray and swaps it with the leftmost unsorted element.

How Selection Sort Works

  1. Two Subarrays:

    • The array is divided into two subarrays: sorted and unsorted.

  2. Selection and Swap:

    • In each iteration, the smallest (or largest) element is selected from the unsorted subarray and swapped with the leftmost unsorted element.

  3. Expansion of Sorted Subarray:

    • The sorted subarray expands, and the unsorted subarray contracts in each iteration.

  4. Repeat Until Sorted:

    • Continue this process until the entire array is sorted.

Key Features

  • Simple Implementation: Selection Sort is easy to understand and implement.
  • In-Place Sorting: It sorts the elements within the original array without requiring additional memory.

Efficiency

  • Time Complexity: The time complexity of Selection Sort is O(n^2) for average and worst-case scenarios.

  • Space Complexity: Selection Sort has a space complexity of O(1) as it sorts elements in place.

Advantages

Selection Sort has several advantages, including:

  • Simple Implementation: It is straightforward to implement and understand.
  • In-Place Sorting: It sorts elements within the original array without requiring additional memory.
  • Memory Efficient: Requires very little additional memory space for processing.

Disadvantages

Selection Sort also has some limitations, such as:

  • Quadratic Time Complexity: Has a time complexity of O(n^2), making it inefficient for larger datasets.
  • Not Suitable for Large Lists: Performs poorly on larger, unsorted arrays.

Selection Sort Implementation in JavaScript

Here's an example of Selection Sort implemented in JavaScript:

Sorting-Algo/selection.js
function selectionSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        let minIndex = i;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
    return arr;
}
 
const unsortedArray = [12, 34, 54, 2, 3];
const sortedArray = selectionSort(unsortedArray);
console.log("Sorted Array:", sortedArray);

In this JavaScript code:

  • The selectionSort function implements the Selection Sort algorithm.
  • It iterates through the array, selects the minimum element, and swaps it with the leftmost unsorted element.
  • The example usage demonstrates how to use the Selection Sort function.

Tracing

Here are step-by-step instructions for tracing selection sort:

Initial State: Write down the unsorted array. Unsorted: [64, 25, 12, 22, 11]

Iteration 2: Find the minimum element in the unsorted part of the array (starting from index 0). In this case, the minimum element is 11, located at index 4. Swap the minimum element (11) with the first element (64). Unsorted: [11, 25, 12, 22, 64]

Iteration 2: Move to the next unsorted part of the array (excluding the first element, which is now sorted). Find the minimum element in this new unsorted part (starting from index 1). The minimum element is 12, located at index 2. Swap the minimum element (12) with the second element (25). Unsorted: [11, 12, 25, 22, 64]

Iteration 3: Continue this process for the remaining unsorted elements. Find the minimum element in the unsorted part (starting from index 2). The minimum element is 22, located at index 3. Swap the minimum element (22) with the third element (25). Unsorted: [11, 12, 22, 25, 64]

Iteration 4: Move to the next unsorted part of the array (excluding the first four elements, which are now sorted). Find the minimum element in this new unsorted part (starting from index 3). The minimum element is 25, located at index 3 (which remains the same). No swap is needed. Unsorted: [11, 12, 22, 25, 64]

Final State: All elements are now sorted. Sorted Array: [11, 12, 22, 25, 64]

These steps show how selection sort repeatedly finds the minimum element in the unsorted part of the array and moves it to its correct position in the sorted part until the entire array is sorted in ascending order.

Radix Sort AlgorithmShell Sort