9b3ea869

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


Упорядоченный массив 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. Схема движения индексов при сортировке вставкой.



Содержание раздела