Учебная работа. Реферат: Сортировка данных в массиве

Учебная работа. Реферат: Сортировка данных в массиве

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

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

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

Сортировка вставками похожа на процесс тасования карточек с именами. Регистратор вносит каждое имя на карточку, а потом упорядочивает карточки по алфавиту, вставляя карточку в верхнюю часть стопки в подходящее пространство. Опишем этот процесс на примере нашего пятиэлементного перечня A = 50, 20, 40, 75, 35 (набросок 1).

В функцию InsertionSort передается массив A и длина перечня n. Разглядим i-ый проход (1<i<n-1). Подсписок от A[0] до A[i-1] уже отсортирован по возрастанию. В качестве вставляемого (TARGET) выберем элемент A[i] и будем продвигать его к началу перечня, сравнивая с элементами A[i-1], A[i-2] и т.д. Просмотр завершается на элементе A[j], который меньше либо равен TARGET, либо находится сначала перечня (j = 0). По мере продвижения к началу перечня любой элемент двигается на Право (A[j] = A[j-1]). Когда подходящее пространство для A[i] будет найдено, этот элемент вставляется в точку j.

Рис. 1

// Сортировка вставками упорядочивает подсписки A[0]…A[i], 1 <= i <= n-1. Для

// всякого i A[i] вставляется в пригодную позицию A[j]

template <class T>

void InsertionSort(T A[], int n)

{

int i, j;

T temp;

// i описывает подсписок A[0]…A[i]

for (i=1; i<n; i++)

{

// индекс j пробегает вниз по списку от A[i] в процессе

// поиска правильной позиции вставляемого значения

j = i;

temp = A[i];

// найти пригодную позицию для вставки, сканируя подсписок,

// пока temp < A[j-1] либо пока не повстречается начало перечня

while (j > 0 && temp < A[j-1])

{

// двинуть элементы на Право, чтоб высвободить пространство для вставки

A[j] = A[j-1];

j—;

}

// точка вставки найдена; вставить temp

A[j] = temp;

}

}

Вычислительная эффективность сортировки вставками

Сортировка вставками просит фиксированного числа проходов. На n-1 проходах вставляются элементы от A[1] до A[n-1]. На i-ом проходе вставки выполняются в подсписок A[0]–A[i] и требуют в среднем i/2 сравнений. Общее число сравнений равно

1/2 + 2/2 + 3/2 + … + (n-2)/2 + (n-1)/2 = n(n-1)/4

В отличие от остальных способов, сортировка вставками не употребляет обмены. Сложность метода измеряется числом сравнений и равна O(n2). Лучший вариант – когда начальный перечень уже отсортирован. Тогда на i-ом проходе вставка делается в точке A[i], а общее число сравнений равно n-1, т.е. сложность составляет O(n). Наихудший вариант возникает, когда перечень отсортирован по убыванию. Тогда любая вставка происходит в точке A[0] и просит i сравнений. Общее число сравнений равно n(n-1)/2, т.е. сложность составляет O(n2).

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

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

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

Обширно применяемый способ пирамидальной сортировки также обрабатывает массив «на месте» и имеет эффективность O(n log2n). Но «стремительная» сортировка, которую изобрел К.Хоар, для большинства приложений превосходит пирамидальную сортировку и является самой резвой из узнаваемых до сего времени.

Описание «резвой» сортировки

Как и для большинства алгоритмов сортировки, методика «резвой» сортировки взята из ежедневного опыта. Чтоб отсортировать огромную стопку алфавитных карточек по именам, можно разбить ее на две наименьшие стопки относительно какой-либо буковкы, к примеру K. Все имена, наименьшие либо равные K, идут в одну стопку, а другие – в другую.

Рис.2

Потом любая стопка опять делится на две. к примеру, на рисунке 2 точками разбиения являются буковкы F и R. процесс разбиения на все наименьшие и наименьшие стопки длится.

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

A = 800, 150, 300, 600, 550, 650, 400, 350, 450, 700

Фаза сканирования

Массив имеет нижнюю границу, равную 0 (low), и верхнюю границу, равную 9 (high). Его середина приходится на 4 элемент (mid). Первым центральным элементом является A[mid] = 550. Таковым образом, все элементы массива A разбиваются на два подсписка: Sl и Sh. Наименьший из их (Sl) будет содержать элементы, наименьшие либо равные центральному. Подсписок Sh будет содержать элементы огромные, чем центральный. Так как заблаговременно понятно, что центральный элемент в итоге будет крайним в подсписке Sl, мы временно передвигаем его в начало массива, меняя местами с A[0] (A[low]). Это дозволяет исследовать подсписок A[1]—A[9] при помощи 2-ух индексов: scanUp и scanDown. Изначальное

Рис.3

Оригинальность «резвой» сортировки заключается во содействии 2-ух индексов в процессе сканирования перечня. Индекс scanUp {перемещается} ввысь по списку, а scanDown – вниз. Мы продвигаем scanUp вперед и отыскиваем элемент A[scanUp] больший, чем центральный. В этом месте сканирование останавливается, и мы готовимся переместить отысканный элемент в верхний подсписок. Перед тем, как это перемещение произойдет, мы продвигаем индекс scanDown вниз по списку и находим элемент, наименьший либо равный центральному. Таковым образом, у нас есть два элемента, которые находятся не в тех подсписках, и их можно поменять местами.

Swap (A[scanUp], A[scanDown]); // поменять местами партнеров

Этот процесс длится до того времени, пока scanUp и scanDown не зайдут друг за друга (scanUp = 6, scanDown = 5). В этот момент scanDown оказывается в подсписке, элементы которого меньше либо равны центральному. Мы попали в точку разбиения 2-ух списков и указали окончательную позицию для центрального элемента. В нашем примере поменялись местами числа 600 и 450, 800 и 350, 650 и 400 (см. набросок 4).

Рис.4

Потом происходит обмен значениями центрального элемента A[0] с A[scanDown]:

Swap(A[0], A[scanDown]);

В итоге у нас возникают два подсписка A[0] – A[5] и A[6] – A[9], при этом все элементы первого подсписка меньше частей второго, и крайний элемент первого подсписка является его большим элементом. Таковым образом, можно считать, что опосля проделанных операций подсписки разбиты элементом А[5] = 550 (набросок 5). Если сейчас отсортировать любой подсписок по отдельности, то у нас получится на сто процентов отсортированный массив. Заметьте, что на самом деле оба этих подсписка являются таковыми же массивами, как и начальный, потому к ним можно применить этот же самый метод. Применение такого же метода к частям массива именуется рекурсивной фазой.

Рекурсивная фаза

Одним и этим же способом обрабатываются два подсписка: Sl(A[0] – A[4]) и Sh(A[6] – A[9]). Элемент А[5] обрабатывать не нужно, потому что он уже находится на собственном месте.

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

Рис.5

метод QuickSort

Этот рекурсивный метод делит перечень A[low]—A[high] по центральному элементу, который выбирается из середины перечня

mid = (high + low) / 2;

pivot = A[mid];

Опосля обмена местами центрального элемента с A[low], задаются исходные значения индексам scanUp = low + 1 и scanDown = high, указывающим на начало и конец перечня, соответственно. метод управляет этими 2-мя индексами. Поначалу scanUp продвигается ввысь по списку, пока не превзойдет

while (scanUp <= scanDown && A[scanUp] <= pivot)

scanUp++;

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

while (pivot < A[scanDown])

scanDown—;

По окончании этого цикла (и при условии что scanUp < scanDown) оба индекса адресуют два элемента, находящихся не в тех подсписках. Эти элементы изменяются местами.

Swap(A[scanUp], A[scanDown]);

Обмен частей прекращается, когда scanDown становится меньше, чем scanUp. В этот момент scanDown показывает начало левого подсписка, который содержит наименьшие либо равные центральному элементы. Индекс scanDown становится центральным. Взять центральный элемент из A[low]:

Swap(A[low], A[scanDown]);

Для обработки подсписков употребляется рекурсия. Опосля обнаружения точки разбиения мы рекурсивно вызываем QuickSort с параметрами low, mid-1 и mid+1, high. Условие останова возникает, когда в подсписке остается наименее 2-ух частей, потому что одноэлементный либо пустой массив упорядочивать не необходимо.

// Swap меняет местами элементы массива. Соответственный тип данных

// должен поддерживать операцию «=».

template <class T>

void Swap(T & el1, T & el2)

{

T tmp = el1;

el1 = el2;

el2 = tmp;

}

// QuickSort воспринимает в качестве характеристик массив

// и предельные значения его индексов

template <class T>

void QuickSort(T A[], int low, int high)

{

// локальные переменные, содержащие индекс середины — mid,

// центральный элемент и индексы сканирования

T pivot;

int scanUp, scanDown;

int mid;

// если спектр индексов не содержит в себе

// как минимум два элемента, окончить работу

if(high — low <= 0)

return;

else if(high — low == 1)

{

// если в подсписке два элемента, сопоставить их меж собой

// и поменять местами по мере необходимости

if(A[high] < A[low])

Swap(A[low], A[high]);

return;

}

// Высчитать индекс середины и поместить

// элемента массива в переменную pivot.

mid = (low + high)/2;

pivot = A[mid];

// Поменять местами центральный и исходный элементы перечня.

Swap(A[mid], A[low]);

// Инициализировать индексы scanUp и scanDown.

scanUp = low + 1;

scanDown = high;

// Находить элементы, расположенные не в тех подсписках.

// Тормознуть при scanDown < scanUp.

do

{

// Продвигаться ввысь по первому подсписку. Тормознуть,

// когда scanUp укажет на 2-ой подсписок либо если

// указываемый сиим индексом элемент > центрального.

while(scanUp <= scanDown && A[scanUp] <= pivot)

scanUp++;

// Продвигаться вниз по второму подсписку. Тормознуть,

// когда scanDown указжет на элемент >= центральному.

while(A[scanDown] > pivot)

scanDown—;

// Если индексы все еще в собственных подсписках, то они указывают

// на два элемента, находящихся не в тех подсписках.

if(scanUp < scanDown)

{

// Поменять их местами

Swap(A[scanUp], A[scanDown]);

}

}

while(scanUp < scanDown);

// Скопировать элемент на который показывает точка разбиения

// в 1-ый элемент первого подсписка, …

A[low] = A[scanDown];

// а центральный элемент в точку разбиения

A[scanDown] = pivot;

// если 1-ый подсписок (low…scanDown-1) имеет 2 либо наиболее

// элемента, выполнить для него рекурсивный вызов QuickSort

if(low < scanDown-1)

QuickSort(A, low, scanDown-1);

// если 2-ой подсписок (scanDown+1…high) имеет 2 либо наиболее

// элемента, выполнить для него рекурсивный вызов QuickSort

if(scanDown+1 < high)

QuickSort(A, scanDown+1, high);

}

Вычислительная сложность «резвой» сортировки

Общий анализ эффективности «резвой» сортировки довольно труден. Будет лучше показать ее вычислительную сложность, подсчитав число сравнений при неких безупречных допущениях. Допустим, что n – степень двойки, n = 2k (k = log2n), а центральный элемент размещается буквально в центре всякого перечня и разбивает его на два подсписка приблизительно схожей длины.

При первом сканировании делается n-1 сравнений. В итоге создаются два подсписка размером n/2. На последующей фазе обработка всякого подсписка просит приблизительно n/2 сравнений. Общее число сравнений на данной фазе равно 2(n/2) = n. На последующей фазе обрабатываются четыре подсписка, что просит 4(n/4) сравнений, и т.д. В конце концов процесс разбиения прекращается опосля k проходов, когда получившиеся подсписки содержат по одному элементу. Общее число сравнений примерно равно

n + 2(n/2) + 4(n/4) + … + n(n/n) = n + n + … + n = n * k = n * log2n

Для перечня вида вычислительная сложность «резвой» сортировки равна O(n log2 n). Безупречный вариант, который мы лишь что разглядели, практически возникает тогда, когда массив уже отсортирован по возрастанию. Тогда центральный элемент попадает буквально в середину всякого подсписка.

Если массив отсортирован по убыванию, то на первом проходе центральный элемент находится на середине перечня и изменяется местами с каждым элементом как в первом, так и во 2-м подсписке. Результирующий перечень практически отсортирован, метод имеет сложность порядка O(n log2n).

Рис.6

Наихудшим сценарием для «резвой» сортировки будет тот, при котором центральный элемент все время попадает в одноэлементный подсписок, а все остальные элементы остаются во 2-м подсписке. Это происходит тогда, когда центральным постоянно является меньший элемент. Разглядим последовательность 3, 8, 1, 5, 9.

На первом проходе делается n сравнений, а больший подсписок содержит n-1 частей. На последующем проходе этот подсписок просит n-1 сравнений и дает подсписок из n-2 частей и т.д. Общее число сравнений равно:

n + n-1 + n-2 + … + 2 = n(n+1)/2 — 1

Сложность худшего варианта равна O(n2), т.е. не лучше, чем для сортировок вставками и выбором. Но этот вариант является патологическим и маловероятен на практике. В общем, средняя производительность «резвой» сортировки выше, чем у всех рассмотренных нами сортировок.

метод QuickSort выбирается за базу в большинстве всепригодных сортирующих утилит. Если вы не сможете смириться с производительностью наихудшего варианта, используйте пирамидальную сортировку – наиболее устойчивый метод, сложность которого равна O(n log2n) и зависит лишь от размера перечня.

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

Мы сравнили методы сортировки, испытав их на массивах, содержащих 4000, 8000, 10000, 15000 и 20000 целых чисел, соответственно. время выполнения измерено в тиках (1/60 толика секунды). Посреди всех алгоритмов порядка O(n2) время сортировки вставками отражает тот факт, что на i-ом проходе требуется только i/2 сравнений. Этот метод очевидно превосходит все остальные сортировки порядка O(n2). Заметьте, что самую худшую общую производительность показывает сортировка способом пузырька. Результаты испытаний показаны в таблице 1 и на рисунке 7.

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

n
Обменная сортировка
Сортировка выбором
Пузырьковая сортировка
Сортировка вставками

4 000
12.23
17.30
15.78
5.67

8 000
49.95
29.43
64.03
23.15

10 000
77.47
46.02
99.10
35.43

15 000
173.97
103.00
223.28
80.23

20 000
313.33
185.05
399.47
143.67

Рис.7 Сопоставление сортировок порядка O(n2)

n
Обменная сортировка
Сортировка выбором
Пузырьковая сортировка
Сортировка вставками

8 000 (упорядочен по возрастанию)
185.27
185.78
0.03
0.05

8 000 (упорядочен по убыванию)
526.17
199.00
584.67
286.92

В общем случае QuickSort является самым резвым методом. Благодаря собственной эффективности, равной O(n log2n), он очевидно превосходит хоть какой метод порядка O(n2). Судя по результатам испытаний, приведенных в последующей таблице, он также резвее хоть какой из сортировок порядка O(n log2n), рассмотренных нами в прошедшем номере. Направьте внимание, что эффективность «резвой» сортировки составляет O(n log2n) даже в экстремальных вариантах. Зато сортировка средством поискового дерева становится в этих вариантах O(n2) сложной, потому что создаваемое дерево является вырожденным.

n
Турнирная сортировка
Сортировка средством дерева
Пирамидальная сортировка
«Стремительная» сортировка

4 000
0.28
0.32
0.13
0.07

8 000
0.63
0.68
0.28
0.17

10 000
0.90
0.92
0.35
0.22

15 000
1.30
1.40
0.58
0.33

20 000
1.95
1.88
0.77
0.47

8 000 (упорядочен по возрастанию)
1.77
262.27
0.75
0.23

8 000 (упорядочен по убыванию)
1.65
275.70
0.80
0.28

Рис.8 Сопоставление сортировок порядка O(n log2n)

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

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

#include <iostream.h>

#include «arrsort.h»

// Перечислимый тип, описывающий изначальное состояние массива данных.

enum Ordering {randomorder, ascending, descending};

// Перечислимый тип, идентифицирующий метод сортировки.

enum SortType

{

SortTypeBegin,

exchange = SortTypeBegin,

selection,

bubble,

insertion,

tournament,

tree,

heap,

quick,

SortTypeEnd = quick

};

// копировать n-элементныймассив y вмассив x

void Copy(int *x, int *y, int n)

{

for (int i=0; i<n; i++)

*x++ = *y++;

}

// Общая сортирующая функция, которая воспринимает начальный массив

// с данной упорядоченностью частей и применяет обозначенный

// алгоритмсортировки.

void Sort(int a[], int n, SortType type, Ordering order)

{

long time;

cout << «Сортировка » << n;

// Вывести тип упорядоченности.

switch(order)

{

case random:

cout << » частей. «;

break;

case ascending:

cout << » частей, упорядоченных по возрастанию. «;

break;

case descending:

cout << » частей, упорядоченных по убыванию. «;

break;

}

// засечьвремя

time = TickCount();

// Выполнить сортировку и вывести ее тип…

switch(type)

{

case exchange:

ExchangeSort(a, n);

cout << «Сортировкаобменом: «;

break;

case selection:

SelectionSort(a, n);

cout << «Сортировкавыбором: «;

break;

case bubble: . . . . . . .

case insertion: . . . . . . .

case tournament: . . . . . . .

case tree: . . . . . . .

case heap: . . . . . . .

case quick: . . . . . . .

}

// Подсчитать время выполнения в секундах.

time = TickCount() — time;

cout << time/60.0 << endl;

}

// Делает сортировку массива с n элементами,

// расположенных в порядке, определяемом параметром order.

void RunTest(int n, Ordering order)

{

int i;

int *a, *b;

SortType stype;

RandomNumber rnd;

// Выделить память для 2-ух n-элементных массивов a и b.

a = new int [n];

b = new int [n];

// Найти тип упорядоченности данных.

if(order == randomorder)

{

// Заполнить массив b случайными числами.

for(i=0; i<n; i++)

b[i] = rnd.Random(n);

}

else

{

// Данные, отсортированные по возрастанию.

for(i=0; i<n; i++)

b[i] = i;

}

else

{

// данные, отсортированные по убыванию.

for(i=0; i<n; i++)

b[i] = n — 1 — i;

}

else

{

// Копировать данные в массив a. Попеременно выполнить сортировку для

// каждоготипа.

for(stype = SortTypeBegin; stype <= SortTypeEnd; stype = SortType(stype+1))

{

Copy(a, b, n);

Sort(a, n, stype, order);

}

}

// Удалить оба динамических массива.

delete [] a;

delete [] b;

}

// Отсортировать 4 000-, 8 000-, 10 000-, 15 000- и 20 000-элементный массивы,

// заполненные случайными числами.

// Потом поначалу отсортировать 20 000-элементный массив, упорядоченный

// по возрастанию, а позже по убыванию.

void main(void)

{

int nelts[5] = {4000, 8000, 10000, 15000, 20000};

int = i;

cout.precision(3);

cout.setf(ios::fixed | ios::showpoint);

for(i= 0; i<5; i++)

RunTest(nelts[i], randomorder);

RunTest(20000, ascending);

RunTest(20000, descending);

]]>