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

Основной принцип пузырьковой сортировки состоит в выталкивании меньших значений на вершину списка, в то время как большие значения опускаются вниз.

Алгоритм пузырьковой сортировки приведен на рис. 14.32. У пузырьковой со­ртировки есть много различных вариантов. В алгоритме пузырьковой сортировки совершается несколько проходов по списку. При каждом проходе происходит срав­нение соседних элементов. Если порядок соседних элементов неправильный, то они меняются местами. Каждый проход начинается с начала списка. Сперва сравнива­ются первый и второй элементы, затем — второй и третий, потом — третий и чет­вертый, и т. д.; элементы с неправильным порядком в паре переставляются. При обнаружении на первом проходе наибольшего элемента списка он переставляется со всеми последующими элементами, пока не дойдет до конца списка. Поэтому при втором проходе нет необходимости производить сравнение с последним элементом.

При втором проходе второй по величине элемент списка опускается во вторую’ позицию с конца. При продолжении процесса на каждом проходе по крайней мере одно из следующих по величине значений встает на свое место. При этом меньшие значения тоже собираются наверху. Если при каком-то проходе не происходит ни одной перестановки элементов, это означает, что все они стоят в нужном порядке, и исполнение алгоритма можно прекратить. Стоит заметить, что при каждом про­ходе ближе к своему месту продвигается сразу несколько элементов, хотя гаран­тированно занимает окончательное положение лишь один.

Дата добавления: 2014-01-03