![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Методические указания. Сортировка данным методом выполняется путем многократного просмотра множества ключей
Сортировка данным методом выполняется путем многократного просмотра множества ключей. Мы будем рассматривать числовые ключи, поэтому в дальнейшем будут рассматриваться массивы чисел. При каждом последовательном просмотре массива сравниваются соседние числа (ключи). Если числа в паре расположены в порядке возрастания, оставляем их без изменения; в противном случае меняем их местами. Затем (в любом случае) переходим к следующей паре. Сортировка считается оконченной, если в ходе просмотра не была произведена ни одна перестановка. В результате на первом шаге процесса (после 1-го просмотра) на последнее место в массиве из N чисел ставится самое большое число и при следующем просмотре чисел массива анализируется (N-1) чисел, при третьем просмотре (N-2) чисел и т.д. Таким образом, сокращается время упорядочения. Этот метод называют иначе “метод пузырька”: большие элементы (записи с большими ключами), подобно пузырькам, “всплывают” на соответствующую позицию. Приведем пример сортировки массива из 6 чисел: Исходный массив 1 7 6 4 2 5 6 7 4 7 2 7 5 7 после первого просмотра 1 6 4 2 5 7 4 6 2 6 5 6 после второго просмотра 1 4 2 5 6 7 2 4 после третьего просмотра 1 2 4 5 6 7. Сортировка окончена, так как во время четвертого просмотра не было совершено ни одной перестановки. Количество сравнений определяется максимальным количеством инверсий:
где
Если k=N-1, то формула принимает вид
Среднее количество сравнений может быть подсчитано по формуле, исходя из того, что среднее количество инверсий равно
Приведенные формулы указывают на возможную оценку количества сравнений при использовании метода пузырька. Блок-схема сортировки представлена в Приложении 1.
|