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.

Selectionsort

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.

Selectionsort

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

Merge Sort
Insertion Sort
Quicksort
Heapsor