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

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

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

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

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

Содержание

Введение

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.

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

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

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

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

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 Критерии оценки алгоритмов сортировки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

метод Шелла.

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

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

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

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

procedure Bubble (var item: DataArray; count: integer);,j: integer;: DataItem;i: = 2 to count doj: = count downto i doitem [j-1] >item [j] then: = item [j-1];[j-1]: = item [j];[j]: = x;;;

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элементов, а каждая операция обмена требует три операции пересылки.

{сортировка выбором}Selekt (var item: DataArray; count: integer);, j, k: integer;: DataItem;i: = i to count-1 do: = i;: = item [i];

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

if item [j] <x then: = j;: = item [j];;[k]: = item [i]; {обмен}

item [i]: = x;;; {конец сортировки выбором}

В среднем число операций обмена равно 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.

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

{ сортировка вставкой }Inser (var item: DataArray; count: integer);, l: integer;: DataItem;i: = 2 to count do: = item [i];: = i-1;(x<item [j]) and (j>0) do[j+1]: = item [j];: = j-1;;[j+1]: = x;

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

Алгоритм:

{ сортировка Шелла }Shell (var item: DataArray; count: integer);= 5;, j, k, s, m: integer;: array [1. t] of integer;: DataItem;[1]: =9; h [2]: =5; h [3]: =3; h [4]: =2; h [5]: =1;m: = 1 to t do: =h [m];: =-k;i: = k+1 to count do: = item [i];: = i-k;s=0 then: = - k;: = s+1;[s]: = x;;(x<item [j]) and (j<count) do[j+k]: = item [j];: = j-k;;[j+k]: = x;

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

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

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

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

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

3. Внедрение

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

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

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

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

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

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

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

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

Условие:условие then begin

…

else

цикл, с постоянным вхождением в цикл:переменная: = 1 to n do оператор;

…;

А так же конструкции вывода и чтения данных:(‘информация’); // вывод данных(переменная); // чтение данных

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

.

оператор;

.;

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

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

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

.

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

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

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

Program Kurs;crt;n = 10;Mas = array [1. n] of integer;: Mas;: char;Menu;;('Выберете метод сортировки: ');('1. Пузырьком');('2. Выбором');('3. Вставкой');('4. Шелла');('0. Выйти из программы');('');('Автор программы - Орлов Сергей Валерьевич');

Writeln;(': > ');;ZapMas;i: integer;;;('Исходный массив: ');i: =1 to n do[i]: = random (20) - 10;(a [i]: 3,' ');;;;Bubble (var item: Mas); {puzirkom},j: integer;: integer;i: = 2 to n doj: = n downto i doitem [j-1] >item [j] then: = item [j-1];[j-1]: = item [j];[j]: = x;;;;Selekt (var item: Mas); { viborom}, j, k: integer;: integer;i: = i to n-1 do: = i;: = item [i];j: = i+1 to n doitem [j] <x then: = j;: = item [j];;[k]: = item [i];[i]: = x;;;Insert (var item: mas); {vstavkoy}, j: integer;: integer;i: = 2 to n do: = item [i];: = i-1;(x<item [j]) and (j>0) do[j+1]: = item [j];: = j-1;;[j+1]: = x;;;Shell;, i, t: integer;: boolean;: = N div 2;d>0 do: = true;k do: = false;i: = 1 to N-d doA [i] >A [i+d] then: = A [i];[i]: = A [i+d];[i+d]: = t;: = true;;;;: = d div 2;;;outmas;i: integer;('Отсортированный: ');i: = 1 to n do(a [i]: 3,' ');;;;: ='-';keypressed then: = readkey;k of

'1': begin;(a);;;;;

'2': begin;(a);;;;;

'3': begin; Insert (a);;;;;

'4': begin;;;;;;;;k='0';.

Заключение

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

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

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

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

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

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

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

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

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

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

Глоссарий