Программирование на языке С
Страница 75. Сортировка вставкой

2.2.2. Сортировка вставкой

Упорядоченный массив B' получается из В следующим образом: сначала он состоит из единственного элемента К1; далее для i=2,...,N выполняется вставка узла Кi в B' так, что B' остается упорядоченным списком длины i.

Например, для начального списка B=<20,-5,10,8,7> имеем:

 B=<20,-5,10,8,7> B'=<>
 B=<-5,10,8,7> B'=<20>
 B=<10,8,7> B'=<-5,20>
 B=<8,7> B'=<-5,10,20>
 B=<7> B'=<-5,8,10,20>
 B=<> B'=<-5,7,8,10,20>

Функция insert реализует сортировку вставкой.

 /* сортировка методом вставки */
 float *insert(float *s, int m, int n)
 {
 int i,j,k;
 float aux;
 for (i=m+1; i<=n; i++) { aux="s[i];" for (k="m;" k<="i" && s[k]=k; j--) s[j+1]=s[j];
 s[k]=aux;
 }
 return(a);
 }

Здесь оба списка В и В' размещаются в массиве s, причем список В занимает часть s c индексами от i до n, а B' - часть s c индексами от m до i-1.

При сортировке вставкой требуется Q=(n-m)*(n-m) сравнений и не требуется дополнительной памяти.