Selection sort

Selection Sort

Generate Random Numbers

How to use ?

Enter an array separated by commas as : 16,15,15,10,1 or just press the hand icon to generate a random array then press enter or Sort button. Sorting will start and you can watch each pass as it gets sorted. When it shows green it means the two of them are being compared when red shows, it means the left number is greater than right number so it needs swapping The blue color means the number is at its correct position and thus sorted it will continue to check other numbers until it reaches end.

Selection Sort Overview

History

Selection sort has been around since the early days of computer programming. It was developed as a simple, intuitive algorithm for sorting data. The concept has been used in various forms across multiple programming languages since the 1960s.

Current Uses

  • Small Data Sets: Efficient for small datasets where performance is not critical.
  • Memory Constraints: Often used in systems with limited memory resources.
  • Selection Problems: Sometimes applied in selection algorithms where the smallest or largest element is needed.

Time and Space Complexity

Time Complexity

  • Best Case: O(n2) – Regardless of the initial arrangement.
  • Average Case: O(n2) – Quadratic complexity for average cases.
  • Worst Case: O(n2) – Quadratic complexity for worst cases.

Space Complexity

Space Complexity: O(1) – It is an in-place sorting algorithm requiring a constant amount of additional space.

Pseudo Code

function selectionSort(arr):
    n = length(arr)
    for i from 0 to n-1:
        minIndex = i
        for j from i+1 to n:
            if arr[j] < arr[minIndex]:
                minIndex = j
        /* Swap the found minimum element with the first element */
        temp = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = temp
    return arr

Key Characteristics

  • Stability: Selection sort is not a stable sorting algorithm.
  • Adaptability: It does not adapt well to varying input patterns.

Summary

Selection sort is a simple algorithm that divides the input list into a sorted and an unsorted region. Despite its O(n2) complexity, its simplicity makes it useful for small datasets and educational purposes.

Selection Sort Code Implementation