Программа методом

"пузырька"

1.2. Шейкер-сортировка

или челночная

►всякий следующий просмотр можно делать в противоположном направлении и фиксировать нижнюю и верхнюю границы упорядоченной части

►Среднее число сравнений и перестановок имеет порядок n^2 .

Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину.

►void Swap(int *B, int i) //функция обмена

►{ int temp;

►temp = B[i]; B[i] = B[i - 1]; B[i - 1] = temp;

►}

►//функция шейкерной сортировки

►void ShakerSort(int *B, int Start, int N)

►{ int Left, Right, i; Left = Start; Right = N - 1;

► while (Left <= Right)
► {	for (i = Right; i >= Left; i--)
►	if (B[i - 1] > B[i]) Swap(B, i);	Left++;

►for(i = Left; i <= Right; i++)

► if (B[i - 1] > B[i]) Swap(B, i);

Right--;

► }

Сортировка выбором

►void SelectSort(int A[], int n) ►{ int k, min;

►for(int i = 0; i < n; i++)

►	{ k = i;	min = A[i];
►	for(int	j = i + 1; j < n; j++)
►	if(A[j] < min) { k = j; min =
	A[j]; }
►	A[k] = A[i]; A[i] = min; }

4. Сортировка выбором

23

35

23

2 3

4 35

411

11	4	56		9
7	44
11		56		9
7
11	23	56		9	7
1
1	23	56		9	35
7			9
	2
	3

Оценка

►Общее количество сравнений будет

(n –1 ) + (n – 2) +…+ 1 = n (n – 1) / 2 ≈ n2 / 2

►Максимальное число перестановок (n – 1) ►4n + n(n – 1) операций присваивания

n(n–1)/2 + n – 1 + 4n + n(n – 1) = n2 + 9n /2 – 1 О(n2)

Число перестановок O(n)

Эффект – перестановки затратны по времени

5. Сортировка

вставками

►трудоемкость алгоритма при линейном поиске n*log(n)

►трудоемкость алгоритма при двоичном поиске n*n/4

реализуема на списках

5.1 ПРОСТАЯ ВСТАВКА

5	8	7	6	1	2	//
			0	4	2
5	8	7	6	1	2	//

8	7	6	1 0	2	4	// 2 5
		0	4	2
7	60	14	22	//	5	8

►void InsertSort(int A[], int

n) //сортировка вставками ►{ int t, i, j;

►for (i = 1; i < n; i++) //для

очередного элемента ► { t = A[i]; //сохранить

►for (j = i - 1; j >= 0 && A[j] > t; j--) //поиск места вставки

►A[j + 1] = A[j]; //сдвиг

элементов массива ► A[j+ 1] = t; } }

Анализ

Число сравнений

максимальное: n (n – l) / 2

Число сдвигов

максимальное: n (n – l) / 2

Количество перестановок

максимальное: 2(n – l)

Основных операций

n(n – l) + 2(n – l) = n2 + n – 2

В среднем

n2 / 4 операций сравнения и n2 / 4 операций полуобмена элементов местами (перемещений)

О(n2)

естественностью поведения не требует дополнительной памяти

для больших массивов, этот метод неэффективен.