Сортировка выборомИдея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке.
template<typename T>
void select_sort(T a[], int size)
{
int k;
T x;
for(int i = 0; i < size; ++i) // i - номер текущего шага
{
k = i;
x = a[i];
for(int j = i + 1; j < size; ++j)// цикл выбора наименьшего элемента
if ( a[j] < x )
{
k = j; // k - индекс наименьшего элемента
x = a[j];
}
a[k] = a[i];
a[i] = x; // меняем местами наименьший с a[i]
}
}
Если входная последовательность почти упорядочена, то сравнений будет столько же, значит алгоритм ведет себя неестественно.
Сортировка пузырькомИдея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.
template<typename T>
void bubble_sort(T a[], int size) {
T x;
for(int i = 0; i < size; ++i) // i - номер прохода
{
for(int j = size - 1; j > i; --j) // внутренний цикл прохода
{
if ( a[j-1] > a[j] )
{
x = a[j-1];
a[j-1] = a[j];
a[j] = x;
}
}
}
}
Дополнительная память, очевидно, не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.
На практике метод пузырька, даже с улучшениями, работает слишком медленно. А потому - почти не применяется.
Сортировка вставкамиСортировка простыми вставками в чем-то похожа на вышеизложенные методы.
template<typename T>
void insert_sort(T a[], int size)
{
T x;
int j;
for (int i = 0; i < size; ++i)
{
x = a[i];
// поиск места элемента в готовой последовательности
for (j = i - 1; j >= 0 && a[j] > x; --j)
a[j+1] = a[j]; // сдвигаем элемент направо, пока не дошли
// место найдено, вставить элемент
a[j+1] = x;
}
}
Аналогично сортировке выбором, среднее, а также худшее число сравнений и пересылок оцениваются как Theta(n2), дополнительная память при этом не используется.
Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет досортирован очень быстро. Это, вкупе с устойчивостью алгоритма, делает метод хорошим выбором в соответствующих ситуациях.
Ну Собственно проверка
template<typename T>
void out_arr(T arr[], int size)
{
for(int i = 0; i < size; ++i)
std::cout << arr[i] << " ";
}
int main()
{
int arr0[6] = {9,5,4,6,2,1};
int arr1[6] = {9,5,4,6,2,1};
int arr2[6] = {9,5,4,6,2,1};
select_sort(arr0, 6);
bubble_sort(arr1, 6);
insert_sort(arr2, 6);
out_arr(arr0, 6); std::cout << '\n';
out_arr(arr1, 6); std::cout << '\n';
out_arr(arr2, 6); std::cout << '\n';
return 0;
}
Имхо лучше юзать std::sort().
#include <iostream>
#include <algorithm>
#include <functional>
int main()
{
int arr[] = {9,8,7,6,5,4,3,2,1};
int size = sizeof(arr)/sizeof(int);
std::sort(arr, arr + size);
std::copy(arr, arr + size, std::ostream_iterator<int>(std::cout," "));
std::cout << '\n';
std::sort(arr, arr + size,std::greater<int>());
std::copy(arr, arr + size, std::ostream_iterator<int>(std::cout," "));
std::cout << '\n';
return 0;
}
PS.
Если вы новичок,и не понимаете,что такое template
или не проходили этого, то есть два способа справиться с этой проблемой:
1. Загуглить "Шаблоны С++. Материал простой,разберетесь"
2. Убрать эту надпись,а в прототипе букву T заменить типом вашего массива (int, double,..etc)
Про std::sort() можно посмотреть
здесь 
