![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Сортировка массива простыми включениями
Метод простых вставок предполагает разделение всего массива элементов на упорядоченную часть, которая вначале содержит лишь один элемент, и неупорядоченную. Очередной элемент из неупорядоченной части вставляется в определенное место упорядоченной части, проходя сравнение с ее элементами. При поиске подходящего места удобно чередовать сравнения и пересылки, т.е. как бы " просеивать" выбранный элемент, сравнивая его с очередным элементом a [j] и либо вставляя, либо пересылая a [i] направо и продвигаясь налево. Заметим, что " просеивание" может закончиться при двух различных условиях: найден элемент a [j] с ключом меньшим, чем ключ x или достигнут левый конец готовой последовательности. При этом упорядоченная часть удлиняется на один элемент. Сортировка заканчивается при окончании неупорядоченной части. При данной сортировке общее число сравнений приблизительно равно
При этом требуется количество проходов по данным P
Рассмотрим пошагово сортировку методом простых вставок на рис.5
Рисунок 5. Пример сортировки массива простыми включениями
Число Ci сравнений ключей при i-м просеивании составляет самое большее i-1, самое меньшее 1 и, если предположить, что все перестановки n ключей равновероятны, в среднем равно i/2. Число Мi пересылок (присваиваний) равно Ci+2 (учитывая барьер). Поэтому общее число сравнений и пересылок есть
Cmin = n-1 Mmin = 2 (n-1) Cср. = (n2+n-2) /4 Mср. = (n2+9n-10) /4 Cmax = ((n2+n) - 1) /2 Mmax = (n2+3n-4) /2.
Алгоритм сортировки простыми включениями можно легко улучшить, пользуясь тем, что готовая последовательность a [1], …, a [i-1], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее, применив бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения. Сортировка массива простым обменом (" метод пузырька")
Данный алгоритм основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут отсортированы все элементы массива. Очевидно, что в наихудшем случае, когда минимальное значение ключа элемента имеется у самого правого элемента, число просмотров равно size − 1. ффективность сортировки. За один проход среднее число сравнений равно С=size/2. При этом среднее число возможных пересылок М=1.5*С (в предположении, что проверяемое условие выполняется в половине случаев). Минимальное количество проходов равно1, максимальное − size -1, а среднее − size/2. Следовательно,
|