Исторически зарождение методов машинной сортировки можно отнести еще к прошлому столетию, и за столь длительное время многие специалисты успели испробовать свои силы в этой области. Нет нужды говорить о важности самой области. Сортировка и поиск в той или иной мере присутствуют во всех приложениях; в частности, при обработке больших объемов данных эффективность именно этих операций определяет эффективность, а иногда и работоспособность всей системы. Поэтому можно сказать, что достаточно четкие представления об этой области нужны при решении любой задачи на ЭВМ как обязательные элементы искусства програмирования. В этом уроке мы обсудим простейшие известные способы сортировки.

Итак, начнем...

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

Алгоритм сортировки выбором основан на использовании элементов в качестве ключей для сравнения, при этом конце каждого просмотра только один элемент помещается в свою правильную позицию. Этот алгоритм прост, но неэффективен, так как он не учитывает частично или полностью отсортированных наборов данных. Это означает, что число проводимых сравнений зависит только от количества элементов, и не зависит от содержимого набора данных.

Алгоритм:

Пусть в массиве X находится N элементов, тогда для i от 0 до N - 1 необходимо выполнить следующие шаги:

1. Считаем, что i-ый элемент цепочки является минимальным среди элементов, идущих после него.
2. Для элементов от X[i + 1] до X[N - 1] выполнить сравнение по ключам и найти наименьший элемент. Назовем его X[min].
3. Поменять местами X[min] и X[i]. X[min] теперь находится в своей отсортированной позиции.

После окончания цикла массив отсортирован.

Пример:

Возьмем массив из чисел:

Первый проход:

Замена:

Второй проход:

Третий проход:

Замена:

Четвертый проход:

Замена:

Массив отсортирован

Реализация алгоритма:

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

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

template <typename T>
void CSort(T array[] /* Сортируемый массив */, int size /* Размер массива */)
{
 // Переменные циклов
 int i, j; 
 // Временная переменная для обмена значений элементов
 T temp; 
 // Переменная для хранения индекса минимального элемента в последовательности
 int min; 

 // Находим наименьший элемент в последовательности и помещаем его
 // в нужную позицию
 for(i = 0; i < size - 1; i++)
 {
 // На каждой итерации определяем элемент с индексом i 
 // как минимальный
 min = i;
 for(j = i + 1; j < size; j++)
 {
 // Поиск минимального элемента
 if(array[j] < array[min])
 min = j;
 }
 // Если переменная min не изменилась, то i-ый элемент
 // находится на своем месте
 if(min == i)
 continue;

 // Иначе меняем i-ый и найденный (меньший) элемент местами
 temp = array[i];
 array[i] = array[min];
 array[min] = temp;
 }
}

// Функция для вывода массива
template <typename T>
void PrintArray(T array[], int size)
{
 // функция setw(n) создает поле для вывода с шириной n символов
 for(int i = 0; i < size; i++)
 {
 if(i % 5 == 0)
 cout << endl;
 cout << setw(15) << array[i];
 }
 cout << endl;
}

// Тестирование
void main()
{
 // Инициализация генератора случайных чисел
 srand(time(0));
 // Размер массивов
 const N = 10;
 
 int i;
 int a[N];
 float b[N];

 // Инициализация массивов случайными числами в диапазоне от -10 до 10
 for(i = 0; i < N; i++)
 {
 a[i] = rand() % 21 - 10;
 b[i] = rand() / (float)32767 * 20 - 10;
 }

 // Вывод массивов
 cout << "Array A:\n";
 PrintArray(a, N); 

 cout << "Array B:\n";
 PrintArray(b, N); 

 // Сортировка массивов
 CSort(a, N);
 CSort(b, N);

 // Вывод отсортированных массивов
 cout << endl;
 cout << "Array A:\n";
 PrintArray(a, N); 

 cout << "Array B:\n";
 PrintArray(b, N); 
}