Скачиваний:
47
Добавлен:
02.05.2014
Размер:
6.81 Кб
Скачать
Изобретено множество различных алгоритмов сортировки. Почему же так много методов сортировки? Для программирования это частный случай вопроса: “Почему существует так много методов х?”, где х пробегает множество всех задач. Ответ состоит в том, что каждый метод имеет свои преимущества и недостатки, поэтому он оказывается эффективнее других при некоторых конфигурациях данных и аппаратуры. К сожалению, неизвестен “наилучший” способ сортировки; существует много наилучших методов в зависимости от того, что сортируется, на какой машине, для какой цели. Говоря словами Редьярда Киплинга , “существует 9 и еще 60 способов сложить песню племени, и каждый из них в отдельности хорош”.Полезно изучить характеристики каждого метода сортировки, чтобы можно было производить разумный выбор для конкретных предложений но мы рассмотрим лишь один из методов сортировки – метод простых вставок.
Сортировка вставками. Одно из важных семейств методов сортировки: предполагается, что перед рассмотрением записи Rj, предыдущие записи R1,…,Rj-1 уже упорядочены, и Rj вставляется в соответствующее место. На основе этой схемы возможны несколько любопытных вариаций. Рассмотрим одну из них.
Простые вставки. Простейшая сортировка вставками относится к наиболее очевидным. Пусть 1<j?N и записи R1,…,Rj-1 уже размещены так, что
K1<K2?Kj-1,
где Kj – это ключ записи Rj.
Будем сравнивать по очереди Kj с Kj-1,Kj-2,… до тех пор, пока не обнаружим, что запись Rj следует вставить между Ri и Ri+1; тогда подвинем записи Ri+1,…,Rj-1 на одно место вверх и поместим новую запись в позицию i+1. Удобно совмещать операции сравнения и перемещения, перемежая их друг с другом, как показано в следующем алгоритме; поскольку запись Rj как “бы проникает на положенный ей уровень”, этот способ часто называют просеиванием или погружением.
Алгоритм S.(Сортировка простыми вставками.) Запись Ri,…,Rn переразмещаются на том же месте; после завершения сортировки их ключи будут упорядочены: Ki?…?Kn.
S1. [Цикл по j.] Выполнить шаги от S2 до S5 при = 2,3,…,N и после этого завершить алгоритм.
S2. [Установить i, K, r.] Установить i < j-1,K — Kj, R < Rj.(В последующих шагах мы попытаемся вставить запись R в нужное место, сравнивая K с Kj при убывающих значениях i.)
S3. [Сравнить K, Ki.] Если K?Ki, то перейти к шагу S5.(Мы нашли искомое место для записи R.)
S4. [Переместить Ri, уменьшить i.] Установить Ri+1 < Ri, i < i-1. Если i>0, то вернуться к шагу S3. (Если i=0, то K – наименьший из рассмотренных до сих пор ключей, а, значит, запись R должна занять первую позицию.)
S5. [R на место Ri+1.] Установить Ri+1 < R.
В табл.1 показано применение алгоритма к шестнадцати числам, взятым нами для примеров. Этот метод чрезвычайно просто реализуется на вычислительной машине; фактически следующая MIX– программа – самая короткая из всех приемлемых программ сортировки.
Программа S.(Сортировка простыми вставками). Записи, которые надо отсортировать, находятся в ячейках INPUT+1,…,INPUT+N; они сортируются в той же области по ключу, занимающему одно слово целиком. Здесь rI1?j-N; rI2?i, rA?R?K; предполагается, что N?2.
N?2.

01 START ENTI 2-N 1 S1.Цикл по j. j< 2
02 2H LDA INPUT+N, 1 N-1 S2.Установить i, K, R.
03 ENTE2 N-1.1 B+N-1-A i < j-1
04 3H CMPA INPUT.2 B+N-1-A S3.Сравнить K, Ki.
05 JGE 5F B K S5, если K? Ki
06 4H LDX INPUT.2 S4. Переместить Ri,
уменьшить i.
07 STX INPUT+1.2 B Ri+1< Ri
08 DEC2 1 B i< i-1
09 J2P 3B B K S3, если i> 0
10 5H STA INPUT+1.2 N-1 S5. R на место Ri+1
11 INC1 1 N-1
12 J1NP 2B N-1 2? j? N.
Время работы этой программы равно 9В+10N-3А-9 единиц, где N - число сортируемых записей, А – число случаев, когда в шаге S4 значение i убывает до 0, а В – число перемещений. Ясно, что А равно числу случаев, когда Kj<(Ki, …, Kj-1) при 1<j?N, т.е. это число левосторонних минимумов. Немного подумав, нетрудно понять, что В – тоже известная величина: число перемещений при фиксированном j равно числу инверсий ключа Kj, так что В равно числу инверсий перестановки K1 K2 … Kn.
Следовательно, согласно формулам :
A=(min 0, aveHn-1, max N-1, devvHn-Hn)
B = (min 0, ave(N^2-N)/4, max(N^2-N)/2, devvN(N-1)(N+2.5) /6),
А среднее время работы программы S в предположении, что ключи различны и
расположены в случайном порядке, равно (2?25N^2+7.75N-3Hn-6)u.
Приведенные в табл.1 данные содержат 16 элементов; имеются два левосторонних минимума, 087 и 061, и 41 инверсия. Следовательно, N=16, A=2, B=41, а общее время сортировки равно 514u.
Таблица 1.
Сортировка подсчетом (алгоритм С)
Ключи 503 087 512 061 908 170 897 275 653 426 154 509 612 677
COUNT(нач.): 0 0 0 0 0 0 0 0 0 0 0 0 0 0
COUNT(i=N): 0 0 0 0 1 0 1 0 0 0 0 0 0 0
COUNT(i=N-1): 0 0 0 0 2 0 2 0 0 0 0 0 0 0
COUNT(i=N-2): 0 0 0 0 3 0 3 0 0 0 0 0 0 11
COUNT(i=N-3): 0 0 0 0 4 0 4 0 1 0 0 0 9 11
COUNT(i=N-4): 0 0 1 0 5 0 5 0 2 0 0 7 9 11
COUNT(i=N-5): 1 0 2 0 6 1 6 1 3 1 2 7 9 11
……………………………………………………………………………………………….
COUNT(i=2): 6 1 8 0 15 3 14 4 10 5 2 7 9 11
Соседние файлы в папке Курсовая работа по Visual Basic3