Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Пузырьковая сортировкаСравниваются и меняются местами при необходимости пары элементов. Можно начать перебирать пары с первой или же с последней. Рассмотрим вариант перебора пар с последней. В результате первого просмотра всех пар самый маленький элемент массива оказывается самым левым (эффект пузырька). Процесс повторяется с оставшимися элементами массива. Результаты первых трех просмотров приведены в таблицах 8.3–8.5. Таблица 8.3 – Результат первого просмотра массива методом пузырьковой сортировки
Таблица 8.4 – Результат второго просмотра массива методом пузырьковой сортировки
Таблица 8.5 – Результат третьего просмотра массива методом пузырьковой сортировки Т.к. после каждого просмотра один элемент массива гарантировано встает на свое место, то для полной сортировки понадобится максимум n-1 просмотр. Однако помимо того, что во время просмотра очередной элемент «гонится» к своему месту, происходит также и частичное упорядочивание («приглаживание») остальных элементов. Поэтому часто массив оказывается упорядоченным раньше, чем через n-1 просмотр. Так что имеет смысл предусмотреть окончание сортировки в случае, если во время очередного просмотра не было обнаружено ни одной «неправильной» пары элементов. В коде, предложенном ниже, для этой цели используется переменная flag.
for(int i=1;i<n;i++){ bool flag=1; for(int j=n-1;j>=i;j--) if(a[j]<a[j-1]){ int tmp=a[j]; a[j]=a[j-1]; a[j-1]=tmp; flag=0; } if(flag) break; } Сортировка устойчивая. В общем случае это одна из самых медленных сортировок, но она легко справляется с частично отсортированными массивами, имеющими лишь небольшие возмущения (а не такие ли массивы мы используем наиболее часто?).
|