Algorithm: Selection Sort

Find the minimum and put it on the left end

Complexity

• O(n²)

Algorithm

1. Select the first element of the list
2. find the smallest element from the rest
3. swap the first element with the smallest
4. repeat 1 ~3 with the second element until you reach the end of the list

https://www.w3resource.com/php-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-4.php

Comparison with bubble sort

Selection sort is somewhat similar to bubble sort. Only two differences.

• find the smallest and put it in the left end. (bubble sort ultimately brings the biggest to the right end)
• doesn’t need to keep swapping all elements, but just swap with the smallest. (bubble sort keep swapping all element while bringing the biggest to the right end)

python

def selectionsort(list):
  for i in range(len(list) - 1):
    minIndex = i
    for j in range(i+1, len(list)):
      if list[j] < list[minIndex]:
        minIndex = j
    list[i], list[minIndex] = list[minIndex], list[i] 
  return list
   
list = [12,4,7,4,67,8,9,3,2,7,98,6,4]
print(selectionsort(list))

C++

#include <iostream>
using namespace std;
int minIndex;
void selection(int a[], int s){
    for(int i = 0; i < s-1; i++){
        minIndex = i;
        for(int j = i+1; j < s; j++){
            if(a[j] < a[minIndex]){
                minIndex = j;
            }
        }
        swap(a[i], a[minIndex]);
    }
}
int main()
{
    int a[5] = {5,4,3,1,2};
    selection(a, 5);
    for(int i = 0; i < n; i++){
        cout<<a[i]<<endl;
    }
}