CS205

Selection Sort

O(n²)

Finds the minimum element and places it at the beginning.

Selection Sort
64
34
25
12
22
11
90
0
1
2
3
4
5
6
Ready to start
Step 0 of 0
Speed:500ms
Default
Comparing
Swapping
Sorted
Pivot
Algorithm Info

Finds the minimum element and places it at the beginning.

Best Case
O(n²)
Average Case
O(n²)
Worst Case
O(n²)
Space
O(1)
How It Works
  1. Find the minimum element in the unsorted portion of the array
  2. Swap it with the first unsorted element
  3. Move the boundary between sorted and unsorted portions one step right
  4. Repeat until the entire array is sorted
  5. The sorted portion grows from left to right
Pseudocode
for i = 0 to n-1:
    minIndex = i
    for j = i+1 to n:
        if arr[j] < arr[minIndex]:
            minIndex = j
    swap(arr[i], arr[minIndex])
Complexity Analysis
Time Complexity
Best:O(n²)
Average:O(n²)
Worst:O(n²)
Space Complexity
O(1)
Stable Sort?
No
Advantages & Disadvantages
Advantages
  • Simple to understand and implement
  • Performs minimal number of swaps - O(n)
  • Good when memory writes are expensive
  • In-place sorting - no extra memory needed
Disadvantages
  • Slow - O(n^2) time complexity in all cases
  • Not stable - may change order of equal elements
  • Always performs O(n^2) comparisons even if sorted
  • Not adaptive - doesn't benefit from partially sorted data
When to Use Selection Sort
  • •When minimizing memory writes is important
  • •Small arrays where simplicity is preferred
  • •Educational purposes
  • •When you need a predictable number of swaps