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

Пожалуй, самый простой алгоритм сортировок – это сортировка выбором. Судя по названию сортировки, необходимо что-то выбирать (максимальный или минимальный элементы массива). Алгоритм сортировки выбором находит в исходном массиве максимальный или минимальный элементы, в зависимости от того как необходимо сортировать массив, по возрастанию или по убыванию. Если массив должен быть отсортирован по возрастанию, то из исходного массива необходимо выбирать минимальные элементы. Если же массив необходимо отсортировать по убыванию, то выбирать следует максимальные элементы.

Допустим необходимо отсортировать массив по возрастанию. В исходном массиве находим минимальный элемент, меняем его местами с первым элементом массива. Уже, из всех элементов массива один элемент стоит на своём месте. Теперь будем рассматривать не отсортированную часть массива, то есть все элементы массива, кроме первого. В неотсортированной части массива опять ищем минимальный элемент. Найденный минимальный элемент меняем местами со вторым элементом массива и т. д. Таким образом, суть алгоритма сортировки выбором сводится к многократному поиску минимального (максимального) элементов в неотсортированной части массива. Отсортируем массив из семи чисел согласно алгоритму «Сортировка выбором».

исходный массив: 3 3 7 1 2 5 0
1)Итак, находим минимальный элемент в массиве. 0 – минимальный элемент
2)Меняем местами минимальный и первый элементы массива.
Текущий массив: 0 3 7 1 2 5 3
3) Находим минимальный элемент в неотсортированной части массива. 1 – минимальный элемент
4) Меняем местами минимальный и первый элементы массива.
Текущий массив: 0 1 7 3 2 5 3
5) min = 2
6) Текущий массив: 0 1 2 3 7 5 3
7)min = 3
8) Текущий массив:  0 1 2 3 7 5 3 в массиве ничего не поменялось, так как 3 стоит на своём месте
9) min = 3
10) Конечный вид массива:  0 1 2 3 3 5 7 – массив отсортирован

Запрограммируем алгоритм сортировки выбором в С++.

// sorting_choices.cpp: определяет точку входа для консольного приложения.

#include "stdafx.h"
#include <iostream>
#include <ctime>
#include <iomanip>
using namespace std;

void choicesSort(int*, int); // прототип функции сортировки выбором

int main(int argc, char* argv[])
{
    srand(time(NULL));
    setlocale(LC_ALL, "rus");
    cout << "Введите размер массива: ";
    int size_array; // длинна массива
    cin >> size_array;

    int *sorted_array = new int [size_array]; // одномерный динамический массив
    for (int counter = 0; counter < size_array; counter++)
    {
        sorted_array[counter] = rand() % 100; // заполняем массив случайными числами
        cout << setw(2) << sorted_array[counter] << "  "; // вывод массива на экран
    }
    cout << "\n\n";

    choicesSort(sorted_array, size_array); // вызов функции сортировки выбором

    for (int counter = 0; counter < size_array; counter++)
    {
        cout << setw(2) << sorted_array[counter] << "  "; // печать отсортированного массива
    }
    cout << "\n";
    delete [] sorted_array; // высвобождаем память
    system("pause");
    return 0;
}

void choicesSort(int* arrayPtr, int length_array) // сортировка выбором
{
    for (int repeat_counter = 0; repeat_counter < length_array; repeat_counter++)
    {
        int temp = arrayPtr[0]; // временная переменная для хранения значения перестановки
        for (int element_counter = repeat_counter + 1; element_counter < length_array; element_counter++)
        {
            if (arrayPtr[repeat_counter] > arrayPtr[element_counter])
            {
                temp = arrayPtr[repeat_counter]; 
                arrayPtr[repeat_counter] = arrayPtr[element_counter];
                arrayPtr[element_counter] = temp;
            }
        }
    }
}