Algorithm - Selection Sort (Concept,Pseudocode and C++ code)

Selection Sort

Selection sort: select the minimum value!

• Selection sort Algorithm
  • Finds minimum value in given data
  • Replace this minimum with the value at the beginning of the data
  • Repeat the rest of the data in the same way except for the first one

Code Design

sorted from the begining of the data
Every each time the for loop executes, sort after the first index value from the previous loop
turn : One rotation turn of condition check for all list

1. two datas for selection sort
   (3 2)
   (2 3)

   data index for comparing	comparing start point index	comparing end point index
   0	1	1

2. three datas for selection sort
   (3 4 2)
   (2 4 3)
   (2 3 4)

   data index for comparing	comparing start point index	comparing end point index
   0	1	2
   1	2	2

3. four datas for selection sort
   (4 5 3 2)
   (2 5 3 4)
   (2 3 5 4)
   (2 3 4 5)

   data index for comparing	comparing start point index	comparing end point index
   0	1	3
   1	2	3
   2	3	3

Pseudocode

1. for(int standard = 0; standard < len(data_list) - 1 ; ++standard) : repeat for loop
2. lowest = standard
3. for(int index = 0; index < len(data_list); ++index) : repeat after standard
   • if( data_list[lowest] > data_list[index] )
     • lowest = index
4. swapping two data
   • data_list[index] <=> data_list[lowest]

Time Complexity

two for loops : $O(n^2)$

C++ code implementation

#include<iostream>
using namespace std;

void selectionSort(int * data, int size)
{
	for(int standard = 0; standard < size-1 ; ++standard)  //turn 
	{
		int lowest = standard;
		for(int index = standard+1; index < size; ++index)
		{
			if(data[lowest] > data[index])
				lowest = index;
		}
		int temp = data[lowest];
		data[lowest] = data[standard];
		data[standard] = temp;
	}
}
int main()
{
	int list_s[] = {4,5,3,2,1};
	
	int len = sizeof(list_s) / sizeof(list_s[0]);
	cout  << len << endl;
	
	for(int i = 0; i < len; ++i)
		cout << list_s[i] << endl;
		
	selectionSort(list_s, len);
	
	for(int i = 0; i < len; ++i)
		cout << list_s[i] << endl;
		
		
	return 0;
	
}