Алгоритмы сортировки данных. (Определение понятия «сортировка массива»)

Содержание:

Введение

Актуальность исследования.

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

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

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

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

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

Для достижения данной цели необходимо решение следующих задач:

• Рассмотреть в литературе определение понятия «сортировка»;
• Привести классификации методов сортировки;
• Изучить квадратичные и субквадратичные методы сортировки – сортировка методом селекции, сортировка вставками, пузырьковая сортировка, шейкерная сортировка, сортировка выбором, сортировка Шелла;
• Изучить логарифмические и линейные алгоритмы сортировка – пирамидальная сортировка, быстрая сортировка, поразрядная сортировка.

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

Работа состоит из введения, трех глав («Глава 1. Основные понятия и определения», «Глава 2. Квадратичные и субквадратичные алгоритмы», «Глава 3. Логарифмические и линейные алгоритмы»), заключения и списка использованной литературы.

Глава 1. Основные понятия и определения

1.1. Определение понятия «сортировка массива»

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

Под сортировкой обычно понимают процесс перестановки объектов данного множества в определенном порядке^[1].

Н. Культин, под процессом сортировки понимает процесс перестановки элементов с целью упорядочивания их в соответствии с каким-либо критерием^[2].

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

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

Следовательно, методы сортировки очень важны, особенно при обработке данных^[3].

Основное требование к методам сортировки массивов — экономное использование памяти. Это означает, что переупорядочение элементов нужно выполнять in situ (на том же месте).

​​​​​​​1.2. Классификация методов сортировки

Так как, сортировка — перестановка местами объектов в определенном порядке. Известно несколько сотен алгоритмов сортировки и их модификаций.

Методы, сортирующие элементы in situ (на том же месте), можно разбить на три основных класса в зависимости от лежащего в их основе приема:

1. Сортировка включениями.

2. Сортировка выбором.

3. Сортировка обменом^[4].

В другом источнике, различают сортировку по возрастанию и по убыванию^[5].

В другом интернет источнике, методы упорядочения подразделяются на внутренние (обрабатывающие массивы) и внешние (занимающиеся только файлами)^[6]. То есть,

- внутренняя сортировка - сортировка в оперативной памяти;

- внешняя сортировка - сортировка во внешней памяти^[7].

Можно так же выделить и методы сортировки:

•строгие (прямые) методы;

•улучшенные методы.

строгие методы:

•метод прямого включения;

•метод прямого выбора;

•метод прямого обмена^[8].

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

Примером квадратичных и субквадратичных алгоритмов являются:

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

· сортировка пузырьком(BubbleSort) и ее улучшения;

· сортировка простыми вставками(InsertSort)4

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

Примером логарифмических и линейных алгоритмов являются:

· пирамидальная сортировка (HeapSort);

· быстрая сортировка (QuickSort);

· поразрядная сортировка(RadixSort).

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

Глава 2. Квадратичные и субквадратичные алгоритмы

2.1 Сортировка методом селекции

Идея метода сортировки методом селекции состоит в то, что определяется исходный минимальный элемент и его позиция. Минимальный элемент меняется местами с 1-ым элементом вектора. Потом берем отрезок [2..n] и находим его минимум. Далее процесс нахождения минимального элемента и его обмена с текущим элементом продолжается (n-1) раз.

Пример. Пусть дан вектор А:

18 13 4 22 10 24 9 1 23 11

1 13 4 22 10 24 9 18 23 11

1 4 13 22 10 24 9 18 23 11

…

1 4 9 10 11 13 18 22 23 24

Исходный алгоритм сортировки методом селекции будет следующий:

For i:= 1 to n-1 step1

{определение минимального элемента участка [i..n]}

{обмен минимального элемента с i-тым элементом}

End

Детализируем предложенный алгоритм и получим следующий алгоритм:

For i:= 1 to n-1 step1

min:= a[i];

i_min:= i;

For j:= i+1 to n step1

If a[j]<min then

min:=a[j];

i_min:= j;

End;

End;

a[i_min]:= a[i];

a[i]:= min;

End.

2.2 Сортировка вставками

Сортировка вставками – относится к самым простым алгоритмам сортировки. Как таково большой «популярностью» он пользуется в новичков в программировании.

Основная идея сортировки вставками состоит в том, что при добавлении нового элемента стоит уже отсортированный список его сразу вставляют в нужное место вместо того, чтобы вставлять его в произвольное место, а затем заново сортировать весь список. При сортировке вставками первый элемент любого списка считается отсортированным списком длины I. Двухэлементный отсортированный список создастся добавлением второго элемента исходного списка в нужное место одно- элементного списка, содержащего первый элемент. После этого можно вставить третий элемент исходного списка в отсортированный двухэлементный список. Этот процесс повторяется до тех пор, пока все элементы исходного списка не окажутся в расширяющейся отсортированной части списка^[9].

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

A 18 13 4 22 10 24 9 1 23 11

13 18 4 22 10 24 9 1 23 11

4 13 18 22 10 24 9 1 23 11

…

1 4 9 10 11 13 18 22 23 24

Исходный алгоритм сортировки методом вставки следующий:

For i:= 2 to n step1

{включение i-ого элемента}

{поиск среди элементов [1..i-1]}

End

Детализируем алгоритм:

For i:= 2 to n step1

x:= a[i];

j:= i-1;

While (j>=1) and (a[j]>x) do

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

j:= j-1;

End;

a[j+1]:= x;

End.

Метод сортировки вставками очень хорош для сортировки небольших массивом.

Сортировка вставками если сравнить с методом сортировки пузырьком отличается тем, что «сопровождаем» элемент массива и вставляем его на нужное место. В сортировке пузырьком, после обмена местами двух элементов, даже если этот обмен привел к опять к нарушению порядка, а процесс все равно двигаемся дальше^[10].

Плюсы данной сортировки: алгоритм эффективен при работе со списками, алгоритм отлично справляется с массивами небольшого размера, может работать с последовательно поступающими данными^[11].

Еще один плюс в том, что алгоритм сортировки вставками является возможность сортировать массив по мере его получения. То есть имея часть массива, можно начинать его сортировать. В параллельном программирование такая особенность играет не маловажную роль^[12].

Следует отметить, что с увеличением размера сортируемого массива увеличивается и время сортировки.

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

Самый простой метод сортировки в реализации – это пузырьковая сортировка. Этот метод еще называется обменная сортировка.

Пузырьковая сортировка известна своей низкой скоростью, однако на концептуальном уровне это простейший алгоритм сортировки^[13].

Исходный алгоритм:

For i:= 1 to n-1 step1

{анализ перестановки}

{обмен}

End

Детализируем алгоритм:

For i:= 1 to n-1 step1

For j:= n-1 to 1 step-1

If a[j+1]<a[j] then

x:= a[j+1];

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

a[j]:= x;

End;

End;

End.

Оптимизируем данный алгоритм:

For j:= n-1 to i (!) step -1 после того, как предыдущий i-ый элемент был установлен на свое место, в следующей итерации массив обрабатывается до следующего элемента.

For i:= 1 to n-1 step1

For j:= n-1 to i step-1

If a[j+1]<a[j] then

x:= a[j+1];

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

a[j]:= x;

End;

End;

End.

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

i:= 1;

Repeat

Swap:=false

For j:= n-1 to i step-1

If a[j+1]<a[j] then

x:= a[j+1];

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

a[j]:= x;

swap:= true;

End;

End;

i:= i+1;

Until (i>n-1) or (not swap)

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

2.4 Шейкерная сортировка

Шейкерная сортировка еще называется и сортировка перемешиванием или коктейльная сортировка.

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

Поэтому была придумана более эффективная форма сортировки «пузырьком» - «шейкер»-сортировка. В ней пределы той части массива в которой есть перестановки, сужаются. Плюс — внутренние циклы проходят по массиву то в одну, то в другую сторону, поднимая самый легкий элемент вверх и опуская самый тяжелый элемент в самый низ за одну итерацию внешнего цикла^[14].

То есть, шейкерная сортировка использует идею пузырьковой сортировки, но 1 раз элементы просматриваются в прямом порядке, 2-ой – в обратном и т.д.

Type

vector = array [1..n] of integer;

Var

a: vector;

k: Natural;

r: Natural;

i: Natural;

x: integer;

Begin

k:= 1;

r:= n;

Repeat

For i:= r to k+1 step-1

If a[i]<a[i-1] then

x:= a[i];

a[i]:= a[i-1];

a[i-1]:= x;

End;

End;

k:= k+1;

For i:= k to r-1 step1

If a[i]>a[i+1] then

x:= a[i];

a[i]:= a[i+1];

a[i+1]:= x;

End;

End;

r:= r-1;

Until k>r

Оптимизируем данный алгоритм: для этого необходимо после каждого обмена запоминать i.

Type

vector = array [1..n] of integer;

Var

a: vector;

k: Natural;

r: Natural;

i: Natural;

m: Natural;

x: integer;

Begin

k:= 1;

r:= n;

Repeat

For i:= r to k+1 step-1

If a[i]<a[i-1] then

x:= a[i];

a[i]:= a[i-1];

a[i-1]:= x;

m:= i- 1;

End;

End;

k:= m+1;

For i:= k to r-1 step1

If a[i]>a[i+1] then

x:= a[i];

a[i]:= a[i+1];

a[i+1]:= x;

m:= i+1;

End;

End;

r:= m-1;

Until k>r

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

Изображенный ниже график иллюстрирует разницу в эффективности изученных алгоритмов.

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

Сортировка выбором (Selection sort) — может быть как устойчивый, так и неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2)(n2), предполагая что сравнения делаются за постоянное время.

Алгоритм метода сортировки Selection sort:

1) Ищем порядковый номер минимального значения в не отсортированной части массива.

2) Меняем его с крайним не отсортированным значением, если крайнее но отсортированное значение является минимальным ничего не делаем.

3) Повторяем пункты 1 и 2 пока весь массив не будет отсортирован^[15].

Пример программы представлен в приложении А.

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

Сортировка Шелла примерно так же получается из сортировки вставками, как пузырьковая сортировка трансформируется в сортировку расчёской.

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

Как известно, вставочный метод очень эффективно обрабатывает почти отсортированные массивы. Сортировка Шелла при первоначальных проходах достаточно быстро и доводит массив к состоянию неполной упорядоченности. На заключительном этапе шаг равен единице, т.е. «Шелл» естественным образом трансформируется в сортировку простыми вставками^[16].

Сложность по времени

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

Первоначально автор сортировки, Дональд Шелл, предложил ряд

[n/4], [n/2], [n/8], …, 1

который давал скорость O(n2).

В течении последующих 50 лет, многие исследователи (среди которых — легендарный Роберт Седжвик) подбирали различные зависимости, постепенно улучшая результат. На данный момент таковым является ряд, предложенный в 2001 году Марсином Сиурой:

701, 301, 132, 57, 23, 10, 4, 1.

Это — результат многочисленных тестов, до сих пор неизвестно, можно или нельзя его улучшить^[17].

Пример реализации сортировки Шелла паскаль:

incr:= n div 2;

while incr>0 do

begin

for i:=incr+1 to n do

begin

j:= i-incr;

while j>0 do

if A[j]>A[j+incr] then

begin

c:= A[j];

A[j]:=A[j+incr];

A[j+incr]:=A[j];

j:=j-incr

end

else j:=0 { останов проверки}

end;

incr:= incr div 2

end;

Сортировка хорошо подходит для массивов среднего размера — например, до нескольких тысяч элементов (в зависимости от конкретной реализации)^[18].

Глава 3. Логарифмические и линейные алгоритмы

3.1 Пирамидальная сортировка

Далее рассмотрим более сложные методы сортировки, но они являются более эффективными.

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

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

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

Является «умной» модификацией-синтезом сортировки выбором и пузырьковой сортировки^[19].

Фрагмент программы, а именно пирамидальной сортировки показан ниже:

var L, R: integer;

x: integer;

procedure sift (L, R: integer);

var i, j: integer; x: integer;

begin i:=L; j:=2*L; x:=a[L]j

if (j<R) and (a[j] < a[j+l]) then j:=j+l;

while (j <= R) and (x < a[j]) do begin

a[i]:=a[j]j i:=j; j:=2*j;

if (j < R) and (a[j] < a[j+l]) then j:=j+l;

end;

a[i]:=x

end;

begin

L:=(n Div 2)+l; R:=n;

while L > 1 do begin L:=L-1; sift(L, R) end;

while R > - do begin

x:= a[l]; a[l]:= a[R]; a[R]:=x; R:=R-l; sift(L,

end;

Несмотря на некоторую внешнюю сложность, пирамидальная сортировка является одной из самых эффективных. Алгоритм сортировки эффективен для больших n. В худшем случае требуется n·log2n шагов, сдвигающих элементы. Среднее число перемещений примерно равно (n/2)·log2n, и отклонения от этого значения относительно невелики.

3.2 Быстрая сортировка

«Быстрая сортировка» была создана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов.

Метод быстрой сортировки основан на подходе "разделяй-и-властвуй". Общий метод сортировки следующий:

1. из массива выбирается некоторый опорный элемент a[i],
2. запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] - вправо,
3. теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого, то есть:

1. для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.

В конце получится полностью отсортированная последовательность^[20].

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

Даёт в среднем O(n log n) сравнений при сортировке n элементов. В худшем случае, однако, получается O(n²) сравнений. Обычно на практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n log n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре, и на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время^[21].

Процедура сортировки методом быстрой сортировки представлен ниже:

procedure quicksort(var mas: array[1..n] of integer; first, last: integer);

var f, l, mid, count: integer;

begin

f:=first;

l:=last;

mid:=mas[(f+l) div 2]; {вычисление опорного элемента}

repeat

while mas[f]<mid do inc(f);

while mas[l]>mid do dec(l);

if f<=l then {перестановка элементов}

begin

count:=mas[f];

mas[f]:=mas[l];

mas[l]:=count;

inc(f);

dec(l);

end;

until f>l;

if first<l then quicksort(A, first, l);

if f<last then quicksort(A, f, last);

end;

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

3.3 Поразрядная сортировка

Ниже представленный метод сортировки существенно отличается от описанных ранее.

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

Применение поразрядной сортировки имеет одно маленькое «но»: да начало выполнения сортировки необходимо знать

length - максимальное количество разрядов в сортируемых величинах (например, при сортировке слов необходимо знать максимальное количество букв в слове),

range - количество возможных значений одного разряда (при сортировке слов - количество букв в алфавите).

Количество проходов равно числу length.

Пошаговое описание алгоритма

Пусть даны следующие числа: 39, 48, 54, 59, 34, 41, 32 (length = 2, range = 10)

1. Создаем пустые списки, количество которых равно числу range.

2. Распределяем исходные числа по этим спискам в зависимости от величины младшего разряда (по возрастанию).

Для нашего примера получим:

41

32

54, 34

48

59, 39

(Вообще надо создать 10 списков, но некоторые из них оказались пустыми)

3. Собираем числа в той последовательности, в которой они находятся после распределения по спискам.

Получим: 41, 32, 54, 34, 48, 59, 39

4. Повторяем пункты 2 и 3 для всех более старших разрядов поочередно.

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

32, 34, 39

41, 48

54, 59

Объединив числа в последовательность, получим отсортированный массив.

Заключение

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

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

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

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

Библиография

1. Динман М. И. С++. Освой на примерах. - - СПб.: БХВ-Петербург, 2006.- 384 с: ил
2. Катаев, С. М. Бейсик для школьников. Подготовка к ЕГЭ / С. М. Катаев. Л. В. Шеретнева. — СПб.: БХВ-Пстсрбург, 2012. — 272 с.
3. Кетков Ю. Л., Кетков А. Ю. Практика программирования: Бейсик, Си, Паскаль. Самоучитель. — СПб.: БХВ-Петербург, 2001. - 480 с: ил
4. Культин, Н. Small Basic для начинающих /II. Культин, Л. Цой. — СПб.: КХВ-Петербург, 2011. — 256 с.
5. Лафоре P. Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. — СПб.: Питер, 2011. — 704 с.
6. Макарова Н. В., Волков В. Б. Информатика: Учебник для вузов. — СПб.: Питер, 2015. — 576 с.
7. Могилев, А. В. Методы программирования. Компьютерные вычисления/ А. В. Могилев, Л. В. Листрова. - - СПб,: БХВ-Петербург, 2008. - 320 с. - ISBN 978-5-9775-0151-4
8. Простые методы сортировки массивов [онлайн] - URL: http://hosting.vspu.ac.ru/~chul/program/sortmass.pdf (дата обращения 24.09.2016)
9. Понятие сортировки. Прямые методы сортировки [Онлайн] - URL: http://www.aisd.kubsau.ru/lections/lect_kurs_bi/lect9_bi.html (дата обращения 02.10.2016)
10. Основные методы внутренней сортировки. Классификация методов сортировки [онлайн] - URL:http://studopedia.su/14_96708_osnovnie-metodi-vnutrenney-sortirovki.html (дата обращения 28.09.2016)).
11. Сортировка вставками [онлайн] - URL: http://learnc.info/algorithms/insertionsort.html (дата обращения 01.10.2016)
12. Сортировка вставками [онлайн] - URL: http://ucxodnuku.ru/algoritm/sortirovka-vstavkami.html (дата обращения 29.09.2016)
13. Сортировка вставками [онлайн] - URL: http://cppstudio.com/post/462/ (дата обращения 29.09.2016)
14. Сортировка Шелла :: Shell sort [онлайн] - URL: http://sorting.valemak.com/shell/ (дата обращения 29.09.2016)
15. Сортировка кучей :: Heap sort [онлайн] - URL: http://sorting.valemak.com/heap/ (дата обращение 28.09.2016)
16. Быстрая сортировка [онлайн] - URL: http://truthiness.ru/88951d72e2ba6711.html (дата обращения 27.09.2016)
17. Лекция №4.1: Сортировки массивов [Онлайн] - URL:https://www.google.com/search?tbm=bks&q=+%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0+%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2%D0%B0 (дата обращения 02.10.2016)

Приложение А

Листинг программы, реализующую сортировку методом выбора

Const

N=100;

procedure Swap(var X,Y:Real);

begin

X:=X+Y;

Y:=X-Y;

X:=X-Y;

end;

Procedure Selection_Sort (var a : array of real; LengthArray :Integer);

var i,i2,Min_idx:integer;

begin

for i:=0 to LengthArray-1 do

begin

Min_idx:=i;

for i2:=i+1 to LengthArray-1 do

if a[Min_idx]>a[i2] then Min_idx:=i2;

if i<>Min_idx then Swap(a[i],a[Min_idx]);

end;

end;

var

a,a1 : array [1..N] of real;

i: integer;

begin

for i:=1 to N do a[i]:=Random(100);

a1:=a;

Selection_Sort(a1,N);

for i:=1 to N do writeln(a[i]:7:0,' ',a1[i]:7:0);

1. Простые методы сортировки массивов [онлайн] - URL: http://hosting.vspu.ac.ru/~chul/program/sortmass.pdf (дата обращения 24.09.2016) ↑

2. Культин, Н. Small Basic для начинающих /II. Культин, Л. Цой. — СПб.: КХВ-Петербург, 2011. — с. 99 ↑

3. Простые методы сортировки массивов [онлайн] - URL: http://hosting.vspu.ac.ru/~chul/program/sortmass.pdf (дата обращения 24.09.2016) ↑

4. Простые методы сортировки массивов [онлайн] - URL: http://hosting.vspu.ac.ru/~chul/program/sortmass.pdf (дата обращения 24.09.2016) ↑

5. Культин, Н. Small Basic для начинающих /II. Культин, Л. Цой. — СПб.: КХВ-Петербург, 2011. — с. 99 ↑

6. Лекция №4.1: Сортировки массивов [Онлайн] - URL:https://www.google.com/search?tbm=bks&q=+%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0+%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2%D0%B0 (дата обращения 02.10.2016) ↑

7. Понятие сортировки. Прямые методы сортировки [Онлайн] - URL: http://www.aisd.kubsau.ru/lections/lect_kurs_bi/lect9_bi.html (дата обращения 02.10.2016) ↑

8. Понятие сортировки. Прямые методы сортировки [Онлайн] - URL: http://www.aisd.kubsau.ru/lections/lect_kurs_bi/lect9_bi.html (дата обращения 02.10.2016) ↑

9. Макарова Н. В., Волков В. Б. Информатика: Учебник для вузов. — СПб.: Питер, 2015. — с. 425 ↑

10. Сортировка вставками [онлайн] - URL: http://learnc.info/algorithms/insertionsort.html (дата обращения 01.10.2016) ↑

11. Сортировка вставками [онлайн] - URL: http://ucxodnuku.ru/algoritm/sortirovka-vstavkami.html (дата обращения 29.09.2016) ↑

12. Сортировка вставками [онлайн] - URL: http://cppstudio.com/post/462/ (дата обращения 29.09.2016) ↑

13. Лафоре P. Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. — СПб.: Питер, 2011. — с. 89. ↑

14. Могилев, А. В. Методы программирования. Компьютерные вычисления/ А. В. Могилев, Л. В. Листрова. - - СПб,: БХВ-Петербург, 2008. – с. 117. ↑

15. Катаев, С. М. Бейсик для школьников. Подготовка к ЕГЭ / С. М. Катаев. Л. В. Шеретнева. — СПб.: БХВ-Пстсрбург, 2012. — с. 246. ↑

16. Кетков Ю. Л., Кетков А. Ю. Практика программирования: Бейсик, Си, Паскаль. Самоучитель. — СПб.: БХВ-Петербург, 2001. – с. 187. ↑

17. Сортировка Шелла :: Shell sort [онлайн] - URL: http://sorting.valemak.com/shell/ (дата обращения 29.09.2016) ↑

18. Лафоре P. Структуры данных и алгоритмы в Java. Классика Computers Science. 2-е изд. — СПб.: Питер, 2011. — с. 299. ↑

19. Сортировка кучей :: Heap sort [онлайн] - URL: http://sorting.valemak.com/heap/ (дата обращение 28.09.2016) ↑

20. Динман М. И. С++. Освой на примерах. - - СПб.: БХВ-Петербург, 2006.- с. 95-96 ↑

21. Быстрая сортировка [онлайн] - URL: http://truthiness.ru/88951d72e2ba6711.html (дата обращения 27.09.2016) ↑