Сортировка отбором

Сортировка отбором заключается в том, что программа сначала анализирует массив, находя в нем элемент с минимальным значением. Затем этот наименьший элемент обменивается местами с первым элементом массива. Далее процесс повторяется для подмассива, начиная со второго элемента. Затем для подмассива, начиная с третьего элемента и так далее. В результате каждого прохода минимальные значения занимают свои позиции последовательно, в итоге получаем отсортированный массив. По производительности данный тип сортировки сравним с алгоритмом пузырьковой сортировки, т.к. для массива из n элементов нужно выполнить n - 1 проход, а для каждого подмассива нужно выполнить n - 1 сравнение. Когда обрабатываемый подмассив будет содержать всего-лишь один элемент, значит массив отсортирован.

Программа, демонстрирующая алгоритм сортировки отбором:

//Сортировка отбором

#include <iostream>
#include <iomanip>

//прототип функции, выводящей массив на экран
void print(int[], int);
using namespace std;

int main()
{

    //определяем переменные
    const int size = 10;
    int array[size] = { 35, 12, 7, 8, 47, 98, 5, 56, 17, 83};
    int min, index, temp;

    //выводим исходный (неотсортированный) массив на экран
    cout << "Nosorted array: " << endl;
    print(array, size);

    //начинаем сортировать
    //цикл проходов
    for (int i = 0; i < size - 1; i++)
    {

        //задаем начальные значения
        min = array[i];
        index = i;

        //цикл перебора элементов массива
        for (int j = i; j < size; j++)
        {

            //находим минимальный элемент
            if (min > array[j])
            {

                //запоминаем минимальный элемент и его индекс
                min = array[j];
                index = j;

            }

        }

        //меняем элементы массива местами
        temp = array[i];
        array[i] = array[index];
        array[index] = temp;

    }

    //выводим отсортированный массив на экран
    cout << "Sorted array: " << endl;
    print(array, size);

    return 0;

}

//функция, печатающая массив
void print (int a[], int sizeOfArray)
{

    for (int i = 0; i < sizeOfArray; i++)

        cout << setw(4) << a[i];

    cout << endl << endl;

}

Результат работы программы:

Можно таже реализовать алгоритм сортировки отбором с помощью рекурсии. Вариант с рекурсией приведен ниже:

//Сортировка отбором (рекурсия)

#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <time.h>

void printArray(int[], int);
int selectionSort(int[], int, int);

using namespace std;

int main()
{

    const int size = 15;
    int array[size];
    int i = 0;

    srand(time(NULL));

    for (int i = 0; i < size; i++)

        array[i] = rand() % 100;

    cout << "Nosorted array: " << endl;
    printArray(array, size);

    selectionSort(array, size, i);

    cout << "Sorted array: " << endl;
    printArray(array, size);

    return 0;

}

int selectionSort(int array[], int size, int i)
{

    if (i < size - 1)
    {

        int min = array[i];
        int index = i;
        int temp;

        for (int j = i; j < size; j++)
        {

            if (min > array[j])
            {

                min = array[j];
                index = j;

            }

        }

        temp = array[i];
        array[i] = array[index];
        array[index] = temp;

        return selectionSort(array, size, i + 1);

    }
    else

        return 0;

}

void printArray(int array[], int size)
{

    for (int i = 0; i < size; i++)

        cout << setw(4) << array[i];

    cout << endl << endl;

}

Результат работы программы: