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

Введение

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

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

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

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

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

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

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

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

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

Работа состоит из введения, трех глав («Глава 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;