Лекция: Функция сортировки прямым обменом
void bubbleSort(int numbers[], int array_size
{
int i, j, temp;
for( i = 0; i < array size; i++
| for ( j { |
^array size — 1); j > i; j--
if( numbers[j-1] > numbers[j
{
temp = numbers[j-1]; numbers[j-1] = numbers[j]; numbers[j] = temp;
| i = 0 i = 1 i = 2 i = 3 1 = 4 i = 5 i = 6 i = 7 | |||||||||
| l*f | Щ | Щ | ED3 | [iji] | DPI | DPI | |||
| rffl | В | ||||||||
| ~И | l_U | HLt*_l | l_I»a | |[il | |||||
| ■ | г^^СРЧ | У- \rM | KifJ | Eir-Л | |||||
| 1S| | —*»gg1 | F^l | Рд | ||||||
| « | J 55 | ||||||||
| Ц | LiZfl | ||||||||
| E |
Рис. З.4. Пример сортировки
Анализ алгоритма [3]. Число сравнений в алгоритме прямого обмена
С = (п2-п)/2,
а минимальное, среднее и максимальное число перемещений элементов равно со отв етств енно
МтЫ = О, Мер = 3(п2 — п)/2, Мтах = 3(п2-п)/4. Резюме:«обменная сортировка» представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора; фактически в пузырьковой сортировке нет ничего ценного, кроме привлекательного названия. Далее мы рассмотрим улучшенные методы сортировки.