алгоритм сортировки «вставкой»

[curly182]

Необходимо реализовать алгоритм сортировки «выбором».
Производить сортировку целых, вещественных чисел, строк. Если кто нибудь делал что то подобное - поделитесь.. Язык - С++

[ISergeyN]

для строк не покатит.

#include <iostream>
using namespace std;

template<typename T> void selectSort(T*, long);

int main()
{
	int		arr_i[5] = {3,2,1,5,4};
	float	arr_f[5] = {3.1f,2.2f,1.1f,1.2f,4.0f};
	selectSort(arr_i,5);
	selectSort(arr_f,5);

	cout<<"arr_i: [ ";
	for(int i = 0; i < 5; ++i)
		cout<<arr_i[i]<<" ";
	cout<<"]"<<endl;

	cout<<"arr_f: [ ";
		for(int i = 0; i < 5; ++i)
			cout<<arr_f[i]<<" ";
	cout<<"]"<<endl;
	return 0;
}

template<typename T> void selectSort(T *a, long size) 
{
	long k;
	T x;
	for(long i=0; i < size; i++) 
	{ 
		k = i; 
		x = a[i];
		for(long j=i + 1; j < size; j++) 
			if ( a[j] < x ) 
			{
				k = j; 
				x = a[j]; 
			}
		a[k] = a[i]; 
		a[i] = x; 
	}
}

[Studentus]

Необходимо разработать алгоритм сортировки вставки в список.Подскажите как он работает??? По Кнуту ничего не понятно(( Других источников не нашёл.