![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Сортировка выбором ⇐ ПредыдущаяСтр 5 из 5
Сортировка выбором – возможно, самый простой в реализации алгоритм сортировки. Как и в большинстве других подобных алгоритмов, в его основе лежит операция сравнения. Сравнивая каждый элемент с каждым, и в случае необходимости производя обмен, метод приводит последовательность к необходимому упорядоченному виду. Идея алгоритма очень проста. Пусть имеется массив A размером N, тогда сортировка выбором сводится к следующему: 1. берем первый элемент последовательности A[i], здесь i – номер элемента, для первого i равен 1; 2. находим минимальный (максимальный) элемент последовательности и запоминаем его номер в переменную key; 3. если номер первого элемента и номер найденного элемента не совпадают, т. е. если key≠ 1, тогда два этих элемента обмениваются значениями, иначе никаких манипуляций не происходит; 4. увеличиваем i на 1 и продолжаем сортировку оставшейся части массива, а именно с элемента с номером 2 по N, так как элемент A[1] уже занимает свою позицию; С каждым последующим шагом размер подмассива, с которым работает алгоритм, уменьшается на 1, но на способ сортировки это не влияет, он одинаков для каждого шага.
Код программы на C++:
Сортировка выбором проста в реализации, и в некоторых ситуациях стоит предпочесть ее наиболее сложным и совершенным методам. Но в большинстве случаев данный алгоритм уступает в эффективности последним, так как в худшем, лучшем и среднем случае ей потребуется О(n 2) времени.
Сортировка пузырьком Сортировка пузырьком (обменная сортировка) – простой в реализации и малоэффективный алгоритм сортировки. Метод изучается одним из первых на курсе теории алгоритмов, в то время как на практике используется очень редко. Идея алгоритма заключается в следующем. Соседние элементы последовательности сравниваются между собой и, в случае необходимости, меняются местами. В качестве примера рассмотрим упорядочивание методом пузырьковой сортировки массива, количество элементов N которого равно 5: 9, 1, 4, 7, 5. В итоге должен получиться массив с элементами, располагающимися в порядке возрастания их значений (см. рис.). Вначале сравниваются два первых элемента последовательности: 9 и 1. Так как значение первого элемента больше значения второго, т. е. 9> 1, они меняются местами. Далее сравниваются второй и третий элементы: девятка больше четверки, следовательно, элементы снова обмениваются позициями. Аналогично алгоритм продолжает выполняться до тех пор, пока все элементы массива не окажутся на своих местах. Всего для этого потребуется N*(N-1) сравнений. В частности, на данной последовательности произведено 20 сравнений и только 5 перестановок.
Код программы на C++:
Приведенный код можно улучшить, а именно – вдвое уменьшить количество выполняемых сравнений. Для этого достаточно с каждым шагом i внешнего цикла на i уменьшать количество итераций внутреннего цикла. Ниже показан основной фрагмент алгоритма обменной сортировки для языков C++ и Pascal, его улучшенный вариант.
C++:
Как отмечалось, алгоритм редко используется на практике, поскольку имеет низкую производительность. В лучшем случае сортировка пузырьком потребует O(n) времени, а в среднем и худшем – O(n2).
https://kvodo.ru/category/algorithms
|