5.2.Метод Шелла (сортировка

субывающим шагом)

►разбить на n частей (группы)

►шаг m

0,	m,	2m...
1,	m+1,	2m+1,….
2,	m+2,	2m+2,	3m+2…..

каждая часть сортируется отдельно вставками (любымалгоритмом)

выбирается меньший шаг и повтор

M=3

5 8

58

M=25 6 56

M=12 6 2 6

11

04

11

0	1
1	1
0	1
2	1
	1

51

1

5 1

0

62

62

82

81

0

81

0

8 1

1

1

1

1

4

1

4

1

4

1

4

1

4

►void Shell(int A[], int n)

►{ d = n; d = d / 2;

►while (d > 0) //цикл выбора шага

►{ for (i = 0; i < n - d; i++)

►	{ int j = i; //запомнить индекс
	текущего

►

d])

►

d];

►

►}

while (j >= 0 && A[j] > A[j +

//сравнить все элементы группы

{ count = A[j];	A[j] = A[j +
A[j + d] = count; j--; }	}
d = d / 2; }

M=	64, 32, 16, 8, 4 ,2 ,1

рекомендуемый шаг по Шеллу h1=[n/2], hi=h((i-1)/2).

рекомендуемый шаг по Хиббарду

h=2k+1где 2k<n<=2k +1

О(n(log2n)2)

2. Сортировка разделением

►Быстрая сортировка

(Ч. Хоаром в 1962 г. и представляет собой рекурсивный алгоритм, основанный на принципе декомпозиции)

3		1	4	5		9	3	7
		1		6			5
		4	9	7				3
								5
4	9	7	11		23	3		56
4	9	7	11		23	535		56
4	7		9	11		23		35	56
4	7		9	11		23		35	56

2	1	сортировка			7
		4	5	3
3	1		6	5

2 1 4

31

2	1	4
3	1

4	1
	1

5	3	7
6	5
5	3	7
6	5

5	9	2
6		3

►// m[] - массив чисел; sm - индекс 1-ого

элемента массива

►// em - индекс последнего элементов массива

►int GetHoarBorder(int m[], int sm, int

em); //разбиение массива

►int* SortHoar(int m[],int sm, int em)

►{ if (sm < em)

►{int hb = GetHoarBorder(m, sm, em);

►	SortHoar(m, sm, hb);
►	SortHoar(m, hb+1,em); }

►returnm;

►int GetHoarBorder(int m[], int sm, int em)

►{ int i = sm-1,j = em+1;

►int brd = m[sm]; int buf;

►while (i < j)

►{ while(m[--j]> brd);

►while(m[++i]< brd);

►if(i< j){buf = m[j]; m[j] = m[i]; m[i] =

buf;}; }; ► return j;

►}