Описание переменных и процедур:

i, j, l, contr, elements – целые числа; mas1 – целочисленные массивы; k, f - тип Boolean;

mas2, mas3, mas4 – массивы строк; T1, T2 – переменные типа TDateTime.

Button1.Click – процедура подготовки и заполнение массива случайными числами.

Button2.Click – процедура сортировки массива методом простых вставок.

Button3.Click – процедура подготовки, заполнение массива случайными числами, процедура сортировки массива методом простых вставок с фиксацией времени сортировки и вывода времени сортировки каждого элемента.

Button4.Click – процедура вывода времени сортировки каждого десятого элемента.

Button5.Click – процедура вывода времени сортировки каждого сотого элемента.

Button6.Click – процедура поиска заданного образца в упорядоченном массиве методом бинарного поиска.

Объем раздела составляет 1 полную печатную страницу.

1. Введение

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

Современные вычислительные системы работают наиболее эффективно при упорядоченных данных. Сортировка информации — это процесс расстановки элементов в некотором поряд­ке. Элементы размещаются следующем образом:

1) вычисления, которые требуют определенного порядка расположения данных, упорядоченных по возрастанию или убыванию, могли выполняться эффек­тивно,

2) результаты имели осмысленный вид,

3) после­дующие операции имели бы упорядоченные исходные данные.

Объем раздела составляет 1 полную печатную страницу.

2. Теоретическая часть

2.1. Сортировка путем вставок

Один из простейших способов отсортировать массив - сортировка вставками.

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

Метод простых вставок. Простейший метод сортировки посредством вставок можно считать наиболее очевидным. Пусть 1 < j < N к записи R_j,...,R_j-1 уже размещены так, что (через K_t обозначается ключ записи R_j). Будем срав­нивать по очереди K_j с K_j-1, K_j-2 ... до тех пор, пока не обнаружим, что запись R_j следует вставить между R_i и R_i+1, тогда подвинем записи R_i+1 и на одну позицию вверх и поместим новую запись в позицию i + 1. Удобно совмещать операции сравнение и перемещения, перемещая их между собой, как продемонстрировало в следующем алгоритме; поскольку запись R_j как бы "погружается" на положенный ей уровень, этот способ часто называют просеиванием или погружением (рис. 1).

Рис. 1. Алгоритм S: сортировка методом простых вставок.

Алгоритм S (Сортировка методам простых вставок). Записи R₁, …, R_N переразмещаются на том же месте. После завершения сортировки их ключи будут упорядочены: K₁<=…<= K_N.

S1. [Цикл по j.] Выполнить шаги от S2 до S5 при i = 2,3,...Т и после этого завершить выполнение процедуры.

S3. [Установка i, К, R] Присвоить I ß j - 1, Kß K_j, Rß R_j. (На последующих шагах будет предпринята попытка вставить запись R в нужное место, сравнивая К с K_j ( при убывающих значениях i.)

S3. [Сравнение К: К(] Если К > K_j , то перейти к шагу S5 (Мы нашли искомое место для записи R.)

S4. [Перемещение R_j, уменьшение i.) Присвоить R_i+1ß R_j , i ß i - 1. Еcли i > 0, то вернуться к шагу S3. (Еcли i=0, то К — наименьший из рассмотренных до сих пор ключей, а значит, запись R должна занять первую позицию.)

S5. (Перенос R на место R_i+1) Присвоить R_i+1ß R

В табл. 1 показан процесс выполнения алгоритма S на множестве из шестнадцати чисел, которые используются для примеров в этом разделе. Данный метод чрезвы­чайно просто реализуется программно.

Время выполнения этой программы равно 9B+10N—ЗА—9 машинных циклов, где N — число сортируемых запасен, А — число случаев, когда на шаге S4 значение i убывает до 0, а В — количество перемещений записей. Ясно, что А равно числу случаев, когда Kj < min{K1,... ,K j-i) при 1 < j < N, т. e. это число левосторонних минимумов. Нетрудно прийти к выводу, что В тоже известно: число перемещения записей при фиксированном j равно числу инверсий ключа Kj, так что В равно числу ин­версий перестановки К1, К2,...KN. Следовательно,

Схематически метод сортировки простыми вставками можно схематически изобразить следующим образом. На рис.2 (a) мы вынимаем элемент 3. Затем элементы, расположенные выше, сдвигаем вниз - до тех пор, пока не найдем место, куда нужно вставить 3. Это процесс продолжается на рис.2(b) для числа 1. Наконец, на рис.2(c) мы завершаем сортировку, поместив 2 на нужное место.

Если длина нашего массива равна n, нам нужно пройтись по n - 1 элементам. Каждый раз нам может понадобиться сдвинуть n - 1 других элементов, получая алгоритм с временем работы O(n2).

Сортировка вставками относится к числу методов сортировки по месту. Ей не требуется вспомогательная память, сортировка элементов массива осуществляется, используя только память, занимаемую самим массивом. Кроме того, она является устойчивой - если среди сортируемых ключей имеются одинаковые, после сортировки они остаются в исходном порядке.

Рис. 2 Сортировка вставками