Selection Sort

Selection Sort is a simple comparison-based sorting algorithm. It divides the array into two parts: the sorted part and the unsorted part. During each iteration, the smallest (or largest) element from the unsorted part is selected and swapped with the first element of the unsorted part, expanding the sorted part by one element.

While Selection Sort is easy to understand and implement, it is not the most efficient for large datasets due to its time complexity of \(O(n^2)\).

Algorithm

Here are the steps of the Selection Sort algorithm:

  1. Start with the first element of the array as the current minimum.
  2. Compare the current minimum with the remaining unsorted elements to find the smallest element.
  3. Swap the smallest element with the first element of the unsorted part.
  4. Move the boundary between the sorted and unsorted parts one element to the right.
  5. Repeat steps 1-4 until the entire array is sorted.

Example

Let’s sort the array [5, 3, 8, 4, 2] using Selection Sort and explain each step:

Initial Array:

Selection Sort Example - Initial Array

Pass 1:

Find the smallest element in the unsorted part [5, 3, 8, 4, 2].

Assume that the first element is smaller.

  1. Compare 5 and 3.
    3 is smaller.
  2. Compare 3 and 8.
    3 is still smaller.
  3. Compare 3 and 4.
    3 is still smaller.
  4. Compare 3 and 2.
    2 is smaller.

The smallest element is 2. Since it is Pass 1, we have to swap 2 with the first element.

Array after Pass 1, the smallest element in the array has taken its right place.

Pass 2:

Find the smallest element in the unsorted part [3, 8, 4, 5].

Assume 3 is the smallest.

  1. Compare 3 and 8:
    3 is smaller.
  2. Compare 3 and 4:
    3 is still smaller.
  3. Compare 3 and 5:
    3 is still smaller.

The smallest element is 3. Since 3 is already in the correct position, no swap is needed.

Array after Pass 2: [2, 3, 8, 4, 5]

Pass 3:

Find the smallest element in the unsorted part [8, 4, 5].

Assume that first element in the unsorted part, 8 is the smallest.

  1. Compare 8 and 4:
    4 is smaller
  2. Compare 4 and 5:
    4 is still smaller

The smallest element is 4. Swap 4 with the first element of unsorted array.

Array after Pass 3: [2, 3, 4, 8, 5]

Pass 4:

Find the smallest element in the unsorted part [8, 5].

Assume that first element in the unsorted array, 8, as the smallest.

  1. Compare 8 and 5:
    5 is smaller

The smallest element is 5. Swap 5 with first element in the unsorted part.

Array after Pass 4

Final Sorted Array:

Complexity of Selection Sort

1. Time Complexity:

  • Worst-Case Complexity (\(O(n^2)\)): This occurs when the array is in reverse order, requiring the maximum number of comparisons and swaps.
  • Average-Case Complexity (\(O(n^2)\)): On average, each element must be compared with half of the remaining unsorted elements.
  • Best-Case Complexity (\(O(n^2)\)): Even if the array is already sorted, Selection Sort performs all comparisons.

2. Space Complexity:

Selection Sort is an in-place algorithm, meaning it does not require additional space for another array. Its space complexity is \(O(1)\).

3. Stability:

Selection Sort is not a stable sorting algorithm. Equal elements may not maintain their relative order after sorting.

Selection Sort Algorithm in Different Programming Languages

Go Program for Selection Sort

Reference: Go – Selection Sort

Program – selection_sort.go

</>
Copy
package main

import "fmt"

// Function to implement Selection Sort
func selectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        // Find the index of the minimum element in the unsorted section
        minIndex := i
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        // Swap the found minimum element with the first element
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    }
}

func main() {
    // Input array
    arr := []int{64, 25, 12, 22, 11}

    // Display the original array
    fmt.Println("Original array:", arr)

    // Sort the array using Selection Sort
    selectionSort(arr)

    // Display the sorted array
    fmt.Println("Sorted array:", arr)
}

Output

Conclusion

Selection Sort is a simple sorting algorithm that is easy to understand and implement. While it is not efficient for large datasets, it is useful for small datasets or as a teaching tool to understand sorting concepts.