Курсовая работа: Алгоритмы сортировки, поиска длиннейшего пути во взвешенном графе и поиска покрытия, близкого к кратчайшему

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

а) расширяем готовую подпоследовательность слева: а₀ = х – барьер;

б) просматривая элементы готовой подпоследовательности слева направо, находим такой номер j что и a_i <=x < a_{i +1} ;

в) если j=j-1, то переходим к пункту г), иначе расширяем готовую
подпоследовательность справа, сдвигая ее элементы, начиная с a_i вправо;

г) a_{i +1} = x

д) i = i + 1. Если i <=n, то переходим к п. 2, иначе сортировка заканчивается.

Процесс может закончиться при двух различных условиях: 1) найден элемент с ключом, меньшим, чем ключ x; 2) достигнут конец готовой последовательности. Получается цикл с двумя условиями. Поэтому для некоторого улучшения быстродействия применяется барьер – a[0] присваивается значение ключа x.

Проанализируем этот алгоритм. Число сравнений (С_i ) при i-м просеивании самое большее равно i-1, самое меньшее – 1; если предположить, что все перестановки из n ключей равновероятны, то среднее число сравнения – i/2. Число же пересылок (присваиваний элементов) M_i равно С_i +2 (включая барьер). Поэтому общее число сравнений и число пересылок таковы:

С_min =n-1, M_min =3*(n-1)

C_ave =(n² +n-2)/4, M_ave =(n² +*n-10)/4,

C_max =(n² +n-4)/4, M_max =(n² +3n-4)/2.

Минимальные оценки в случае уже упорядоченной исходной последовательности элементов, наихудшие же оценки – когда они первоначально расположены в обратном порядке. Очевидно, что приведенный алгоритм описывает метод устойчивой сортировки (см. [1]).

Этот алгоритм можно легко улучшить, поскольку готовая последовательность сама уже упорядочена. Поэтому при поиске подходящей позиции для i-го ключа целесообразно использовать двоичный поиск. При этом такой модифицированный алгоритм носит название метода с двоичным включением.

Словесное описание алгоритма сортировки с двоичным включением:

0. В готовую подпоследовательность записывается а₁ , во входную а₂ ,….а_n .

1. i = 2

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

а) организуем бинарный поиск места включения х в готовую подпоследовательность: находим срединный элемент готовой подпоследовательности – a_m , где m =] i/2 (, и сравниваем его с х. Если a_m > х то ведем далее поиск в левой половине готовой подпоследовательности, т.е. опять находим срединный элемент и сравниваем его с х и т.д., пока не найдем номер j такой, что a_i <=x < a_{i +1} , иначе аналогично ведем поиск в правой половине готовой подпоследовательности;

б) если j=j-1, то переходим к пункту в), иначе расширяем готовую подпоследовательность справа, сдвигая ее элементы, начиная с a_i вправо;

в) a_{i +1} = х

3. i=i+1. Если i <= n, то переходим к п. 2, иначе сортировка заканчивается.

Деление пополам производится i*log₂ i. Число сравнений практически не зависит от начального порядка элементов. В нижней части последовательности место включения отыскивается несколько быстрее, чем в верхней, поэтому предпочтительна ситуация, когда элементы немного упорядочены. Фактически, если элементы в обратном порядке, потребуется минимальное число сравнений, если уже упорядочены – максимальное:

C≈n*log₂ (log₂ -log₂ e±0,5). Однако число пересылок так и остается порядка n² . И на самом деле сортировка уже упорядоченного массива потребует больше времени, чем метод с прямыми включениями (см. [1]).

2.3 Выбор структур данных

Алгоритмы сортировки очень сильно зависят от структуры данных, так что выделяют два класса: сортировку массивов и сортировку последовательностей (файлов). В данной работе рассматривается сортировка массивов. Тип данных «массив» удобен тем, что хранится во внутренней памяти и имеет случайный доступ к элементам, то есть более быстрый, чем у последовательности. Поэтому массивы целесообразно использовать для хранения небольших, часто используемых множеств.

Обычно упорядочивающая функция не вычисляется по какому-либо правилу, а хранится как явная компонента (поле) каждого элемента. Её значение называется ключом элемента. Поэтому для представления элемента хорошо подходит тип «запись», что на языке «Pascal» выглядит следующим образом:

TYPE item = RECORD key: INTEGER;

{здесь описаны другие компоненты}

END;