• Алгоритм:

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

Пирамидальная сортировка сильно улучшает базовый алгоритм, используя структуру данных «куча» для ускорения нахождения и удаления минимального элемента.

• Основные принципы метода

1. Для нахождения наименьшего элемента из n+1 рассматриваемых алгоритм совершает n сравнений. Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки возрастает относительно количества элементов.
2. Алгоритм не использует дополнительной памяти: все операции происходят "на месте".

Давайте, определим, насколько устойчив данный метод? Рассмотрим последовательность из трех элементов, каждый из которых имеет два поля, а сортировка идет по первому из них. Результат ее сортировки можно увидеть уже после шага 0, так как больше обменов не будет. Порядок ключей 2a, 2b был изменен на 2b, 2a.

Таким образом, входная последовательность почти упорядочена, то сравнений будет столько же, значит алгоритм ведет себя не очень оптимально. Однако, такую сортировку можно использовать для массивов имеющих небольшие размеры.

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
template <class T>
void selectSort(T a[], long size) {
    long i, j, k; 
	T x;
 
	for(i=0;i<size;i++) {   	// i - номер текущего шага
		k=i;
		x=a[i];
 
		for(j=i+1;j<size;j++)	// цикл выбора наименьшего элемента
			if(a[j]<x){
				k=j;
				x=a[j];	        // k - индекс наименьшего элемента
			}
		a[k]=a[i];
		a[i]=x;   	// меняем местами наименьший с a[i]
	}
}
 
void main(){
	srand(time(NULL));
	const long SIZE=10;
	int ar[SIZE];
 
	// до сортировки
	for(int i=0;i<SIZE;i++){
		ar[i]=rand()%100;
		cout<<ar[i]<<"\t";
	}
	cout<<"\n\n";
	selectSort(ar,SIZE);
 
	// после сортировки
	for(int i=0;i<SIZE;i++){
		cout<<ar[i]<<"\t";
	}
	cout<<"\n\n";
}