Сортировка посредством выбора

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

На i-м этапе сортировки выбирается запись с наименьшим ключом среди записей A[i], ..., А[n] и меняется местами с записью А[i]. В результате после i-го этапа все записи А[1], ..., A[i] будут упорядочены. Сортировку посредством выбора можно описать следующим образом:

for i: = 1 to n - 1 do

выбрать среди A[i], ..., А[n] элемент с наименьшим ключом и поменять его местами с А[i];

Более полный код, реализующий этот метод сортировки, приведен в ниже

for(int i=0;i<len-1;i++)

{

int min=i;

for(int j=i+1;j<len;j++)

{

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

min=j;

}

if(a[min]!=a[i]) /* эта проверка делается только в устойчивых реализациях */

exch(a[i],a[min]);

}

Временная сложность

Наконец, рассмотрим сортировку посредством выбора. Легко проверить, что внутренний цикл требует времени порядка 0(п —i), поскольку j здесь изменяется от (i + 1) до п. Поэтому общее время выполнения алгоритма составляет с*∑_i=1^n-1 (п - i) для некоторой константы с. Эта сумма, равная с*п*(п - 1)/2, имеет порядок роста 0(п²). С другой стороны, нетрудно показать, что c*п(п-1)/2 независимо от начального списка сортируемых элементов. Поэтому сортировка посредством выбора требует времени не менее O(n²) в худшем, в лучшем и в среднем случае.

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

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

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

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

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

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

Минусом же является высокая сложность алгоритма: O(n²).

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

Вот алгоритм, реализующий этот процесс:

Вход: массив A, состоящий из элементов A[1], A[2], ..., A[n]

for i = 2, 3, ..., n:

newElement := A[i]

location := i - 1

while location >= 1 and A[location] > newElement:

A[location + 1] := A[location]

location := location - 1

A[location + 1] := newElement

Этот алгоритм заносит новое вставляемое значение в переменную newElement. Затем он освобождает место для этого нового элемен­та, подвигая (в цикле while) все большие элементы на одну позицию в массиве. Последняя итерация никла переносит элемент с номером location+1 в позицию location+2. Это означает, что позиция location+1 освобождается для «нового» элемента.

Анализ наихудшего случая

Если посмотреть на внутренний цикл while, то видно, что наиболь­шее количество операций выполняется в случае, если вновь добавляе­мый элемент меньше всех элементов, содержащихся в уже отсортиро­ванной части списка. В этой ситуации выполнение цикла завершается, когда значение переменной location становится равным 0. Поэтому наибольшее количество работы алгоритм произведет, когда всякий но­вый элемент добавляется в начало списка. Такое возможно только, если элементы исходного списка идут в убывающем порядке. Это один воз­можный наихудший случай, однако бывают и другие.

Посмотрим, как происходит обработка такого списка. Первым вставля­ется второй элемент списка. Он сравнивается всего с одним элементом. Второй вставляемый элемент (третий по порядку) сравнивается с двумя предыдущими, а третий вставляемый элемент — с тремя предыдущи­ми; вообще, t-ый вставляемый элемент сравнивается с iпредыдущими, и этот процесс повторяется N — 1 раз. Таким образом, сложность сор­тировки вставками в наихудшем случае равна

W(N) = 0(N*).

Анализ среднего случая

Анализ среднего случая разобьем на два этапа. Сначала подсчита­ем среднее число сравнений, необходимое для определения положения очередного элемента. Затем среднее число всех необходимых опера­ций можно подсчитать, воспользовавшись результатом первого шага. Начнем с подсчета среднего числа сравнений, необходимых для опреде­ления местоположения 2-го элемента. Мы уже говорили о том.что до­бавление t-ro элемента к списку требует по крайней мере одного срав­нения даже, если элемент уже стоит на нужном месте.

Сколько существует возможных положений для г-ого элемента? Посмотрим на короткие списки и попробуем обобщить результат на произвольный случай. Для первого добавляемого элемента есть две возможности: он может оказаться первым или вторым в отсор­тированном списке из двух элементов. У второго добавляемого элемен­та три возможных положения: с номерами 1, 2 и 3. Оказывается, что t-ый добавляемый элемент может занимать одно из т + 1 возможных положений. Мы будем предполагать, что все эти возможности равно-вероятны.

Сколько требуется сравнений для того, чтобы добраться до каждой из г + I возможных позиций? Посмотрим снова на малые значения I и попробуем обобщить результат. Если четвертый добавляемый элемент попадает на позицию 5. то уже первое сравнение окажется ложным. Ес­ли правильная его позиция 4, то первое сравнение будет истинным, авторое — ложным. При попадании в позицию 3 первое и второе сравне­ние будут истинными, а третье — ложным. В позиции 2 первое, второе и третье сравнение оказываются успешными, а четвертое — нет. При попадании в первую позицию истинными будут первое, второе, третье и четвертое сравнения, а ложных сравнений не будет. Это означает, что для r-го элемента, попадающего на позиции t + 1. г, t: — 1, . . . , 2, число сравнений будет равно соответственно 1, 2, 3, .... г, а при по­падании на первую позицию число сравнений равно г. Среднее число сравнений для вставки i-го элемента дается равенством