Студопедия

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

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

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






Сортировка методом Вставки






 

Метод Вставок чем-то похож на метод Выбора, однако более эффективен, за счет того, что отсортированная часть выглядит скорее как упорядоченная, а из неотсортированной части берется элемент и вставляется в нужное место упорядоченной части. Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте (вставка завершена), либо они меняются местами и процесс повторяется. Если заменить первый элемент массива на сторожевой элемент, заведомо наименьший, среди остальных элементов массива, то при значении счетчика j=0 внутреннего цикла будет заведомо верно array[o]< =x, таким образом не нужно проверять условие для вставки в первый элемент во внутреннем цикле. Затем заменим обратно сторожевой на изначальный элемент и вставим в нужное место последовательности array[1]…array[n-1].

Переведем эту задачу в алгоритм для написания в дальнейшем его кода:

1. Заменим первый элемент массива заведомо наименьшим, который можно определить как наименьший из значений для указанного типа или функцией определения наименьшего элемента. Предварительно первый элемент запомним во временной переменной. Далее создадим цикл проходов по всем элементам массива:

backup=array[0];

SetMin(array[0]); // в данном случае пользовательская функция

for (i=1; i< size; i++){

x=array[i]; // запомним текущий элемент

}

2. Будем перебирать упорядоченную часть до тех пор, пока не найдется нужное место для вставки текущего элемента. Для этого создадим соответствующий цикл с проверкой этого условия. После того, как место будет найдено, вставим туда текущий элемент:

for (j=i-1; array[j]> x; j--) // поиск в цикле нужного места с соответств. условием

array[j+1] = array[j]; // освобождаем место для вставки, сдвинув все вправо

 

array[j+1] = x; // кода место будет найдено, вставим туда элемент

3. Вставим в подходящее место первый элемент (который менялся на заведомо минимальный):

for (j=1; j< size & & a[j] < backup; j++) // поиск подходящего места

array[j-1] = array[j]; освободим место, сдвигая другие элементы влево

array[j-1] = backup; // вставим элемент

 

Таким образом, блок-схема и весь алгоритм выглядит так:

 

Рис. 1.3. Блок-схема сортировки Вставками

 

long i, j, x, backup;

 

backup=array[0];

SetMin(array[0]); // в данном случае пользовательская функция

for (i=1; i< size; i++){

x=array[i]; // запомним текущий элемент

for (j=i-1; array[j]> x; j--) // поиск в цикле нужного места

array[j+1] = array[j]; // освобождаем место, сдвинув все вправо

 

array[j+1] = x; // кода место будет найдено, вставим туда элемент

}

 

for (j=1; j< size & & a[j] < backup; j++) // поиск подходящего места для backup

array[j-1] = array[j]; освободим место, сдвигая другие элементы влево

array[j-1] = backup; // вставим элемент

 

Аналогично сортировке выбором, среднее, а также худшее число сравнений и пересылок оцениваются как Theta(n2), дополнительная память при этом не используется. Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет досортирован очень быстро. Это, вкупе с устойчивостью алгоритма, делает метод хорошим выбором в соответствующих ситуациях.

 






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