Разработка программы сортировки данных на языке Turbo Pascal

Анализ эффективности методов сортировки данных в языке Turbo Pascal. Разработка эскизного и технического проекта программы. Сортировка без и с использованием дополнительной памяти, за исключением небольшого стека (массива). Сортировка связанных списков.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 23.05.2012
Размер файла 359,0 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Новгородский филиал

Курсовая работа

Программирование на языке высокого уровня

Орлов Сергей Валерьевич

Содержание

  • Введение
  • 1. Разработка эскизного и технического проекта программы (ГОСТ 19.404-79)
  • 1.1 Задание
  • 1.2 Назначение и область применения
  • 1.3 Технические характеристики
  • 2. Разработка рабочего проекта
  • 2.1 Понятие сортировки
  • 2.2 Критерии оценки алгоритмов сортировки
  • 2.3 Постановка задачи сортировки и методы её решения
  • 2.4 Сортировка пузырьковым методом
  • 2.5 Сортировка выбором
  • 2.6 Сортировка вставкой
  • 2.7 Сортировка Шелла
  • 3. Внедрение
  • 3.1 Интерфейс программного продукта
  • 3.2 Текст программы
  • Заключение
  • Глоссарий
  • Список использованных источников

Введение

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

Однако верно и обратное. Сколь бы хорошим и эффективным ни был выбранный вами алгоритм, но если в качестве подзадачи он использует "плохую" сортировку, то вся работа по его оптимизации оказывается бесполезной. Неудачно реализованная сортировка входных данных способна заметно понизить эффективность алгоритма в целом. В курсовой работе наша речь будет идти об эффективности различных методов сортировки данных в языке Turbo Pascal.

Объект и предмет исследования - методы сортировки данных, используемые в языке Turbo Pascal.

Целью данного исследования является анализ эффективности различных методов сортировки данных в языке Turbo Pascal.

Вообще говоря, методы сортировки делятся на три типа:

1. методы сортировки, которые сортируют без использования дополнительной памяти, за исключением, возможно, небольшого стека и/или массива;

2. методы, которые используют для сортировки связанные списки и поэтому используют N дополнительных указателей хранящихся в памяти;

3. а также методы, которые нуждаются в дополнительной памяти для хранения копии сортируемого файла.

1. Разработка эскизного и технического проекта программы (ГОСТ 19.404-79)

1.1 Задание

Тема:

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

Условие задачи:

Разработать проект, который позволит сортировать заданный линейный массив целых чисел различными методами, например, методом линейной сортировки, пузырька, Шелла и др. Предусмотреть использование не менее трех методов.

1.2 Назначение и область применения

В данном задании необходимо разработать вычислительную программу, представляющую собой проект для осуществления сортировки различными методами, не менее трех. Область применения: сортировка чисел. Поскольку ставится задача разработать приложение под Windows, то использоваться программа может только под управлением Windows 9х - Windows 7.

1.3 Технические характеристики

При создании данной курсовой работы выбран язык программирования Turbo Pascal - очень гибкий и развитый в отношении типов данных.

Паскамль (Pascal) - язык программирования общего назначения. Один из наиболее известных языков программирования, широко применяется в промышленном программировании, обучении программированию в высшей школе, является базой для большого числа других языков. Был создан Николаусом Виртом в 1970, после его участия в работе комитета разработки стандарта языка Алгол-68.

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

Наиболее известной реализацией Паскаля является система Turbo Pascal (выросшая затем в Borland Pascal и далее в Delphi) фирмы Borland, в которой язык был значительно расширен, были устранены некоторые недостатки языка, добавлены новые возможности. Язык стал богаче, но в отсутствие отраслевой стандартизации, потерял переносимость и общность (до появления в 1998 году Kylix - Delphi для Linux, продукты Borland работали только на платформе DOS/Windows, в настоящее время Kylix фактически заморожена).

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

компьютер на базе процессора Pentium 100 (или выше)

жесткий диск объемом 500 Мб (и выше)

объем оперативной памяти не менее 8 Мб

операционная система Windows 95 и выше, 32 бита.

2. Разработка рабочего проекта

2.1 Понятие сортировки

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

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

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

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

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

программа сортировка turbo pascal

2.2 Критерии оценки алгоритмов сортировки

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

1) с какой средней скоростью этот алгоритм сортирует информацию?;

2) какова скорость для лучшего случая и для худшего случая?;

3) поведение алгоритма является естественным или является не естественным?;

4) выполняется ли перестановка элементов для одинаковых ключей?

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

Время работы алгоритма для лучшего и худшего случаев важно учитывать, когда ожидается их частое появление. Часто сортировка имеет хорошую среднюю скорость, но очень плохую скорость для худшего случая, и наоборот. Считается поведение алгоритма сортировки естественным, если время сортировки наименьшее при упорядоченном списке элементов, время сортировки увеличивается при менее упорядоченном списке элементов и время сортировки становится наихудшим, когда список элементов упорядочен в обратном порядке.

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

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

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

2.3 Постановка задачи сортировки и методы её решения

Задачу сортировки данных можно сформулировать для информационной совокупности самой различной природы - для числовой информации, для слов и символов текста. Для этого, требуется определить понятие порядка для элементов массива, определить понятия "больше" и "меньше" для каждой пары элементов. Отсортировать последовательность чисел можно точно таким же способом, как и последовательность строк текста. Необходимо только определить какой из элементов пары "больше" другого.

Более важным для выбора алгоритма является местоположение данных - в оперативной памяти компьютера или на внешнем устройстве.

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

Различают два вида сортировки данных:

сортировка данных, расположенных в оперативной памяти компьютера (внутренняя сортировка);

сортировка данных, расположенных на внешних запоминающих устройствах (внешняя сортировка).

Сформулируем постановку задачи сортировки данных для внутренней сортировки одномерного числового массива по возрастанию.

Имеется одномерный массив чисел, состоящий из n элементов: X [n]. Переставить элементы массива так, чтобы их значения располагались в порядке возрастания. Другими словами, для любой пары элементов X [i] и X [i+1] выполняется неравенство вида:

X [i] <= X [i+1].

В этой задаче однозначно определяется структура данных для внутренней сортировки (одномерный массив) и порядок упорядочения элементов. Ключом для определения порядка элементов является само числовое значение элемента массива. Результатом решения задачи должна быть программа сортировки массива одним или несколькими методами.

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

метод сортировки обменами ("пузырьковая" сортировка);

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

метод сортировки выбором;

метод Шелла.

2.4 Сортировка пузырьковым методом

Наиболее известной (и наиболее "бесславной") является сортировка пузырьковым методом. Ее популярность объясняется запоминающимся названием и простотой алгоритма. Однако, эта сортировка является одной из самых худших среди всех когда-либо придуманных сортировок. Метод основан на том, что в процессе исполнения алгоритма более "легкие" элементы массива постепенно "всплывают". Особенностью данного метода является сравнение не каждого элемента со всеми, а сравнение в парах соседних элементов. Алгоритм пузырьковой сортировки по убыванию состоит в последовательных просмотрах снизу вверх (от начала к концу) массива М. Если соседние элементы таковы, что выполняется условие, согласно которому элемент справа больше элемента слева, то выполняется обмен значениями этих элементов.

Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень. Ниже показана самая простая форма программы сортировки методом пузырька:

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

procedure Bubble (var item: DataArray; count: integer);

var

i,j: integer;

x: DataItem;

begin

for i: = 2 to count do

begin

for j: = count downto i do

if item [j-1] >item [j] then

begin

x: = item [j-1];

item [j-1]: = item [j];

item [j]: = x;

end;

end;

end; {конец сортировки пузырьковым методом}

В этом случае данное "item" является массивом элементов "DataItem", который сортируется, а данное "count" содержит число элементов в массиве.

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

Для иллюстрации работы сортировки пузырьковым методом ниже даны результаты каждого этапа сортировки массива "dcab":

исходное положение: d c a b;

первый проход: a d c b;

второй проход: a b d c;

третий проход: a b c d.

При анализе всякой сортировки определяется число операций сравнения и обмена, выполняемых в лучшем, среднем и худшем случаях. Для сортировки пузырьковым методом число сравнений остается неизменным, поскольку два цикла всегда выполняются заданное число раз вне зависимости от упорядоченности исходного массива. Это означает, что при сортировке пузырьковым методом всегда выполняется 1/2 (n2-n) операций сравнения, где "n" задает число сортируемых элементов массива. Эта формула выводится на том основании, что внешний цикл сортировки пузырьковым методом выполняется n-1 раз, а внутренний цикл выполняется n/2 раз. Их перемножение даст указанную формулу. Число операций обмена будет нулевым для наилучшего случая, когда исходный массив уже является отсортированным. Число операций обмена для среднего случая будет равно 3/4 (n2-n), а для наихудшего случая будет равно 3/2 (n2-n) раз. Можно заметить, что по мере ухудшения упорядоченности исходного массива число неупорядоченных элементов приближается к числу сравнений (каждый неупорядоченный элемент требует три операции обмена). Сортировку пузырьковым методом называют квадратичным алгоритмом, поскольку время его выполнения пропорционально квадрату числа сортируемых элементов. Сортировка большого числа элементов пузырьковым методом потребует очень много времени, т.к. время выполнения сортировки находится в квадратичной зависимости от числа элементов массива. Например, если не учитывать время операций обмена, выполняемых для перестановки неупорядоченных элементов, то тогда при выполнении одной операции сравнения в течение 0,001 секунд сортировка десяти элементов займет 0,05 секунд, сортировка ста элементов займет 5 секунд, а сортировка 1000 элементов займет 500 секунд. Сортировка 100 000 элементов (такой размер имеет небольшой телефонный справочник) потребовала бы 5 000 000 секунд или около 1400 часов (т.е. два месяца непрерывной работы)! Сортировку пузырьковым методом можно в некоторой степени улучшить и тем самым немного улучшить ее временные характеристики. Можно, например, заметить, что сортировка пузырьковым методом обладает одной особенностью: расположенный не на своем месте в конце массива элемент (например, элемент "а" в массиве "dcab") достигает своего места за один проход, а элемент, расположенный в начале массива (например, элемент "d"), очень медленно достигает своего места. Необязательно все просмотры делать в одном направлении. Вместо этого всякий последующий просмотр можно делать в противоположном направлении. В этом случае сильно удаленные от своего места элементы будут быстро перемещаться в соответствующее место. Ниже показана улучшенная версия сортировки пузырьковым методом, получившая название "челночной сортировки" из-за соответствующего характера движений по массиву.

Хотя эта сортировка является улучшением пузырьковым методом, ее нельзя рекомендовать для использования, поскольку время выполнения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину.

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

При сортировке выбором выбирается элемент с наименьшим значением и делается его обмен с первым элементом массива. Затем находится элемент с наименьшим значением из оставшихся n-1 элементов и делается его обмен со вторым элементом и т.д. до обмена двух последних элементов. Например, если сортировку выбором применить для массива "bdac", то будут получены следующие проходы:

исходное положение: b d a c;

первый проход: a d b c;

второй проход: a b b c;

третий проход: a b c d.

К сожалению как и в сортировке пузырьковым методом внешний цикл выполняется n-1 раз, а внутренний цикл выполняется n/2 раз. Это значит, что число сравнений для сортировки выбором равно 1/2 (n2-n) и эта сортировка будет выполняться слишком медленно для большого числа элементов. Число операций обмена в наилучшем случае равно 3 (n-1), а в худшем случае равно n2/4+3 (n-1). В лучшем случае (когда исходный массив уже упорядочен) потребуется поменять местами только n-1элементов, а каждая операция обмена требует три операции пересылки.

{сортировка выбором}

procedure Selekt (var item: DataArray; count: integer);

var

i, j, k: integer;

x: DataItem;

begin

for i: = i to count-1 do

begin

k: = i;

x: = item [i];

for j: = i+1 to count do {найти элемент с наименьшим значением}

if item [j] <x then

begin

k: = j;

x: = item [j];

end;

item [k]: = item [i]; {обмен}

item [i]: = x;

end;

end; {конец сортировки выбором}

В среднем число операций обмена равно n (ln+y), где "y" является константой Эйлера, приблизительно равной 0,577216. Это значит, что несмотря на одинаковое число операций сравнений для сортировок пузырьковым методом и сортировок выбором, число операций обмена для среднего случая будет значительно меньшим для сортировки выбором.

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

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

Этот процесс повторяется до тех пор, пока все элементы не будут упорядочены. Например, для массива "dcab" сортировка вставкой будет проходить следующим образом:

исходное положение: d c a b;

первый проход: c d a b;

второй проход: a c d b;

третий проход: a b c d.

Ниже приводится алгоритм сортировки вставкой:

{ сортировка вставкой }

procedure Inser (var item: DataArray; count: integer);

var

i, l: integer;

x: DataItem;

begin

for i: = 2 to count do

begin

x: = item [i];

j: = i-1;

while (x<item [j]) and (j>0) do

begin

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

j: = j-1;

end;

item [j+1]: = x;

end;

end; { конец сортировки вставкой }

В отличие от сортировки пузырьковым методом и сортировки выбором число операций сравнения для сортировки вставкой зависит от исходной упорядоченности массива элементов. Если исходный массив уже упорядочен, то число операций сравнения равно n-1.

Если массив упорядочен в обратном порядке, то число операций сравнения равно 1/2 (n2 +n) - 1, давая в среднем значение 1/4 (n2+n-2).

Число операций обмена будет следующим:

для лучшего случая: 2 (n-1);

в среднем: 1/4 (n2+9n-10);

для худшего случая: 1/2 (n2+3n-4).

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

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

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

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

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

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

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

Сортировка Шелла получила свое название по имени ее создателя Д.Л. Шелла. Однако, это название можно считать удачным, так как выполняемые при сортировке действия напоминают укладывание морских ракушек друг на друга.

Общий метод, который использует сортировку вставкой, применяет принцип уменьшения расстояния между сравниваемыми элементами. Ниже показана схема выполнения сортировки Шелла для массива "f d a c b e". Сначала сортируются все элементы, которые смещены друг от друга на три позиции. Затем сортируются все элементы, которые смещены на две позиции. И, наконец, упорядочиваются все соседние элементы:

проход 1 f d a c b e

проход 2 c b a f d e

проход 3 a b c e d f

полученный результат a b c d e f

Алгоритм:

{ сортировка Шелла }

procedure Shell (var item: DataArray; count: integer);

const

t = 5;

var

i, j, k, s, m: integer;

h: array [1. t] of integer;

x: DataItem;

begin

h [1]: =9; h [2]: =5; h [3]: =3; h [4]: =2; h [5]: =1;

for m: = 1 to t do

begin

k: =h [m];

s: =-k;

for i: = k+1 to count do

begin

x: = item [i];

j: = i-k;

if s=0 then

begin

s: = - k;

s: = s+1;

item [s]: = x;

end;

while (x<item [j]) and (j<count) do

begin

item [j+k]: = item [j];

j: = j-k;

end;

item [j+k]: = x;

end;

end;

end; { конец сортировки Шелла }

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

Расстояния между сравниваемыми элементами могут изменяться по-разному. Обязательным является лишь то, что последний шаг должен равняться единице. Например, хорошие результаты дает последовательность шагов 9, 5, 3, 2, 1, которая использована в показанном выше примере. Следует избегать последовательностей степени двойки, которые, как показывают сложные математические выкладки, снижают эффективность алгоритма сортировки. (Однако, при использовании таких последовательностей шагов между сравниваемыми элементами эта сортировка будет по-прежнему работать правильно).

Внутренний цикл имеет два условия проверки. Условие "х<item [j] " необходимо для упорядочения элементов. Условия "j>0" и "j<=count" необходимы для того, чтобы предотвратить выход за пределы массива "item". Эта дополнительная проверка в некоторой степени ухудшает сортировку Шелла. Слегка измененные версии сортировки Шелла используют специальные управляющие элементы, которые не являются в действительности частью той информации, которая должна сортироваться. Управляющие элементы имеют граничные для массива данных значения, т.е. наименьшее и наибольшее значения. В этом случае не обязательно выполнять проверку на граничные значения. Однако, применение таких управляющих элементов требует специальных знаний о той информации, которая сортируется, и это снижает универсальность процедуры сортировки.

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

3. Внедрение

3.1 Интерфейс программного продукта

Запуск программы осуществляется при открытии файла в Приложении А МETHOD. exe.

Рис.3.1 Основное окно программы.

Далее нужно выбрать метод сортировки и нажать на соответствующую номеру клавишу на клавиатуре.

После этого программа выдаст исходный массив чисел (генерируется случайным выбором) и отсортированный массив (см. рис.3.2).

Чтобы протестировать еще один метод, достаточно нажать "Enter" и выбрать другой номер, соответствующий номеру метода сортировки.

Выход из программы осуществляется нажатием на "0".

Рис.3.2 Осуществление процесса сортировки

При разработке программы использовались следующие конструкции языка приведены ниже:

Условие:

if условие then begin

end

else

begin

цикл, с постоянным вхождением в цикл:

for переменная: = 1 to n do оператор;

end;

А так же конструкции вывода и чтения данных:

writeln (`информация'); // вывод данных

readln (переменная); // чтение данных

цикл с предусловием:

while (условие) do

begin

.

оператор;

.

end;

оператор выбора условию равенств значения переменной:

case переменная of

значение 1: оператор;

значение 2: оператор;

.

значение n: оператор;

При создание курсовой работы так же пользовалась функциями библиотеки crt.

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

Program Kurs;

uses crt;

const n = 10;

type Mas = array [1. n] of integer;

var

a: Mas;

K: char;

Procedure Menu;

begin

ClrScr;

WriteLn ('Выберете метод сортировки: ');

writeln ('1. Пузырьком');

writeln ('2. Выбором');

writeln ('3. Вставкой');

writeln ('4. Шелла');

writeln ('0. Выйти из программы');

writeln ('');

writeln ('Автор программы - Орлов Сергей Валерьевич');

Writeln;

Write (': > ');

end;

Procedure ZapMas;

var i: integer;

begin

ClrScr;

Randomize;

Writeln ('Исходный массив: ');

for i: =1 to n do

begin

a [i]: = random (20) - 10;

write (a [i]: 3,' ');

end;

Writeln;

end;

procedure Bubble (var item: Mas); {puzirkom}

var

i,j: integer;

x: integer;

begin

for i: = 2 to n do

begin

for j: = n downto i do

if item [j-1] >item [j] then

begin

x: = item [j-1];

item [j-1]: = item [j];

item [j]: = x;

end;

end;

end;

procedure Selekt (var item: Mas); { viborom}

var

i, j, k: integer;

x: integer;

begin

for i: = i to n-1 do

begin

k: = i;

x: = item [i];

for j: = i+1 to n do

if item [j] <x then

begin

k: = j;

x: = item [j];

end;

item [k]: = item [i];

item [i]: = x;

end;

end;

procedure Insert (var item: mas); {vstavkoy}

var

i, j: integer;

x: integer;

begin

for i: = 2 to n do

begin

x: = item [i];

j: = i-1;

while (x<item [j]) and (j>0) do

begin

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

j: = j-1;

end;

item [j+1]: = x;

end;

end;

procedure Shell;

Var

d, i, t: integer;

k: boolean;

begin

d: = N div 2;

while d>0 do

begin

k: = true;

while k do

begin

k: = false;

for i: = 1 to N-d do

begin

if A [i] >A [i+d] then

begin

t: = A [i];

A [i]: = A [i+d];

A [i+d]: = t;

k: = true;

end;

end;

end;

d: = d div 2;

end;

end;

procedure outmas;

var i: integer;

begin

Writeln ('Отсортированный: ');

for i: = 1 to n do

Write (a [i]: 3,' ');

Writeln;

end;

begin

Menu;

k: ='-';

Repeat

if keypressed then

begin

k: = readkey;

case k of

'1': begin

ZapMas;

Bubble (a);

OutMas;

Readln;

Menu;

end;

'2': begin

ZapMas;

Selekt (a);

OutMas;

Readln;

Menu;

end;

'3': begin

ZapMas; Insert (a);

OutMas;

Readln;

Menu;

end;

'4': begin

ZapMas;

Shell;

OutMas;

Readln;

Menu;

end;

end;

end;

until k='0';

end.

Заключение

В ходе курсовой работы была написана программа на языке Turbo Pascal, позволяющая сортировать линейный массив 4-мя методами:

1) Методом пузырька;

2) Методом вставок;

3) Методом выбора;

4) Методом Шелла.

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

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

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

И, наконец, некоторые из простых методов можно расширить до более хороших методов или использовать их для улучшения более сложных. Например, таким как метод Шелла.

Таким образом все поставленные задачи курсовой работы полностью выполнены.

Глоссарий

№ п/п

Понятие

Определение

Алгоритм сортировки

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

Внешняя сортировка

оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т.е. в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики.

Внутренняя сортировка

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

Время

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

Гетерогенный массив

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

Гипертекст

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

Динамический массив

массив, размер которого может меняться во время исполнения программы.

Естественность поведения

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

Индекс массива

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

Информационный массив

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

Сортировка простыми обменами, сортировка пузырьком

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

Сортировка простыми обменами, сортировка пузырьком

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

Сортировка слиянием

алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например - потоки) в определённом порядке.

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

алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами - это сортировка вставками с предварительными "грубыми" проходами.

Топологическая сортировка

упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин.

Список использованных источников

1. Джордейн, Р. Справочник программиста персональных компьютеров типа IBM PC, XT и AT: Пер. с англ. / Предисл. Н.В. Гайского, 2001 - 116с.

2. Довгаль, С.И. Персональные ЭВМ: Турбо-Паскаль V6.0, Объектное программирование, Локальные сети. (учебное пособие) /, С.И. Довгаль, Б.Ю. Литвинов, А.И. Сбитнев, - Киев: Информсистема сервис, 1993. - 210с.

3. Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching - 2-е изд. - М.: "Вильямс", 2007. - С.824. - ISBN 5-8459-0082-4.

4. М.М. Канаев, Т.З. Султанбекова, Программирование на языке TP: учебное пособие. Махачкала: ДГТУ, 2010 г.

5. Малыхина М.П. Программирование на языке высокого уровня Turbo Pascal. - издательство "СПб: БХВ-Петербург", 2006.

6. Меженный О. А.,Turbo Pascal Краткое руководство. Москва 2006 г.

7. Моргун Александр Николаевич Программирование на языке Паскаль (Pascal). Основы обработки структур данных. - М.: "Диалектика", 2005. - С.576. - ISBN 5-8459-0935-X.

8. Павловская, Т.А. Паскаль. Программирование на языке высокого уровня: Учебник для вузов/ Т.А. Павловская - СПб.: Питер, 2006. - 123 с.

9. Перминов, О.Н. Программирование на языке Паскаль. / О.Н. Перминов - М.: Радио и связь, 1988. - 156с.

10. Порублев Илья Николаевич, Ставровский Андрей Борисович Алгоритмы и программы. Решение олимпиадных задач - М.: "Вильямс", 2007. - С.480. - ISBN 978-5-8459-1244-2.

11. Прайс, Д. Программирование на языке Паскаль: Практическое руководство. Пер. с англ. /Д. Прайс - М.: Мир, 1987. - 232с.

12. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS - 2-е изд. - М.: "Вильямс", 2006. - С.1296. - ISBN 5-8459-0857-4.

13. Уоррен, Д. Алгоритмические трюки для программистов. Пер. с англ. [Текст] / Д. Уоррен, С. Генри - М.: Вильямс, 2007, - -288с,

14. Фролов В.В. Turbo Pascal 7.0 Учебный курс. Москва, 2011 г.

15. Эллилот Б. Коффман, Turbo Pascal (5-е издание). Москва 2010 г.

Размещено на Allbest.ru


Подобные документы

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.