Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Методические указания. Сортировка данным методом выполняется путем многократного просмотра множества ключей






    Сортировка данным методом выполняется путем многократного просмотра множества ключей. Мы будем рассматривать числовые ключи, поэтому в дальнейшем будут рассматриваться массивы чисел. При каждом последовательном просмотре массива сравниваются соседние числа (ключи). Если числа в паре расположены в порядке возрастания, оставляем их без изменения; в противном случае меняем их местами. Затем (в любом случае) переходим к следующей паре. Сортировка считается оконченной, если в ходе просмотра не была произведена ни одна перестановка. В результате на первом шаге процесса (после 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.

    Сортировка окончена, так как во время четвертого просмотра не было совершено ни одной перестановки.

    Количество сравнений определяется максимальным количеством инверсий:

    (2.1)

    где , . Определение инверсий, относящихся к описанию комбинаторных свойств перестановок, можно найти в [1]. Если для (массив упорядочен), то минимальное количество сравнений

    (2.2)

    Если k=N-1, то формула принимает вид

    (2.3)

    Среднее количество сравнений может быть подсчитано по формуле, исходя из того, что среднее количество инверсий равно :

    (2.4)

    Приведенные формулы указывают на возможную оценку количества сравнений при использовании метода пузырька. Блок-схема сортировки представлена в Приложении 1.






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.