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

Оглавление

• ВВЕДЕНИЕ
• ГЛАВА 1. ТЕОРЕТИКО-МЕТОДОЛОГИЧЕСКИЕ АСПЕКТЫ ПРОБЛЕМЫ методов сортировки данных в языке Pascal
• 1.1 Понятие сортировки
• 1.2 Критерии оценки алгоритмов сортировки
• 1.3 Постановка задачи сортировки и методы её решения
• 1.4 Сортировка пузырьковым методом
• 1.5 Сортировка выбором элемента
• 1.6 Сортировка вставкой
• 1.7 Усовершенствованные алгоритмы сортировки. Сортировка Шелла
• 1.8 Метод разделения (алгоритм "быстрой" сортировки, метод Хоара)
• 1.9 Сравнительный анализ методов сортировки
• ГЛАВА 2. Использование методов сортировки данных на примере решения практических задач
• 2.1 Задача №1
• 2.2 Задача №2
• 2.3 Задача №3
• Заключение
• Список использованных источников
• ВВЕДЕНИЕ
• Необходимость отсортировать какие-либо величины возникает в программировании очень часто. К примеру, входные данные подаются "вперемешку", а нашей программе удобнее обрабатывать упорядоченную последовательность. Существуют ситуации, когда предварительная сортировка данных позволяет сократить содержательную часть алгоритма в разы, а время его работы - в десятки раз.
• Однако верно и обратное. Сколь бы хорошим и эффективным ни был выбранный вами алгоритм, но если в качестве подзадачи он использует "плохую" сортировку, то вся работа по его оптимизации оказывается бесполезной. Неудачно реализованная сортировка входных данных способна заметно понизить эффективность алгоритма в целом. В данной курсовой работе наша речь будет идти об эффективности различных методов сортировки данных в языке Pascal.
• Объект и предмет исследования - методы сортировки данных, используемые в языке Pascal.
• Целью данного исследования является анализ эффективности различных методов сортировки данных в языке Pascal.
• Вообще говоря, методы сортировки делятся на три типа:
• 1. методы сортировки, которые сортируют без использования дополнительной памяти, за исключением, возможно, небольшого стека и/или массива;
• 2. методы, которые используют для сортировки связанные списки и поэтому используют N дополнительных указателей хранящихся в памяти;
• 3. и методы, которые нуждаются в дополнительной памяти для хранения копии сортируемого файла.
• Мною были рассмотрены преимущества и недостатки таких методов сортировки, как метод обмена, вставок, выбора, методы Шелла и Хоара.
• Основными критериями эффективности алгоритмов сортировки мною были выбраны время его работы и экономное использование памяти.
• И первые три алгоритма, которые мы рассмотрим, для сортировки N элементов имеют время работы пропорциональное N2, в то время как более сложные алгоритмы используют время пропорциональное N log N.
• Кроме времени и объема памяти, критерии эффективности рассмотренных в работе алгоритмов могут включать следующие параметры:
• 1. количество шагов алгоритма, необходимых для упорядочения;
• 2. количество сравнений элементов;
• 3. количество перестановок, выполняемых при сортировке.
• Само собой разумеется, что, чем выше показатель, тем «хуже» алгоритм сортировки.

ГЛАВА 1. ТЕОРЕТИКО-МЕТОДОЛОГИЧЕСКИЕ АСПЕКТЫ ПРОБЛЕМЫ методов сортировки данных в языке Pascal

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- метод сортировки выбором элемента;

- метод разделения (алгоритм "быстрой" сортировки метод Хоара);

- метод Шелла.

1.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"), очень медленно достигает своего места. Необязательно все просмотры делать в одном направлении. Вместо этого всякий последующий просмотр можно делать в противоположном направлении. В этом случае сильно удаленные от своего места элементы будут быстро перемещаться в соответствующее место. Ниже показана улучшенная версия сортировки пузырьковым методом, получившая название "челночной сортировки" из-за соответствующего характера движений по массиву.

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

{челночная сортировка является улучшенной версией сортировки пузырьковым методом}

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

var

j, k, l, r: integer;

x: DataItem;

begin

l := 2; r := count; k := count;

repeat

for j := r downto l do

if item[j-1] then

begin { обмен }

x := item[j-1];

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

item[j] := x;

k := j;

end;

l := k+1;

for j := l to r do

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

begin { обмен }

x := item[j-1];

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

item[j] := x;

k := j;

end;

r := k-1;

until l>r

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

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

1.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. Это значит, что несмотря на одинаковое число операций сравнений для сортировок пузырьковым методом и сортировок выбором, число операций обмена для среднего случая будет значительно меньшим для сортировки выбором.

1.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).

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

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

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

1.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. Эта зависимость значительно лучше квадратичной зависимости, которой подчиняются рассмотренные ранее алгоритмы сортировки. Однако, прежде чем вы решите использовать сортировку Шелла, следует иметь в виду, что быстрая сортировка дает даже еще лучшие результаты.

1.8 Метод разделения (алгоритм "быстрой" сортировки, метод Хоара)

Метод быстрой сортировки был разработан Ч. Ф. Р. Хоаром и он же дал ему это название. В настоящее время этот метод сортировки считается наилучшим. Он основан на использовании обменного метода сортировки. Это тем более удивительно, если учесть очень низкое быстродействие сортировки пузырьковым методом, который представляет собой простейшую версию обменной сортировки.

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

исходное состояние: f e d a c b;

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

второй проход: a b c d e f.

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

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

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

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

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

procedure qs(l, r: integer; var it: DataArray);

var

i, j: integer;

x, y: DataItem;

begin

i:=l; j:=r;

x:=it[(l+r) div 2];

repeat

while it[i]<x do i := i+1;

while x<it[j] do j := j-1;

if y<=j then

begin

y := it[i];

it[i] := it[j];

it[j] := y;

i := i+1; j := j-1;

end;

until i>j;

if l<j then qs(l, j, it);

if l<r then qs(i, r, it)

end;

begin

qs(1, count, item);

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

В данном примере процедура быстрой сортировки обращается к основной процедуре сортировки с именем "qs". Это обеспечивает доступ к данным "item" и "count" при всех вызовах "qs".

Можно считать, что число операций сравнения равно n*log2n, а число операций обмена равно приблизительно n/6*log2n. Эти характеристики значительно лучше характеристик рассмотренных ранее сортировок.

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

1.9 Сравнительный анализ методов сортировки

Итак, какой же метод является лучшим? И от чего зависит выбор того или иного метода при решении задач на сортировку?

Исходя из того, что основным критерием эффективности алгоритма сортировки является скорость, можно сделать вывод, что методы Шелла и Хоара являются наиболее оптимальными.

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

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

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

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

ГЛАВА 2. ИСПОЛЬЗОВАНИЕ МЕТОДОВ СОРТИРОВКИ ДАННЫХ НА ПРИМЕРЕ РЕШЕНИЯ ПРАКТИЧЕСКИХ ЗАДАЧ

2.1 Задача №1

Условие:

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

Решение:

Т.к. задача является простой, решим её «пузырьковым» методом.

Program Zadacha1;

uses crt;

const n=100;

procedure obmen (var x,y: real);

var t:real;

begin t:=x;

x:=y;

y:=t;

end;

var

A:array [1..n] of real;

i,k,j:integer;

begin

clrscr;

writeln ('vvedite razmer massiva');

readln (k);

writeln ('vvedite elementy massiva');

for i:=1 to k do

readln (A[i]);

for i:=1 to k do

if A[i]<0 then A[i]:=abs(A[i]);

for j:=1 to k-1 do

for i:=1 to k-j do

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

obmen (A[i], A[i+1]);

writeln ('resultat:');

for i:=1 to k do

writeln (A[i]:3:2);

readln;

end.

Результат выполнения алгоритма показан на рисунке 2.1:

2.2 Задача №2

Условие:

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

Решение:

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

Program Zadacha2;

uses crt;

const n=100;

procedure obmen (var x,y: integer);

var t:integer;

begin t:=x;

x:=y;

y:=t;

end;

var

A:array [1..n] of integer;

i,k,j:integer;

begin

clrscr;

writeln ('vvedite razmer massiva');

readln (k);

writeln ('vvedite elementy massiva');

for i:=1 to k do

readln (A[i]);

for i:=1 to k do

if A[i]<0 then A[i]:=sqr(A[i]);

for j:=1 to k-1 do

for i:=1 to k-j do

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

obmen (A[i], A[i+1]);

writeln ('resultat:');

for i:=1 to k do

write (A[i]);

readln;

end.

2.3 Задача №3

Условие:

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

Решение:

Program Zadacha3;

uses crt;

const n=100;

procedure obmen (var x,y: integer);

var t:integer;

begin t:=x;

x:=y;

y:=t;

end;

var

A:array [1..n] of integer;

i,k,j:integer;

begin

clrscr;

writeln ('vvedite razmer massiva');

readln (k);

writeln ('vvedite elementy massiva');

for i:=1 to k do

readln (A[i]);

for j:=1 to k-1 do

for i:=1 to k-j do

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

obmen (A[i], A[i+1]);

writeln ('resultat:');

for i:=1 to k do

writeln (A[i]);

readln;

end.

Данная задача решена методом обмена.

Заключение

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

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

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

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

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

pascal данные сортировка

1. Глушков, В.Н. Основы безбумажной информатики Изд. 2-е, испр./Н. В. Глушков - М: Наука, 1987.- 232с.

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

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

4. Зубков, С.В. Assembler, DOS, Windows и Unix./С.В. Зубков - М.: ДМК, 1999.-640с.

5. Корнеев, В.В. Современные микропроцессоры. /В.В. Корнеев, А.В. Киселев - М.: Нолидж, 1998.-376с.

6. Гук, М.А. Процессоры Pentium II, Pentium Pro и просто Pentium./ М.А. Гук - С-Пб: Питер, 1999. - 183с.

7. Офицеров, Д.В. Программирование в интегрированной среде Турбо-Паскаль: Справ. пособие. /Д.В. Офицеров, В.А. Старых - Мн.: Беларусь, 1992. - 240с.

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

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

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

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