Algorithms - Selection Sort
Selection sort is a sorting algorithm, specifically an in-place comparison sort.
It has O(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.
Given a pile of cards, a common way to sort the pile is to select and remove the largest (or smallest) card, and then repeat the process until all cards are gone. This approach is selection sort.
This sort is probably the slowest of all the sorting algorithms. It requires quadratic time even in the best case (i.e., when the array is already sorted). It repeatedly performs almost the same task without learning anything from one iteration to the next.
C++ Code:
#include <iostream>
using namespace std;
void swap(int *n, int *m) {
int tmp;
tmp = *m;
*m = *n;
*n = tmp;
}
void print(int a[], int sz) {
for (int i = 0; i < sz; i++ ) cout << a[i] << " ";
cout << endl;
}
void SelectionSort(int a[], int sz) {
int i,j,mn;
/* traverse the entire array */
for (i = 0; i < sz; i++) {
/* find the min */
mn = i;
/* compare against all other elements */
for (j = i + 1; j < sz; j++) {
if (a[j] < a[mn]) mn = j;
}
swap(a[mn], a[i]);
print(a,sz);
}
}
int main()
{
int a[] = {4,6,9,1,2,0,8,7,5,3};
const size_t sz = sizeof(a)/sizeof(a[0]);
print(a,sz);
cout << "---------------------\n" ;
SelectionSort(a, sz);
}
Output:
4 6 9 1 2 0 8 7 5 3 --------------------- 0 6 9 1 2 4 8 7 5 3 0 1 9 6 2 4 8 7 5 3 0 1 2 6 9 4 8 7 5 3 0 1 2 3 9 4 8 7 5 6 0 1 2 3 4 9 8 7 5 6 0 1 2 3 4 5 8 7 9 6 0 1 2 3 4 5 6 7 9 8 0 1 2 3 4 5 6 7 9 8 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
Ph.D. / Golden Gate Ave, San Francisco / Seoul National Univ / Carnegie Mellon / UC Berkeley / DevOps / Deep Learning / Visualization
My YouTube channel