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

ОГЛАВЛЕНИЕ

 

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) сравнений и не требуется дополнительной памяти.