Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Сортировка вставками
|
|
Одним из наиболее простых и естественных методов внутренней сортировки является сортировка с простыми включениями или вставками. Идея алгоритма очень проста. Пусть имеется массив ключей a[1], a[2],..., a[n]. Для каждого элемента массива, начиная со второго, производится сравнение с элементами с меньшим индексом (элемент a[i] последовательно сравнивается с элементами a[i-1], a[i-2]...) и до тех пор, пока для очередного элемента a[j] выполняется соотношение a[j] > a[i], a[i] и a[j] меняются местами. Если удается встретить такой элемент a[j], что a[j] < = a[i], или если достигнута нижняя граница массива, производится переход к обработке элемента a[i+1] (пока не будет достигнута верхняя граница массива).
Аналогичным образом делаются проходы по части массива, и аналогичным же образом в его начале " вырастает" отсортированная последовательность.
Однако в сортировке «пузырьком» или «выбором» можно было четко заявить, что на i -м шаге элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[0]...a[i] упорядочена. При этом по ходу алгоритма в нее будут вставляться все новые элементы.
На i -м шаге работы алгоритма последовательность разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n].
На следующем, (i+1)- м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива. Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте (вставка завершена), либо они меняются местами и процесс повторяется (рис. 8).
| 0 | 1 | 3 | 4 |
Последовательность на текущий момент. Часть a[0]…a[2] уже упорядочена.
| 2 ↔ 4 | 2 ↔ 3 | Вставка завершена | |||||||||||||||||||||
|
|
| |||||||||||||||||||||
2
2
1
Вставка числа 2 в отсортированную подпоследовательность. Сравниваемые пары выделены
Рис. 8
Таким образом, в процессе вставки мы " просеиваем" элемент x к началу массива, останавливаясь в случае, когда:
1) найден элемент, меньший x, или
2) достигнуто начало последовательности.
Иногда этот метод называют сортировкой «просеиванием».
template< class T> void insertSort(T a[], long size) { T x; long i, j; for (i=0; i < size; i++) { // цикл проходов, i - номер прохода x = a[i]; // поиск места элемента в готовой последовательности for (j=i-1; j> =0 & & a[j] > x; j--) a[j+1] = a[j]; // сдвигаем элемент направо, пока не дошли // место найдено, вставить элемент a[j+1] = x; }}Аналогично сортировке выбором, среднее, а также худшее число сравнений и пересылок оцениваются О(n2), дополнительная память при этом не используется.
Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет «досортирован» очень быстро. Именно эти качества алгоритма делают его широко применимым на практике в соответствующих ситуациях.
|
|