Алгоритмические языки_ Лабораторная работа №3 -... Методические указания к лабораторной работе 3 по дисциплине Алгоритмические языки и программирование для студентов специальности 230100 (ивт)
 Скачать 329 Kb.
|
Сортировка вставками Сортировка простыми вставками в чем-то похожа на вышеизложенные методы.Аналогичным образом делаются проходы по части массива, и аналогичным же образом в его начале «вырастает» отсортированная последовательность... Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[0]...a[i] упорядочена. При этом по ходу алгоритма в нее будут вставляться (см. название метода) все новые элементы. Будем разбирать алгоритм, рассматривая его действия на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n]. На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива. Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте (вставка завершена), либо они меняются местами и процесс повторяется.  Таким образом, в процессе вставки мы «просеиваем» элемент x к началу массива, останавливаясь в случае, когда Найден элемент, меньший x Достигнуто начало последовательности. Алгоритм сортировки вставками представлен ниже: i-цикл от 0 до size с шагом 1 x = a[i] j-цикл от i-1 пока (j >= 0 И a[j] > x) с шагом -1 a[j+1] = a[j] все j-цикл a[j+1] = x все i-цикл Аналогично сортировке выбором, среднее, а также худшее число сравнений и пересылок оцениваются как O(n2), дополнительная память при этом не используется. Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет досортирован очень быстро. Это, вкупе с устойчивостью алгоритма, делает метод хорошим выбором в соответствующих ситуациях. Сортировка подсчетомДанный метод сортировки требует использования вспомогательного массива, по размеру совпадающего с исходным. В этот массив помещаются отсортированные элементы. Суть метода заключается в том, что на каждом шаге подсчитывается, в какую позицию результирующего массива надо записать очередной элемент исходного массива. Выглядит это так: Для i = 0 До N-1 k = 0 Для j = 0 До N-1 Если A(i) > A(j) Или A(i) = A(j) И j < i, То k = k +1 Все-Если Все-Для-j B(k) = A(i) Все-Для-i Вычисление номера позиции, куда нужно поместить очередной элемент, реализуется, исходя из следующих соображений. Слева от B(k) должны стоять элементы, меньшие или равные B(k). Значит, число k складывается из количества элементов меньших A(i) и, возможно, некоторого числа элементов, равных A(i). Условимся, что из равных мы будем учитывать только те элементы, которые в исходном массиве стоят левее A(i). Сортировка слияниемЭтот метод сортирует массив последовательным слиянием пар уже отсортированных подмассивов, поэтому его и назвали сортировкой слиянием. Поскольку данный метод имеет повышенную (по сравнению с уже рассмотренными) сложность, то алгоритм данного метода предлагается найти в литературе и реализовать самостоятельно. Линейный поиск в массивеЛинейным поиском называется обычный просмотр всего массива на предмет нахождения отдельного элемента, отвечающего заданному условию. Линейный поиск – простейшая разновидность алгоритмов поиска данных. Например, если нам требуется найти число 5 в массиве из 15 элементов, то мы начинаем поиск с элемента с номером 0 и последовательно проверяем каждый элемент на равенство числу 5. Если совпадение найдено – необходимо запомнить номер элемента и завершить цикл поиска. Ввиду простоты алгоритма его псевдокод и реализация не приводятся и предлагаются для самостоятельной работы. |