четверг, 13 июня 2013 г.

Selection Sort (Сортировка выбором)

Идея: ищем наименьший элемент - ставим на первое место массива, ищем второй наименьший элемент - ставим на второе место и т.д.  Причем кол-во итераций поиска следующего наименьшего элемента равно N - 1, т.к. последний элемент после сортировки предыдущих и так будет на своем месте.

Функция меняющая позиции двух элементов: 


template<typename T>
void mySwap(T &first, T &second)
{
T tmp = first;
first = second;
second = tmp;
}

Сортировка выбором:
template <typename T>
void selectionSort(T arr[], int left, int right)
{
for (int i = left; i < right - 1; ++i)
{
int min = i;
for (int j = i + 1; j < right; ++ j)
{
if (arr[min] > arr[j])
{
min = j;
}
}
mySwap(arr[min], arr[i]);
}
}