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

Существует множество различных алгоритмов сортировки. Все они имеют свои положительные и отрицательные стороны. Перечислим общие критерии оценки алгоритмов сортировки.

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

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

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

Различные сортировки массивов отличаются по быстродействию. Существуют простые методы сортировок, которые требуют порядка n * n сравнений, где n – количество элементов массива и быстрые сортировки, которые требуют порядка n* ln(n) сравнений. Простые методы удобны для объяснения принципов сортировок, т.к. имеют простые и короткие алгоритмы. Усложненные методы требуют меньшего числа операций, но сами операции более сложные, поэтому для небольших массивов простые методы более эффективны.

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

· сортировка методом «пузырька» (простого обмена);

· сортировка методом простого выбора (простой перебор);

· сортировка методом простого включения (сдвиг-вставка, вставками, вставка и сдвиг).

Сортировка методом «пузырька» (простого обмена)

Самый известный алгоритм – пузырьковая сортировка (bubble sort, сортировка методом пузырька или просто сортировка пузырьком). Его популярность объясняется интересным названием и простотой самого алгоритма.

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

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

Рис.1. Демонстрация сортировки по неубыванию методом «пузырька»

//Описание функции сортировки методом "пузырька"

void BubbleSort (int k,int x[max]) {

int i,j,buf;

for (i=k-1;i>0;i--)

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

if (x[j]>x[j+1]) {

buf=x[j];

x[j]=x[j+1];

x[j+1]=buf;

}

}

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

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

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

//Описание функции шейкер-сортировки

void Shaker(int k,int x[max]){

int i,t;

bool exchange;

do {

exchange = false;

for(i=k-1; i > 0; --i) {

if(x[i-1] > x[i]) {

t = x[i-1];

x[i-1] = x[i];

x[i] = t;

exchange = true;

}

}

for(i=1; i < k; ++i) {

if(x[i-1] > x[i]) {

t = x[i-1];

x[i-1] = x[i];

x[i] = t;

exchange = true;

}

}

} while(exchange);

//сортировать до тех пор, пока не будет обменов

}

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

Сортировка методом простого выбора (простой перебор)

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

Шаги алгоритма:

1. находим минимальное значение в текущей части массива;

2. производим обмен этого значения со значением на первой неотсортированной позиции;

3. далее сортируем хвост массива, исключив из рассмотрения уже отсортированные элементы.

Рис.2. Демонстрация сортировки по неубыванию методом простого выбора

//Описание функции сортировки методом простого выбора

void SelectionSort (int k,int x[max]) {

int i,j,min,temp;

for (i=0;i<k-1;i++) {

//устанавливаем начальное значение минимального индекса

min=i;

//находим минимальный индекс элемента

for (j=i+1;j<k;j++){

if (x[j]<x[min])

min=j;

//меняем значения местами

}

temp=x[i];

x[i]=x[min];

x[min]=temp;

}

}

Как и в пузырьковой сортировке, внешний цикл выполняется раз, а внутренний – в среднем раз. Следовательно, сортировка методом простого выбора требует

сравнений. Таким образом, это алгоритм порядка , из-за чего он считается слишком медленным для сортировки большого количества элементов. Несмотря на то, что количество сравнений в пузырьковой сортировке и сортировке простым выбором одинаковое, в последней количество обменов в среднем случае намного меньше, чем в пузырьковой сортировке.

Сортировка методом простого включения (сдвиг-вставка, вставками, вставка и сдвиг)

Хотя этот метод сортировки намного менее эффективен, чем сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:

· прост в реализации;

· эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;

· эффективен на наборах данных, которые уже частично отсортированы;

· это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);

· может сортировать массив по мере его получения;

· не требует временной памяти, даже под стек.

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

Рис.3. Демонстрация сортировки по неубыванию методом простого включения

//Описание функции сортировки методом простого включения

void InsertSort (int k,int x[max]) {

int i,j, temp;

for (i=0;i<k;i++) {

//цикл проходов, i - номер прохода

temp=x[i];

//поиск места элемента

for (j=i-1; j>=0 && x[j]>temp; j--)

x[j+1]=x[j];//сдвигаем элемент вправо, пока не дошли

//место найдено, вставить элемент

x[j+1]=temp;

}

}

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

Дата добавления: 2014-01-20