Сортировка вставкой
Упорядоченный массив 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=k; j--) s[j+1]=s[j]; s[k]=aux; } return(a); }
Здесь оба списка В и В' размещаются в массиве s, причем список В занимает часть s c индексами от i до n, а B' - часть s c индексами от m до i-1 (см. рис.26).
При сортировке вставкой требуется Q=(n-m)*(n-m) сравнений и не требуется дополнительной памяти.
Рис.26. Схема движения индексов при сортировке вставкой.
