Классические сортировки числовых массивов

Общие требования к сортировкам:

1. Используется участок памяти с исходным массивом

2. Допустимы дополнительные затраты памяти только для вспомогательных переменных

 

Примем, что массивы сортируем по возрастанию и рассмотрим 5 сортировок и сравним их между собой.

● Обменная сортировка (сортировка обменами)

Индекс	Исходный массив	Действия	Полученный массив	Количество сравнений
i=0 (номер прохода)	8 3 6 2 (сравнение 8 и 3)	Обмен	3 8 6 2
	3 8 6 2 (сравнение 3 и 6)	Нет обмена	3 8 6 2
	3 8 6 2 (3 и 2)	Обмен	2 8 6 2	3 (n-1)
i=1	2 8 6 3 (8 и 6)	Обмен	2 6 8 3
	2 6 8 3 (6 и 3)	Обмен	2 3 8 6	2 (n-1-1)
i=2	2 3 8 6 (8 и 6)	Обмен	2 3 6 8	1 (n-1-2)

  

Вывод: количество проходов (n-1) , в каждом проходе фиксированное число сравнений, в i-ом проходе (n-1-i). Общее количество сравнений Σ (от i=0 до n-2) (n-1-i)=n(n-1)/2. Наилучший случай – массив уже отсортирован и тогда обменов не будет. Наихудший – пересортировка, обмены = сравнениям. Вычислительную эффективность (сложность) сортировок оцениваем количеством сравнений и обменов и обозначаем О(n²).

 

 

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

A[0]	A[1]	A[2]	A[3]	A[4]	Действия
5	2	4	7	3	Выбрать 2, поменять местами 2 и a[0]
Проход 0
2	5	4	7	3	Выбрать 3, поменять местами с a[1]
	Проход 1
2	3	4	7	5	Выбрать 4, поменять местами с a[2]
		Проход 2
2	3	4	7	5	Выбрать 5, поменять местами с a[3]
			Проход 3
2	3	4	5	7

Вычислительная сложность этой сортировки: сортировка требует фиксированного числа сравнений, в i-ом проходе происходит сравнений i-ого элемента с a[i+1] до a[n-1], количество сравнений (n-1)-(i+1)-1 =n -1 –I, общее число проходов n(n-1)/2, O(n²), количество обменов всегда один на один проход, т.е. О(n), наилучшего и наихудшего случаев нет.

● Пузырьковая сортировка

Для повышения эффективности вводится переменная last, в которую помещается индекс первого в последнем сравнении элемента, поэтому в очередном проходе сортируются элементы с индексами от 0 до last. Процесс прекращается, когда при очередном проходе сохраняется last=0.

 

проходы	A[0]	A[1]	A[2]	A[3]	A[4]
0, last 0	5	2	4	7	3	5 ← → Last 0
	2	5	4	7	3	5←→4 Last 1
	2	4	5	7	3	5←→7 Last 1
	2	4	5	7	3	7←→ Last 3
	2	4	5	3	7
1, last 0	2	4	5	3	7	2←→4 Last 0
	2	4	5	3	7	4←→5 Last 0
	2	4	5	3	7	5←→3 Last 2
	2	4	3	5	7
При 3 last=0

Вычислительная сложность: если массив отсортирован, то нужен всего один проход с (n-1) сравнениями, это наилучший случай – О(n), наихудший – при пересортировке, требуется (n-1) проход, на каждое сравнение 1 обмен, вычислительная сложность О(n²). Эта сортировка в общем случае хуже сортировки выбором за счет большего количества обменов.

 

● Сортировка вставками

Исходный массив	A[0] 5	A[1] 2	A[2] 4	A[3] 7	A[4] 3
Обработка a[1]=2	2	5 Передвинуть 5 в позицию 1, вставить2 в позицию 0
Обработка a[2]=4	2	4	5 Передвинуть 5 в позицию 2, вставить 4 в позицию 1
A[3]=7	2	4	5	7 Оставляем на месте
A[4]=3	2	3	4	5	7 Сдвинуть «хвост» массива в право, вставить 3 в позицию 1

Среднее количество сравнений ½ +2/2+3/2+(n-1)/2=n(n-1)/2. Наилучший случай – массив отсортирован, количество сравнений (n-1), эффективность О(n), наихудший – каждый последующий элемент вставляется на место a[0], это будет при пересортировке, в этом случае сложность n(n-1)/2, O(n²).

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

Превосходит все остальные случаи, требует меньших затрат машинного времени, но не в благоприятном для себя случае, она не лучше других сортировок, но на практике такие случаи весьма редкие. Быстрая сортировка состоит из двух фаз, на первой фазе просматривается исходный массив и делится на 2 подмассива – нижний и верхний, в нижнем массиве помещаются элементы равные или меньшие центрального, в верхний – больше центрального, вторая фаза – рекурсивная, повторяются снова все действия для подмассивов и т.д. до тех пор, пока подмассивы не станут одноэлементнами.

 

Индексы   0 1 2 3 4 5 6 7 8 9

Исх. Массив 80 15 30 60 55 65 40 35 45 70

   Low =0     mid=(low+high)/2=4 high=9

A[mid]=55

 

Вычислительная сложность: пусть подчиняется n=2, пусть массивы делятся поровну, т.е. центральный элемент все время оказывается в середине массива, тогда на первой фазе будет n сравнений, на рекурсивной фазе длины массива n, количество сравнений 2*n/2. Общее число сравнений n+2(n/2)+4(n/2)…=n*k=n*log₂n, на этот случай соответствует уже отсортированному массиву.

Пересортировка массива:

8 7 6  5 4 3 2 1

 

После первой фазы:

4 1 2 3 5 8 6 7

 

При пересортировке затраты машинного времени почти такие же, как для отсортированного массива. Значит случай пересортировки не наихудший случай, наихудший возникает тогда, когда центральный элемент все время попадает в одноэлементный подмассив.

3 8 1  5 9

В этом случае общее количество сравнений n+(n-1)+(n-2)+…+2=n(n+1)/2 -1, вычислительная эффективность O(n²). Следовательно, наихудший случай быстрой сортировки не лучше других, но такой случай маловероятен на практике, значит данная сортировка значительно эффективнее остальных сортировок.

● Поиск

Цель поиска – найти в массиве элемент равный ключу.

 

1. Линейный поиск, т.к. индекс возрастает линейно

 

Наиболее благоприятный O(1), наихудший – последний совпал с ключом O(n), в среднем O(n/2), линейный поиск применяется для коротких массивов.

 

⇐ Предыдущая123456789Следующая ⇒

Поделиться: