# Algorithm: Selection Sort

Find the minimum and put it on the left end

## Complexity

- O(n²)

## Algorithm

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

## 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;

}

}