Сортировка выбором

Сортировка

Сортировка – один из наиболее сложных и важных для изучения алгоритмов.

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

Во-вторых, многие алгоритмы сортировки являются интересными примерами программирования, демонстрирующих важные методы: частное упорядочивание, рекурсия, объединение списков, сохранение двоичных деревьев в массивах.

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

Сортировка – одна из немногих задач с точными теоретическими границами производительности. Любой алгоритм сортировки, который использует сравнения, занимает по крайней мере, O(N*logN) времени.

Сортировка выбором – это простой алгоритм O(N²). Его задача – искать наименьший элемент, который затем меняется местами с элементом из начала списка. Затем находится из оставшихся элементов и меняется местами со вторым элементом. Процесс продолжается до тех пор, пока все элементы не займут свое конечное положение.

2 4 5 3 10 8 1

a₁ a₂ a₃ a₄ a₅ a₆ a₇

1. Определяется наименьший элемент a₇=1
2. Меняется местами с первым 1 4 5 3 10 8 2
3. В оставшемся снова ищется минимальный и меняется со вторым 1 2 5 3 10 8 4
4. и т. д.

1 2 3 5 10 8 4
1 2 3 4 10 8 5
1 2 3 4 5 8 10
1 2 3 4 5 8 10

Всего проходов n-1.

При поиске i-го наименьшего элемента алгоритм должен проверить каждый из N-I оставшихся. Время выполнения алгоритма равно N+(N-1)+(N-2)+…+1 или O(N²).

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

If a(j) < Min Then

Min = a(j)

k_min = j

End If

Если список отсортирован в обратном порядке, условие a(j) < Min выполняется большую часть времени. Во время первого прохода через список элементов, оно будет истинно для всех элементов, потому что каждый элемент меньше, чем предыдущий. Программа выполняет сравнение много раз, что приводит к некоторому замедлению работы алгоритма.

Это не самый быстрый алгоритм, но он очень прост, а также быстро сортирует небольшие списки.