Algorithm: Selection Sort

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

  • 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;
}
}

--

--

--

Software Engineer

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Why I think great interviews are lost with advents of speed programming?

Growing a Slack Bot from Zero to $25k per month

Overview of AWS and Cloud Computing

Exception Handling

Initializer in Swift

Setting up an Authentication Service using AWS Cognito

Generic Cuckoo Matcher Using Swift KeyPaths

Cloud adoption in Manufacturing: What is holding it back and what can be done differently?

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Poby’s Home

Poby’s Home

Software Engineer

More from Medium

Find the Highest Altitude — Day 102(Python)

Data Structure and Algorithms: Complexity

Python Algorithm: Pt. 12: GREEDY >:D

Circular Linked List