# Selection sort | C++ Implementation

**Selection sort** is an in-place sorting algorithm. In the input array there is a sorted portion and an unsorted portion. The algorithm repeatedly finds the smallest element in the unsorted portion of the array and puts it at the end of the sorted portion of the array.

First the algorithm finds the smallest element in the array which is 1 and it is added to the sorted array and then the algorithm finds smallest element in the remaining array and so on.

# Implementation

Here is the implementation of `selection_sort`

function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void selection_sort(int array[], int size)
{
int start_index = 0;
while(start_index < size)
{
int min_index = start_index;
for(int i = start_index+1; i < size; i++)
{
if(array[i] < array[min_index])
{
min_index = i;
}
}
std::swap(array[start_index], array[min_index]);
start_index++;
}
}

The above function works only for integer value. Here is the generic function which works for all data types.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

template<typename T>
void selection_sort(std::vector<T>& array)
{
typedef typename std::vector<T>::iterator Itr;
Itr itr = array.begin();
while(itr != array.end())
{
Itr itr_min = itr;
for(Itr i = itr + 1; i != array.end(); i++)
{
if(*i < *itr_min)
{
itr_min = i;
}
}
std::iter_swap(itr, itr_min);
itr++;
}
}

The function can take a vector of integers or vector of characters or a vector of strings, it sorts all of them. `itr`

is the iterator, initially which points to the first element of the array. `itr_min`

is the iterator which points to the smallest element in the range `[i, array.end())`

. `std::iter_swap`

method is used to swap `itr`

and `itr_min`

iterator and it puts the smallest element in the range, at the end of the sorted portion in the array.

`std::swap`

swap the values whereas `std::iter_swap`

swap the iterators.

Here is the output after running generic function.

### C++ Implementation of Selection Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include <iostream>
#include <vector>
template<typename T>
void selection_sort(std::vector<T>& array)
{
typedef typename std::vector<T>::iterator Itr;
Itr itr = array.begin();
while(itr != array.end())
{
Itr itr_min = itr;
for(Itr i = itr + 1; i != array.end(); i++)
{
if(*i < *itr_min)
{
itr_min = i;
}
}
std::iter_swap(itr, itr_min);
itr++;
}
}
template<typename T>
void print(const std::vector<T>& array)
{
for(auto itr = array.begin(); itr != array.end(); itr++)
{
std::cout << *itr << " ";
}
std::cout << '\n';
}
int main()
{
std::vector<int> v({5, 3, 12, 2, 8});
std::cout << "Original Array :";
print(v);
selection_sort(v);
std::cout <<"Sorted Array :";
print(v);
std::cout << '\n';
std::vector<char> c({'t', 'q', 'a', 'r', 'p'});
std::cout << "Original Array :";
print(c);
selection_sort(c);
std::cout <<"Sorted Array :";
print(c);
std::cout << '\n';
std::vector<std::string> str({"code", "live", "love", "sing", "create"});
std::cout << "Original Array :";
print(str);
selection_sort(str);
std::cout <<"Sorted Array :";
print(str);
std::cout << '\n';
}

You can view this code on Github

Get this post in pdf - Selection Sort

Reference:

Introduction to Algorithms

The Algorithm Design Manual

Data Structures and Algorithms Made Easy

Competitive Programmer’s Handbook - Antti Laaksonen

### You may also like