XIV Международная студенческая научная конференция Студенческий научный форум - 2022

Идея метода сортировки выбором состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке. Следуя этой идее, будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n-1 последовательных шагов, начиная от нулевого и заканчивая (n-2)-м. На i-м шаге выбираем наименьший из элементов a[i] ... a[n-1] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на Рис.1

Результаты работы алгоритма сортировки выбором (Рис.1)

Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] (на Рис.2 она выделена серым) является упорядоченной. Таким образом, на (n-2)-м шаге вся последовательность, кроме a[n-1] оказывается отсортированной, а a[n-1] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.

Анализ и определение асимптотической оценки временной сложности

Анализ сортировки выбором. Во внутреннем цикле алгоритма SelecSort (См. Рис. 1) выполняется одно сравнение и, в зависимости от результата этой операции либо одна операции присваивания, предназначенная для сохранения текущего найденного минимума, либо ни одной. Во внешнем цикле алгоритма выполняются три операции присваивания, обеспечивающие перестановку элементов.

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

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

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

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

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

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

Иллюстрация неустойчивости сортировки выбором (Рис.2)

Алгоритм сортировки выбором представлен на рисунке 3.

Алгоритм сортировки выбором (Рис.3)

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

Листинг 1.

#include<iostream>

usingnamespace std;

void SelectSort(int* a, intn);

int _count = 0;

int main() {

int n;

cout <<"Enter size array : ";

cin >> n;

int* a = newint[n];

cout <<" Enter:\n";

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

cout <<"a["<< i <<"] = ";

cin >> a[i];

}

SelectSort(a,n);

cout << endl;

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

cout <<"a["<< i <<"] = "<< a[i] << endl;

}

}

void SelectSort(int* a, intn) {

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

int k = i, min = a[i];

for (int j = i + 1; j < n; j++) {

if (a[j] < min) {

k = j;

min = a[j];

}

}

a[k] = a[i];

a[i] = min;

}

}

Запустим нашу программу на выполнение, введем данные и убедимся в правильности полученных результатов (См. Рис.4).

Результаты работы программы (Рис.4)

Вывод: В представленной работе выполнено описание алгоритма сортировки выбором, проведён его анализ и определена асимптотическая оценка его временной сложности.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

применение :

учебное пособие / Д.В. Шагбазян, А.А. Штанюк, Е.В. Малкина .–

Нижний Новгород: Нижегородский госуниверситет, 2019. – 42 с.

Алгоритмы сортировки. Анализ, реализация, применение :

учебное пособие / Д.В. Шагбазян, А.А. Штанюк, Е.В. Малкина .–

Нижний Новгород: Нижегородский госуниверситет, 2019. – 42 с.

Алгоритмы сортировки. Анализ, реализация, применение: учебное пособие/Д.В. Шагбазян, А.А. Штанюк, Е.В. Малкина.- Нижний Новгород: Нижегородский госуниверситет, 2019. – 42с.

Гамма, Э. Приёмы объектно-ориентированного проектирования. Паттерны проектирования / Гамма Э., Хелм Р., Джонсон Р., Влассидес Дж. – СПБ.: Питер, 2015. – 368 с.

Код для цитирования: Скопировать