Алгоритмы поиска и сортировки данных

1. Обзор предприятия и постановка задач

1.1 Обзор предприятия

1.2 Постановка задачи

2. Основные сведения про используемые алгоритмы сортировки и поиска

3. Разработка программного средства и руководство пользователя

3.1 Описание процесса создания программного средства

3.2 Руководство пользователя

Заключение

Приложения

Введение

Объектом исследования в данной курсовой работе являются алгоритмы сортировки данных и алгоритмы поиска данных.

Предметом исследования в данной курсовой работе являются способы и методы реализации алгоритмов сортировки и алгоритмов поиска на языках программирования высокого уровня, в частности на языке Delphi.

В рамках выполнения курсовой работе необходимо решить следующие основные задачи:

1. Выполнить исследование рассматриваемой организации и точки зрения структуры и используемых технологий.

2. Подробно рассмотреть основные алгоритмы сортировки данных с подробным их описанием и примерами использования.

3. Подробно рассмотреть основные алгоритмы поиска данных с подробным их описанием и примерами использования.

4. Запрограммировать рассмотренные алгоритмы сортировки и поиска в рамках создаваемого программного средства.

5. Разработать детальное руководство пользователя для обучения работе с программой.

Необходимо заметить, что вопросами исследования алгоритмов, их классификацией, анализом и способами их программирования в разное время занимались: Левитин А., Гудман С., Хидетниеми С., Ахо А., Хлопкрофт Дж., Ульман Дж., Цейтлин Г. Е., Кнут Д., Вирт Н., Лорин Г., Макконнелл Дж.

Цель данной курсовой работы — исследование алгоритмов поиска и сортировки данных, приобретение навыков в программировании данных алгоритмов и в конечном итоге — написание программного средства, которое должно реализовывать функции сортировки больших объемов данных и поиска данных.

1. Обзор предприятия и постановка задачи

1.1 Обзор предприятия Открытое акционерное общество «Комитекс» — признанный лидер в производстве нетканых материалов и синтетических волокон в России.

ОАО «Комитекс» находится в городе Сыктывкаре, столице Республики Коми, на северо-востоке европейской части Российской Федерации. Компания была создана в 1979 году и в настоящее время в ней работает около 1000 человек.

ОАО «Комитекс» имеет несколько представительств в различных регионах России: ООО «Комитекс сервис» (г. Москва), ООО «КОМИТЕКСНЕВА» (г. Санкт-Петербург), ЗАО «Комитекс-Авто» (г. Тольятти), Филиал «Комитекс-Киров» (г. Киров), ООО «Комитекс трейдинг» (г. Сыктывкар), ООО «Комитекс Лин» (г. Сыктывкар) и другие.

ОАО «Комитекс» является членом Европейской ассоциации производителей предметов гигиены и нетканых материалов (EDANA), Ассоциации изготовителей нетканых материалов (АСИНЕМ).

Компания обладает большинством известных в настоящее время в мире технологий производства нетканых материалов «сухим способом». Уникальный набор оборудования, сложившийся более чем за 30 лет, коллективный опыт профессионалов, накопленный за годы становления рыночных отношений, позволяют производить широкий спектр высококачественной продукции. На предприятии сертифицирована система качества на соответствие требованиям международного стандарта ISO 9001:2008.

Технологии, используемые на предприятии, позволяют выпускать полотна с широким спектром свойств, применяющиеся в самых разных областях. Это достигается посредством:

· использования различных типов волокон;

· высококачественного процесса формирования холста;

· использования различных технологий скрепления холста:

ь химическим способом;

ь термическим способом;

ь иглопробиванием;

ь холстопрошиванием;

ь комбинированием различных способов;

· разнообразной отделки полученного полотна.

Постепенное наращивание мощностей по выпуску синтетических волокон вывело ОАО «Комитекс» в лидеры по данному виду производства в России. В настоящее время предприятие обеспечивает свои потребности в таких волокнах, что дает дополнительные гарантии качества, объемов, стабильности и гибкости поставок, увеличения технологических возможностей производства нетканых материалов. Кроме того, ОАО «Комитекс» стало одним из основных поставщиков синтетических волокон России для нужд текстильных и других компаний.

Стабильное финансовое положение во многом определяется ежегодным увеличением объема производства, ростом продаж и прибыли.

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

В настоящее время ассортимент предприятия состоит из более чем 50 видов продукции.

ОАО «Комитекс» поставляет свою продукцию 700 потребителям в России и за ее пределами. Гибкий производственный процесс и наличие высококвалифицированных специалистов позволяют дорабатывать продукт в соответствии с требованиями отдельных потребителей. Компьютерная корпоративная система планирования, учета и контроля работы предприятия обеспечивает эффективное использование времени и материальных ресурсов, ускоряет процесс обслуживания клиентов.

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

Основные этапы развития компании:

1979 Основание компании.

1980 Выпуск основы для производства столовой клеенки.

1983 Компания — крупнейший в СССР поставщик нетканой основы.

1985 Выпуск иглопробивных полотен.

1986 Выпуск термоскрепленных полотен.

1991 Экспорт продукции.

1993 Выпуск объемных и холстопрошивных полотен.

1995 Внедрение компьютерной информационной системы управления компанией.

1997 Реализация стратегии роста на рынке полотен для автомобильной промышленности.

1997 Выпуск линолеума на нетканой основе.

1999 Реализация инвестиционной программы модернизации производства.

2000 Расширение производства иглопробивных полотен.

2001 Внедрение системы штрихового кодирования продукции.

2001 Реализация инвестиционной программы расширения производства иглопробивных полотен.

2002 Реализация инвестиционной программы расширения производства.

2002 Сертифицирована система качества на соответствие требованиям МС ISO 9001:2000.

2003 Выпуск полипропиленового волокна.

2004 Реализация инвестиционного проекта и увеличение мощностей предприятия по выпуску иглопробивных полотен.

2005 Выпуск полиэфирного волокна.

2006 Увеличение мощностей по выпуску иглопробивных полотен.

2006;2008 Поэтапное увеличение мощностей предприятия по выпуску полиэфирного волокна.

2008 Увеличение мощностей компании по выпуску иглопробивных и иглопробивных-термоскрепленных полотен.

2009 Компания становится общепризнанным лидером России по производству синтетических волокон.

2010 Увеличение объемов выпуска и расширение ассортимента нетканых материалов для автомобильной промышленности.

2011 Увеличение мощностей по выпуску иглопробивных полотен.

1.2 Постановка задачи В процессе работы на предприятии очень часто возникает необходимость в сортировке и поиске данных. Предприятие имеет дело с большими объемами информации (списки поставщиков, перечень комплектующих, ассортимент продукции, списки сотрудников) и обрабатывать такие массивы вручную — это довольно большие затраты времени. Кроме того при ручной обработке не исключена вероятность ошибок.

Именно для этой цели и поставлена задача разработать программное средство, которое будет выполнять сортировку больших объемов текстовых данных, и выполнять поиск необходимой информации в массивах данных.

2. Основные сведения про используемые алгоритмы

сортировки и поиска

Сортировка выбором:

Сортировка выбором начинается с поиска наименьшего элемента в списке и обмена его с первым элементом (таким образом, наименьший элемент помещается в окончательную позицию в отсортированном списке). Затем сканируется список, начиная со второго элемента, в поисках наименьшего среди оставшихся п — 1 элементов и найденный наименьший элемент обменивается со вторым, т. е. второй наименьший элемент помещается в окончательную позицию в отсортированном списке.

В общем случае, при i-ом проходе по списку (0 i п — 2) алгоритм ищет наименьший элемент среди последних п — i элементов и обменивает его с Ai;

После выполнения п — 1 проходов список оказывается отсортирован. Вот псевдокод данного алгоритма, в котором для простоты предполагается, что список реализован в виде массива.

Алгоритм SelectionSort (A[0.n — 1])

// Сортировка массива методом выбора

// Входные данные: Массив А[0.n — 1] упорядочиваемых элементов

// Выходные данные: Массив A[0.n — 1], отсортированный

// в неубывающем порядке

for i = 0 to n — 2 do

min = i

for j = i + 1 to n — 1 do

if A[j] < A[min]

min = j

Обмен A[i] и A[min]

В качестве примера на рис. 2.1 приведена сортировка выбором следующего списка: 89, 45, 68, 90, 29, 34, 17.

Рис. 2.1. Сортировка выбором списка 89, 45, 68, 90, 29, 34, 17

Пузырьковая сортировка:

Суть метода пузырьковой сортировки состоит в сравнении соседних элементов и их обмене, если они находятся не в надлежащем порядке. Неоднократное выполнение этих действий заставляем наибольший элемент «всплывать» к концу списка. Следующий проход приведет к всплыванию второго наибольшего элемента, и так до тех пор, пока после п — 1 итерации список не будет полностью отсортирован.

Ниже приведен псевдокод данного алгоритма.

Алгоритм BubbleSort (A[0.n — 1])

// Сортировка массива пузырьковой сортировкой

// Входные данные: Массив А[0.n — 1] упорядочиваемых элементов

// Выходные данные: Массив A[0.n — 1], отсортированный

// в неубывающем порядке

for i = 0 to n — 2 do

for j = 0 + 1 to n — 2 — i do

if A[j + 1] < A[j]

Обмен A[j] и A[j + 1]

Применение описываемого алгоритма к списку 89, 45, 68, 90, 29, 34, 17 показано на рис. 2.2.

Рис. 2.2. Два первых прохода пузырьковой сортировки списка 89, 45, 68, 90, 29, 34, 17

Сортировка вставкой:

Рассмотрим применение метода уменьшения на единицу к сортировке массива А[0.n-1]. Следуя идее метода, полагаем, что задача меньшего размера, а именно сортировка массива А[0.n-2], уже решена и имеется отсортированный массив размером n-1: А[0] … А[n-2]. Каким образом воспользоваться этим решением задачи меньшего размера для получения решения исходной задачи, учитывающей наличие элемента А[n-1]? Очевидно, все, что необходимо, — это найти нужную позицию среди отсортированных элементов и вставить туда элемент А[n — 1].

Для этого используется следующий способ: сканируется отсортированный подмассив слева направо, пока не достигается первый элемент, больший или равный А[n-1], и после этого осуществляется вставка непосредственно перед найденным элементом.

Хотя сортировка вставкой основана на рекурсивном подходе, более эффективной будет ее реализация снизу вверх, т. е. итеративная. Элемент А[i] (начиная с элемента А[1] и заканчивая А[n-1]) вставляется в соответствующее место среди первых i элементов массива (которые к этому моменту уже отсортированы). Однако в отличие от сортировки выбором элемент в общем случае вставляется не в окончательную позицию, которую он будет занимать в полностью отсортированном массиве.

Ниже приведен псевдокод данного алгоритма.

Алгоритм Insertions’ort (А [0.n-1])

// Сортировка массива методом сортировки вставкой

// Входные данные: Массив А[0.n -1] из п упорядочиваемых

// элементов

// Выходные данные: Массив А[0.n — 1], отсортированный

// в неубывающем порядке

for i = 1 to n — 1 do

v = A[i]

j = i — 1

while j 0 and A[j] > v do

A[j + 1] = A[j]

j = j — 1

A[j + 1] = v

Работа алгоритма проиллюстрирована на рис. 2.3.

Рис. 2.3. Пример сортировки вставкой Сортировка подсчетом:

Идея данного метода состоит в том, чтобы подсчитать для каждого элемента сортируемого списка общее количество элементов, меньших данного, и занести полученный результат в таблицу. Полученные числа указывают позиции элементов в отсортированном списке: например, если для некоторого элемента это количество равно 10, то он должен быть одиннадцатым (его индекс будет равен 10, если индексы начинаются с 0) в отсортированном массиве. Таким образом, можно отсортировать список, просто копируя его элементы в соответствующие позиции в новом, отсортированном списке. Такой алгоритм называется сортировкой подсчетом сравнений (comparison counting) (рис. 2.4).

Рис. 2.4. Пример сортировки подсчетом сравнений Псевдокод данного алгоритма.

Алгоритм ComparisonCountingSort (А [0.n — 1])

// Сортировка массива подсчетом сравнений

// Входные данные: Массив А[0.n — 1] упорядочиваемых значений

// Выходные данные: Массив S[0.n — 1] элементов А,

// отсортированных в неубывающем порядке

for i = 0 to n — 1 do

Count[i] = 0

for i = 0 to n — 2 do

for j = i + 1 to n — 1 do

if A[i] < A[j]

Count[j] = Count[j] + 1

Else

Count[i] = Count[i] + 1

for i = 0 to n — 1 do

S[Count[i]] = A[i]

Сортировка Шелла:

Сортировка Шелла — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской.

При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d=1 (то есть обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).

Работа алгоритма проиллюстрирована на рис. 2.5.

Рис. 2.5. Пример сортировки методом Шелла Псевдокод данного алгоритма.

Алгоритм ShellSort (А [0.n — 1])

// Сортировка массива подсчетом Шелла

// Входные данные: Массив А[0.n — 1] упорядочиваемых значений

// Выходные данные: Массив А[0.n — 1] элементов отсортированных

// в неубывающем порядке

d = n

while d > 1

d = d / 2

i = 0

while (j = i + d) < n

if А[i] > А[j]

обмен А[i] и А[j]

i++

Вызов метода сортировки пузырьком или сортировки вставками или сортировки выбором.

Последовательный поиск:

Этот алгоритм просто по очереди сравнивает элементы заданного списка с ключом поиска до тех пор, пока не будет найден элемент с указанным значением ключа (успешный поиск) или весь список будет проверен, но требуемый элемент не найден (неудачный поиск). Зачастую применяется простой дополнительный прием: если добавить ключ поиска в конец списка, то поиск обязательно будет успешным, следовательно, можно убрать проверку завершения списка в каждой итерации алгоритма. Далее приведен псевдокод такой улучшенной версии; предполагается, что входные данные имеют вид массива.

Алгоритм SequentialSearch2 (А[0.n], К)

// Алгоритм реализует последовательный поиск с использованием

// ключа поиска в качестве ограничителя

// Входные данные: Массив, А из п элементов и ключ поиска К

// Выходные данные: Позиция первого элемента массива A[0.n — 1],

// значение которого совпадает с К; если элемент не найден,

// возвращается значение -1

А[п] = К

i = 0

while А[i] K

i = i + 1

if i < п

return i

else

return -1

Если исходный список отсортирован, можно воспользоваться еще одним усовершенствованием: поиск в таком списке можно прекращать, как только встретится элемент, не меньший ключа поиска.

Бинарный поиск:

Бинарный поиск представляет собой в высшей степени эффективный алгоритм для поиска в отсортированном массиве. Он работает путем сравнения искомого ключа К со средним элементом массива А[m]. Если они равны, алгоритм прекращает работу. В противном случае та же операция рекурсивно повторяется для первой половины массива, если К < А[m], и для второй, если К > А [m].

В качестве примера найдем ключ К = 70, применяя алгоритм бинарного поиска к массиву. Пример показан на рисунке 2.6

алгоритм сортировка программирование поиск Рис. 2.6. Пример бинарного поиска Хотя ясно, что бинарный поиск основан на рекурсии, его очень легко реализовать как нерекурсивный алгоритм. Вот псевдокод нерекурсивной версии АЛГОРИТМ Binary Search (А[0.п — 1], К)

// Реализует нерекурсивный бинарный поиск

// Входные данные: Массив А[0.п — 1], отсортированный

// в возрастающем порядке, и искомый ключ К

// Выходные данные: Индекс элемента массива, равного К,

// или -1, если такого элемента нет

l = 0;

r = n — 1

while l r do

т = ;

if К = А[т]

return m

else if К < А[т]

r = m — 1

else

r = m + 1

return -1

Стандартный способ анализа эффективности бинарного поиска состоит в подсчете количества сравнений искомого ключа с элементами массива. Кроме того, из соображений простоты, мы будем считать, что используются тройные сравнения, т. е. что одно сравнение К и А[m] позволяет определить, меньше ли К, больше или равно значению А[m].

Сколько же сравнений должен выполнить алгоритм при поиске в массиве из n элементов? Ответ, очевидно, зависит не только от n, но и от конкретного экземпляра задачи. Найдем количество сравнений в наихудшем случае. В наихудший случай входят все массивы, которые не содержат искомого ключа (кроме них в этот разряд попадают и некоторые массивы, поиск в которых завершается успешно).

В частности, потребуется не более чем 10 тройных сравнений для поиска элемента с заданным значением (или выяснения того, что такой элемент отсутствует) в массиве из 1000 элементов, и не более 20 сравнений для поиска в массиве в миллион элементов.

Поиск подстроки:

Описание задачи поиска подстроки: дана символьная строка длиной п, называющаяся текстом, и строка длиной т (т п). именуемая шаблоном (pattern); требуется найти в тексте подстроку, соответствующую шаблону. Говоря точнее, нужно определить i — индекс крайнего слева символа первой соответствующей шаблону подстроки в тексте.

Если требуется найти все такие подстроки, алгоритм поиска подстроки может просто продолжать работу до полной проверки текста.

Алгоритм, основанный на грубой силе, очевиден: шаблон выравнивается с началом текста и по очереди сравниваются соответствующие пары символов слева направо до тех пор либо символы во всех т парах будут равны (в этом случае алгоритм может прекращать работу), либо не встречается пара разных символов. В последнем случае шаблон смещается на одну позицию вправо, и сравнение символов продолжается, начиная с первого символа шаблона и символа в соответствующей позиции в тексте. Заметим, что последняя позиция в тексте, которая еще может выступать в роли начала искомой подстроки — п — т (если позиции в тексте индексируются значениями от 0 до п — 1). После этой позиции в тексте остается слишком мало символов, чтобы они могли соответствовать шаблону. Следовательно, по достижении указанной позиции алгоритм не должен делать никаких сравнений.

Алгоритм BruteForceStriny Match (Т[0.п — 1], Р[0.т — 1])

// Алгоритм реализует поиск подстроки методом грубой силы

// Входные данные: массив Т[0.п — 1] из п символов, представляющий

// текст; массив P[0.m — 1] из т символов, представляющий шаблон

// Выходные данные: позиция первого символа в тексте, с которой

// начинается первая искомая подстрока, соответствующая шаблону;

// если подстрока не найдена, возвращается — 1

for i = 0 to п — т do

j = 0

while j < т and P[j] = Т[i + j] do

j = j + 1

if j = m

return i

return — 1

Работа алгоритма проиллюстрирована на рис. 2.7.

Рис. 2.7. Пример поиска подстроки с применением грубой силы Обратите внимание, что в данном примере алгоритм практически всегда смещает шаблон после первого же сравнения символа. Однако наихудший случай намного неприятнее: алгоритм может выполнять все m сравнений перед сдвигом шаблона, и это происходит в каждой из п — m + 1 попыток. Однако в случае типичного поиска слова в тексте на естественном языке можно ожидать, что большинство сдвигов будет выполняться после небольшого количества сравнений (взгляните на приведенный пример). Таким образом, эффективность в среднем случае должна быть существенно выше эффективности в худшем случае.

3. Разработка программного средства и руководство пользователя

3.1 Описание процесса создания программного средства Программа будет разрабатываться при помощи программного средства Borland Delphi 7.

Программа будет состоять из одной формы, на которой и будут производиться все действия.

Для удобства работы форма будет разделена на три области (для ввода данных, для вызова действий и для вывода результатов). Для визуального разделения областей используем компоненты TGroupBox.

Для ввода исходных данных и вывода результатов используем компоненты ТMemo и компонент TLabeledEdit.

Для выбора действий используем компоненты TButton и TCheckBox.

Внешний вид формы на этапе разработки показан на рис. 3.1. (Приложение 2).

Для массива, с которым будем работать, используем тип данных String — это позволить осуществлять сортировку и поиск строк.

Изначально все кнопки, кроме кнопки «Принять данные», переключатель для показа времени сортировки и поле для ввода шаблона поиска должны быть недоступны. Для этого на этапе разработки установим им свойство Enabled в значение false.

Для того чтобы эти компоненты стали доступны пользователь должен ввести в левую область данные, с которыми должна работать программа и нажать кнопку «Принять данные».

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

if Memo1. Text <> '' then

begin

…

end

else

MessageDlg ('Не введен список!', mtWarning, [mbOK], 0);

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

for i := 1 to Memo1.Lines.Count do

mas[i] := Memo1. Lines[i-1];

kol := Memo1.Lines.Count;

Button2.Enabled := true;

Button3.Enabled := true;

Button4.Enabled := true;

Button5.Enabled := true;

Button6.Enabled := true;

Button7.Enabled := true;

Button8.Enabled := true;

Button9.Enabled := true;

LE_Shablon.Enabled := true;

CheckBox1.Enabled := true;

Обработчики всех кнопок, предназначенных для сортировки, имеют практически идентичную структуру, которая отличается только реализацией алгоритма сортировки. Типичная структура обработчика приведена ниже:

QueryPerformanceFrequency (iCounterPerSec);

QueryPerformanceCounter (T1);

// реализация используемого алгоритма сортировки

QueryPerformanceCounter (T2);

if CheckBox1. Checked = true then

MessageDlg ('Время сортировки ' + FormatFloat ('0.0', (T2 — T1) / iCounterPerSec) + ' сек.', mtInformation, [mbOK], 0);

Memo2.Lines.Clear;

for i := 1 to kol do

Memo2.Lines.Add (mas[i]);

В программе предусмотрена возможность отображать время, за которое была выполнена сортировка. Для этого предназначены функции QueryPerformanceFrequency и QueryPerformanceCounter и функция MessageDlg, которая выводит эти данные на экран (если пользователь поставил соответствующую галочку).

Приведем код одного из используемых алгоритмов сортировки (сортировка вставками):

for i:=1 to kol do

begin

temp := mas[i];

j := i-1;

while (j >= 0) and (mas[j] > temp) do

begin

mas[j+1] := mas[j];

j := j-1

end;

mas[j+1] := temp;

end;

Структура обработчиков на каждый из алгоритмов поиска отлична друг от друга, поэтому рассмотрим их более подробно.

При последовательном поиске используются данные из левой части формы, предусмотрены проверки на наличие списка и на наличие ключа поиска:

if Memo1. Text <> '' then

…

else

MessageDlg ('Не введен список!', mtWarning, [mbOK], 0);

if LE_Shablon.Text = '' then

MessageDlg ('Не задан шаблон поиска', mtWarning, [mbOK], 0)

Затем считывается шаблон и производится поиск. Для этого используется следующий код:

str := LE_Shablon.Text;

for i := 1 to kol do

if temp[i] = str then

break;

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

if i <= kol then

begin

Memo1.SelStart := Memo1. Perform (EM_LINEINDEX, i-1, 0);

Memo1.SelLength := Length (Memo1.Lines[i-1]);

Memo1.SetFocus;

end

else

MessageDlg ('Шаблон поиска не найден!', mtWarning,[mbOK], 0);

При бинарном поиске вначале производится проверка на отсортированность списка данных. Если список не отсортирован, то применения метода невозможно и производится вывод соответствующего сообщения. Это проиллюстрировано следующим фрагментом кода:

flag := true;

for i := 1 to kol-1 do

begin

if mas[i] > mas[i+1] then

begin

flag := false;

break;

end;

end;

if flag then

…

else

MessageDlg ('Данные не отсортированы! Поиск невозможен!', mtWarning, [mbOK], 0);

Если же список отсортирован, то производится поиск:

str := LE_Shablon.Text;

low := 1;

high := kol;

found := false;

while (low <= high) and (not found) do

begin

mid := (low+high) div 2;

if str < mas[mid] then

high := mid-1

else if str > mas[mid] then

low := mid+1

else

found:=true;

end;

Для определения «удачности» поиска используется булева переменная found. Если она равна true — значит поиск удачен. В таком случае найденная строка выделяется в правой части формы, иначе выводится соответствующее сообщение:

if found then

begin

Memo2.SelStart := Memo2. Perform (EM_LINEINDEX, mid-1, 0);

Memo2.SelLength := Length (Memo2.Lines[mid-1]);

Memo2.SetFocus;

end

else

MessageDlg ('Шаблон поиска не найден!', mtWarning,[mbOK], 0);

При поиске подстрок аналогично производится проверка на наличие списка данных и ключа поиска. Затем выполняется сам поиск:

str := LE_Shablon.Text;

m := Length (str);

for k := 1 to kol do

begin

n := Length (temp[k]);

for i := 1 to n-m+1 do

begin

j := 0;

while (j < m) and (str[j+1] = temp[k, i+j]) do

inc (j);

if j = m then

begin

flag := true;

break;

end;

end;

if flag then

break;

Для определения «удачности» поиска используется булева переменная flag. Если она равна true — значит поиск удачен. В таком случае найденная строка выделяется в правой части формы, иначе выводится соответствующее сообщение:

if flag then

begin

Memo1.SelStart := Memo1. Perform (EM_LINEINDEX, k-1,0)+i-1;

Memo1.SelLength := m;

Memo1.SetFocus;

end

else

MessageDlg ('Шаблон поиска не найден!', mtWarning,[mbOK], 0);

3.2 Руководство пользователя После запуска программы на исполнение в экране появляется главная форма, которая показана на рис. 3.2. (Приложение 3).

Данная форма состоит из трех частей:

— область для ввода данных, предназначенных для сортировки или поиска (расположена слева),

— область, на которой размещены все кнопки, которые отвечают за выполнение определенных действий в программе (расположена посередине),

— область для вывода результатов сортировки или поиска (расположена справа).

Область с кнопками в свою очередь состоит из трех основных элементов:

— кнопки «Принять данные»,

— панели «Сортировка данных»,

— панели «Поиск данных».

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

Данные можно вводить непосредственно в данное поле вручную или вставить в поле скопированные при помощи буфера обмена данные из произвольной программы.

При запуске программы доступной является только одна кнопка — «Принять данные». Все остальные кнопки и переключатель «Показать время сортировки» изначально недоступны.

После ввода данных необходимо нажать кнопку «Принять данные». Если при этом пользователь забыл ввести данные в левое поле, то программа выдаст предупреждение, показанное на рис 3.3.

Рис. 3.3. Предупреждение об отсутствии данных Если данные были введены, то программа их принимает и происходит разблокировка всех остальных кнопок и переключателя «Показать время сортировки». Это показано на рис. 3.4.

После этого возможно выполнять процедуры поиска данных и процедуры сортировки данных.

Начнем с сортировки. Программа предоставляет возможность использовать пять алгоритмов сортировки:

§ сортировку выбором;

§ сортировку пузырьком;

§ сортировку вставками;

§ сортировку подсчетом;

§ сортировку Шелла.

Рис. 3.4. Главная форма после ввода данных При сортировке данных существует возможность смотреть, сколько времени заняла эта процедура у программы. Для этого предназначен переключателя «Показать время сортировки», которой размещается в нижней части панели «Сортировка данных». Изначально он выключен. При его включении программа, независимо от выбранного способа сортировки, будет по окончанию сортировки выводить сообщение с указанием количество времени, которое ушло на сортировку.

Пример такого сообщения показан на рис. 3.5.

Рис. 3.5. Сообщение со временем сортировки Результат сортировки выводится в правую часть формы, как это показано на рис. 3.6.

Рис. 3.6. Главная форма с результатами сортировки При необходимости можно ввести новые данные и выполнить сортировки для них.

Если у пользователя есть желание, он может сравнить используемые в программе алгоритмы сортировки по быстродействию. Для этого ему надо несколько раз отсортировать одни и те же данные, используя разные алгоритмы. Однако следует помнить, что перед вторым и более использованием сортировки для одних и тех же данных, необходимо нажимать кнопку «Принять данные».

Это необходимо для того, чтоб второй, третий и т. д. разу алгоритм начинал работы со списком, который имеет такой же вид, как и данные введенные в левой части формы. Если этого не делать, то при втором, третьем и т. д. вызове сортировки программа будет работать с данными, которые уже были отсортированы предыдущим алгоритмом, что не позволит корректно сравнить алгоритмы между собой, так как они будут находиться в неравных условиях — первый алгоритм будет иметь дело с неотсортированным списком, а все остальные — с уже отсортированным.

Теперь рассмотрим поиск данных.

Программа предоставляет возможность использовать три алгоритма поиска:

· последовательный поиск;

· бинарный поиск;

· поиск подстроки методом грубой силы.

Способ работы с методами поиска (в отличие от сортировки) различен, поэтому остановимся на каждом более подробно.

1. Последовательный поиск.

Для его использования необходимо ввести в поле «Шаблон поиска» искомую запись и нажать кнопку «Последовательный поиск».

Если пользователь забыл ввести шаблон поиска, то будет выдано соответствующее сообщение (рис. 3.7.)

Если шаблон поиска был введен, то будет произведен поиск. При этом возможно два варианта:

· поиск неудачен (шаблон не найден);

· поиск удачен (шаблон найден).

Рис. 3.7. Сообщение об отсутствии шаблона поиска В первом случае будет выдано соответствующее сообщение, которое показано на рис. 3.8.

Рис. 3.8. Сообщение об отсутствии искомого значения Во втором случае искомая строка будет выделена в левой части формы. Пример удачного поиска показан на рис. 3.9.

2. Бинарный поиск.

Для его использования необходимо ввести в поле «Шаблон поиска» искомую запись и нажать кнопку «Бинарный поиск».

Если пользователь забыл ввести шаблон поиска, то будет выдано соответствующее сообщение (рис. 3.7.)

Если шаблон поиска был введен, то будет произведен поиск.

Однако необходимо отметить, что бинарный поиск (в силу специфики алгоритма) работает только с предварительно отсортированными данными. Поэтому перед выполнением сортировки программа проверить отсортирован ли список, в котором предполагается проведение поиска.

Если в результате проверки окажется, что список не отсортирован, то об этом будет выдано соответствующее предупреждение, внешний вид которого показан на рисунке 3.10

Рис. 3.9. Результат удачного последовательного поиска Рис. 3.10. Сообщение о попытке бинарного поиска в неотсортированном списке Так же как и при последовательном поиске возможно два варианта:

§ поиск неудачен (шаблон не найден);

§ поиск удачен (шаблон найден).

В первом случае будет выдано соответствующее сообщение, которое показано на рис. 3.8.

Во втором случае искомая строка будет выделена в правой части формы. Пример удачного поиска показан на рис. 3.11.

Рис. 3.11. Результат удачного бинарного поиска

3. Поиск подстроки.

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

Для его использования необходимо ввести в поле «Шаблон поиска» искомую подстроку и нажать кнопку «Поиск подстроки».

Если пользователь забыл ввести шаблон поиска, то будет выдано соответствующее сообщение (рис. 3.7.)

Если шаблон поиска был введен, то будет произведен поиск.

Так же как и при рассмотренных вариантах поиска возможны два варианта:

— поиск неудачен (шаблон не найден),

— поиск удачен (шаблон найден).

В первом случае будет выдано соответствующее сообщение, которое показано на рис. 3.8.

Во втором случае искомая подстрока будет выделена в левой части формы. Пример удачного поиска показан на рис. 3.11.

Рис. 3.11. Результат удачного поиска подстроки

Заключение

В первой главе курсовой работы было произведено исследование предприятия и поставлено задание на разработку программы.

В качестве рассматриваемого предприятия было выбрано открытое акционерное общество «Комитекс».

Были рассмотрены следующие моменты:

1. История развития предприятия и основные этапы его развития.

2. Укрупненная структура предприятия (представительства).

3. Членство предприятия в различных ассоциациях.

4. Краской обзор используемых на предприятии технологий.

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

Во второй главе были изучены основные моменты, которые необходимы для решения данной задачи, а именно были рассмотрены части используемые алгоритмы сортировки данных и поиска.

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

· сортировка выбором;

· пузырьковая сортировка;

· сортировка вставкой;

· сортировка подсчетом;

· сортировка Шелла.

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

§ последовательный поиск;

§ бинарный поиск;

§ поиск подстроки методом грубой силы.

По каждому алгоритму были рассмотрены:

ь основная идея алгоритм;

ь суть алгоритма;

ь приведен псевдокод алгоритма;

ь рассмотрен пример работы алгоритма.

После рассмотрения этих вопросов можно было перейти непосредственно к написанию программы.

В качестве среды разработки программного продукта был была выбрана IDE (интегрированная среда разработки) Borland Delphi 7.

В третьей главе данной курсовой работы детально расписан процесс создания программного средства.

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

После этого было описана логика работы программы и приведены следующие фрагменты кода:

— проверка на наличие исходных данных;

— код для считывания данных в специальный массив и разблокировки элементов;

— обработчики кнопок, предназначенных для сортировки;

— код одного из используемых алгоритмов сортировки (сортировка вставками);

— обработчик кнопки для последовательного поиска;

— обработчик кнопки для бинарного поиска;

— обработчик кнопки для поиска подстрок.

Затем было создано руководство пользователя, которое предназначено для обучения пользователей работе с программой.

Необходимо заметить, что в данном руководстве описаны все функции программы и указан порядок действий пользователя при работе с ней.

При этом рассмотрены все возможные ошибочные действия пользователя.

Все поставленные в первом разделе задачи в процессе выполнения работы были выполнены.

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

1. Левитин Ананий. Алгоритмы: введение в разработку и анализ. :Пер. с англ. — М.: Издательский дом «Вильямс», 2006. — 576с.: ил.

2. Гудман С., Хидетниеми С.

Введение

в разработку и анализ алгоритмов. — М.: Мир, 1981.

3. Ахо А., Хлопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир. 1974.

4. Ахо A.B., Хопкрофт Д. Э., Ульман Д. Д. Структуры данных и алгоритмы. -М.: Вильяме, 2000. 384с.

5. Цейтлин Г. Е.

Введение

в алгоритмику. Киев: Сфера, 1998. 473с.

6. Кнут Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы. — М.: Мир, 1976.

7. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. — М.: Мир, 1978.

8. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989. — 360с.

9. Лорин Г. Сортировка и системы сортировки. М.: Наука, 1983. — 384с.

10. Цейтлин Г. Е. Алгоритмы адаптивной сортировки и их классификация. // Проблемы управления и информатики 1995, № 3. С. 95−103.

11. Макконнелл Дж. Анализ алгоритмов. Вводный курс. М.: Техносфера, 2002.-304с.

12. Архангельский А. Я. Object Pascal в Delphi. — М: ЗАО? Издательство БИНОМ, 2002.

13. Павловская Т. А. Паскаль. Программирование на языке высокого уровня: Учебник для вузов. — СПб.: Питер, 2007. — 393с.

14. М. В. Сухарев Основы Delphi. Профессиональный подход. — СПб.: Наука и Техника, 2004. 600c.

15. Н. Б. Культин Программирование в Turbo Pascal 7.0 и Delphi — СПб.: BHV — Санкт-Петербург 1998 — 240с.

16. Грызлов В. И., Грызлова Т. П. Турбо Паскаль 7.0 — М.: ДМК, 1998 — 400с.

17. Ж. Джонс, К. Жарроу Решение задач в системе TurboPascal. — М., Финансы и статистика 1991 — 714с.

18. Delphi 5. Руководство программиста. — М.: «Нолидж», 2001. — 880с

19. Архангельский А. Я. Delphi 7. Справочное пособие, — М: ЗАО? Издательство БИНОМ, 2003.

20. Культин Н. Б. Delphi 6 Программирование на Object Pascal — СПб: БХВ-Петербург 2001 — 528с: ил.

21. Архангельский А. Я. Приемы программирования в Delph. Версии 5−7. — М: ЗАО? Издательство БИНОМ?, 2003.

22. Фленов М. Е. Библия Delphi. — СПб.: БХВ-Петербург, 2004. — 880с.:

23. Гринзоу Лу. Философия программирования для Windows 95/NT. пер. с англ. — СПб.: Символ-плюс, 1997. — 640с.

24 Тейксейра C, Пачеко К Borland Delphi 6. Руководство разработчика.: Пер. с англ. — М.: Издательский дом «Вильямс», 2002. — 1120с.

Приложение 1

Текст программы

unit UnitMain;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, DateUtils, ExtCtrls;

type

TMainForm = class (TForm)

GroupBox3: TGroupBox;

Memo1: TMemo;

GroupBox4: TGroupBox;

Button1: TButton;

GroupBox1: TGroupBox;

Button2: TButton;

Button3: TButton;

Button4: TButton;

Button5: TButton;

Button6: TButton;

GroupBox2: TGroupBox;

Button7: TButton;

Button9: TButton;

Button8: TButton;

LE_Shablon: TLabeledEdit;

GroupBox5: TGroupBox;

Memo2: TMemo;

CheckBox1: TCheckBox;

procedure Button1Click (Sender: TObject);

procedure Button2Click (Sender: TObject);

procedure Button3Click (Sender: TObject);

procedure Button4Click (Sender: TObject);

procedure Button5Click (Sender: TObject);

procedure Button6Click (Sender: TObject);

procedure Button7Click (Sender: TObject);

procedure Button9Click (Sender: TObject);

procedure Button8Click (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

MainForm: TMainForm;

mas: array [0.1000] of String;

kol: integer;

iCounterPerSec: TLargeInteger;

T1, T2: TLargeInteger;

implementation

{$R *.dfm}

procedure TMainForm. Button1Click (Sender: TObject);

var

ttt, i: integer;

begin

if Memo1. Text <> '' then

begin

for i := 1 to Memo1.Lines.Count do

mas[i] := Memo1. Lines[i-1];

kol := Memo1.Lines.Count;

Button2.Enabled := true;

Button3.Enabled := true;

Button4.Enabled := true;

Button5.Enabled := true;

Button6.Enabled := true;

Button7.Enabled := true;

Button8.Enabled := true;

Button9.Enabled := true;

LE_Shablon.Enabled := true;

CheckBox1.Enabled := true;

end

else

MessageDlg ('Не введен список!', mtWarning, [mbOK], 0);

end;

procedure TMainForm. Button2Click (Sender: TObject);

var

i, j, min: integer;

temp: String;

begin

QueryPerformanceFrequency (iCounterPerSec);

QueryPerformanceCounter (T1);

for i := 1 to kol-1 do

begin

min := i;

for j := i+1 to kol do

if mas[j] < mas[min] then

min := j;

temp := mas[min];

mas[min] := mas[i];

mas[i] := temp;

end;

QueryPerformanceCounter (T2);

if CheckBox1. Checked = true then

MessageDlg ('Время сортировки ' + FormatFloat ('0.0', (T2 — T1) / iCounterPerSec) + ' сек.', mtInformation, [mbOK], 0);

Memo2.Lines.Clear;

for i := 1 to kol do

Memo2.Lines.Add (mas[i]);

end;

procedure TMainForm. Button3Click (Sender: TObject);

var

i, j, min: integer;

temp: String;

begin

QueryPerformanceFrequency (iCounterPerSec);

QueryPerformanceCounter (T1);

for i := 1 to kol-1 do

for j := 1 to kol-i do

if mas[j+1] < mas[j] then

begin

temp := mas[j];

mas[j] := mas[j+1];

mas[j+1] := temp;

end;

QueryPerformanceCounter (T2);

if CheckBox1. Checked = true then

MessageDlg ('Время сортировки ' + FormatFloat ('0.0', (T2 — T1) / iCounterPerSec) + ' сек.', mtInformation, [mbOK], 0);

Memo2.Lines.Clear;

for i := 1 to kol do

Memo2.Lines.Add (mas[i]);

end;

procedure TMainForm. Button4Click (Sender: TObject);

var

i, j, min: integer;

temp: String;

begin

QueryPerformanceFrequency (iCounterPerSec);

QueryPerformanceCounter (T1);

for i:=1 to kol do

begin

temp := mas[i];

j := i-1;

while (j >= 0) and (mas[j] > temp) do

begin

mas[j+1] := mas[j];

j := j-1

end;

mas[j+1] := temp;

end;

QueryPerformanceCounter (T2);

if CheckBox1. Checked = true then

MessageDlg ('Время сортировки ' + FormatFloat ('0.0', (T2 — T1) / iCounterPerSec) + ' сек.', mtInformation, [mbOK], 0);

Memo2.Lines.Clear;

for i := 1 to kol do

Memo2.Lines.Add (mas[i]);

end;

procedure TMainForm. Button5Click (Sender: TObject);

var

i, j, min: integer;

temp: array [0.10 000] of String;

count: array [0.10 000] of integer;

begin

QueryPerformanceFrequency (iCounterPerSec);

QueryPerformanceCounter (T1);

for i := 1 to kol do

count[i] := 0;

for i := 1 to kol-1 do

begin

for j := i+1 to kol do

if mas[i] < mas[j] then

inc (count[j])

else

inc (count[i]);

end;

for i := 1 to kol do

temp[count[i]] := mas[i];

QueryPerformanceCounter (T2);

if CheckBox1. Checked = true then

MessageDlg ('Время сортировки ' + FormatFloat ('0.0', (T2 — T1) / iCounterPerSec) + ' сек.', mtInformation, [mbOK], 0);

Memo2.Lines.Clear;

for i := 1 to kol do

begin

mas[i] := temp[i-1];

Memo2.Lines.Add (mas[i]);

end;

end;

procedure TMainForm. Button6Click (Sender: TObject);

var

d, i, j: integer;

h: word;

temp: String;

begin

QueryPerformanceFrequency (iCounterPerSec);

QueryPerformanceCounter (T1);

d := kol div 2;

while d > 0 do

begin

for i := 0 to kol-d do

begin

j := i;

while (j >= 0) and (mas[j] > mas[j+d]) do

begin

temp := mas[j];

mas[j]:= mas[j+d];

mas[j+d] := temp;

j:=j-d;

end;

end;

d := d div 2;

end;

QueryPerformanceCounter (T2);

if CheckBox1. Checked = true then

MessageDlg ('Время сортировки ' + FormatFloat ('0.0', (T2 — T1) / iCounterPerSec) + ' сек.', mtInformation, [mbOK], 0);

Memo2.Lines.Clear;

for i := 1 to kol do

Memo2.Lines.Add (mas[i]);

end;

procedure TMainForm. Button7Click (Sender: TObject);

var

str: String;

i, line: integer;

temp: array [0.10 000] of String;

begin

if Memo1. Text <> '' then

begin

for i := 1 to Memo1.Lines.Count do

temp[i] := Memo1. Lines[i-1];

kol := Memo1.Lines.Count;

end

else

MessageDlg ('Не введен список!', mtWarning, [mbOK], 0);

if LE_Shablon.Text = '' then

MessageDlg ('Не задан шаблон поиска', mtWarning, [mbOK], 0)

else

begin

str := LE_Shablon.Text;

for i := 1 to kol do

if temp[i] = str then

break;

if i <= kol then

begin

Memo1.SelStart := Memo1. Perform (EM_LINEINDEX, i-1, 0);

Memo1.SelLength := Length (Memo1.Lines[i-1]);

Memo1.SetFocus;

end

else

MessageDlg ('Шаблон поиска не найден!', mtWarning, [mbOK], 0);

end;

end;

procedure TMainForm. Button9Click (Sender: TObject);

var

low, high, mid, i: integer;

found, flag: boolean;

str: String;

begin

//проверка на отсортированность.

flag := true;

for i := 1 to kol-1 do

begin

if mas[i] > mas[i+1] then

begin

flag := false;

break;

end;

end;

if flag then

begin

if LE_Shablon.Text = '' then

MessageDlg ('Не задан шаблон поиска', mtWarning, [mbOK], 0)

else

begin

str := LE_Shablon.Text;

low := 1;

high := kol;

found := false;

while (low <= high) and (not found) do

begin

mid := (low+high) div 2;

if str < mas[mid] then

high := mid-1

else if str > mas[mid] then

low := mid+1

else

found:=true;

end;

if found then

begin

Memo2.SelStart := Memo2. Perform (EM_LINEINDEX, mid-1, 0);

Memo2.SelLength := Length (Memo2.Lines[mid-1]);

Memo2.SetFocus;

end

else

MessageDlg ('Шаблон поиска не найден!', mtWarning, [mbOK], 0);

end;

end

else

MessageDlg ('Данные не отсортированы! Поиск невозможен!', mtWarning, [mbOK], 0);

end;

procedure TMainForm. Button8Click (Sender: TObject);

var

str: String;

i, j, k, m, n, nom: integer;

temp: array [0.10 000] of String;

flag: boolean;

begin

flag := false;

if Memo1. Text <> '' then

begin

for i := 1 to Memo1.Lines.Count do

temp[i] := Memo1. Lines[i-1];

kol := Memo1.Lines.Count;

end

else

MessageDlg ('Не введен список!', mtWarning, [mbOK], 0);

if LE_Shablon.Text = '' then

MessageDlg ('Не задан шаблон поиска', mtWarning, [mbOK], 0)

Else

begin

str := LE_Shablon.Text;

m := Length (str);

for k := 1 to kol do

begin

n := Length (temp[k]);

for i := 1 to n-m+1 do

begin

j := 0;

while (j < m) and (str[j+1] = temp[k, i+j]) do

inc (j);

if j = m then

begin

flag := true;

break;

end;

end;

if flag then

break;

end;

if flag then

begin

Memo1.SelStart := Memo1. Perform (EM_LINEINDEX, k-1, 0) + i-1;

Memo1.SelLength := m;

Memo1.SetFocus;

end

else

MessageDlg ('Шаблон поиска не найден!', mtWarning, [mbOK], 0);

end;

end;

end.

Приложение 2

Сортировка и поиск данных Рис. 3.1. Внешний вид формы на этапе разработки Приложение 3

Сортировка и поиск данных Рис. 3.2. Главная форма программы