Сортировка выбором — это алгоритм сортировки на месте. Во входном массиве есть отсортированная часть и несортированная часть. Алгоритм неоднократно находит наименьший элемент в несортированной части массива и помещает его в конец отсортированной части массива.

Сначала алгоритм находит наименьший элемент в массиве, равный 1, и добавляет его к отсортированному массиву, затем алгоритм находит наименьший элемент в оставшемся массиве и так далее.

Выполнение

Вот реализация функции selection_sort.

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

Вышеупомянутая функция работает только для целочисленного значения. Вот общая функция, которая работает для всех типов данных.

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

Функция может принимать вектор целых чисел, вектор символов или вектор строк, она сортирует их все. itr — это итератор, изначально указывающий на первый элемент массива. itr_min — это итератор, указывающий на наименьший элемент в диапазоне [i, array.end()). Метод std::iter_swap используется для замены итераторов itr и itr_min и помещает наименьший элемент диапазона в конец отсортированной части массива.

std::swap поменять местами значения, тогда как std::iter_swap поменять местами итераторы.

Вот результат после запуска универсальной функции.

C++ реализация сортировки выбором

#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';
}

Вы можете просмотреть этот код на Github

Ссылка:
Введение в алгоритмы
Руководство по проектированию алгоритмов
Простые структуры данных и алгоритмы
Справочник конкурентоспособного программиста — Антти Лааксонен

Вам также может понравиться

Сортировка слиянием
Сортировка вставками
Быстрая сортировка
Сортировка пирамидой

Первоначально опубликовано на https://programmercave0.github.io 29 августа 2017 г.