Подразделы

Другие разделы

Дата и время

09/04/2025 22:13:36

Авторизация

Зарегистрироваться
Восстановить пароль

Методы грубой силы

Идея методов грубой силы Последовательный поиск Исчерпывающий перебор Сортировки методом грубой силы

Сортировки методом грубой силы

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

Рассмотрим задачу сортировки, которая заключается в следующем: дан список из $n$ элементов (чисел или символьных строк), которые надо разместить в неубывающем порядке.

Сортировка выбором основана на определении упорядоченного списка – первым элементом в нём должен быть наименьший элемент среди элементов исходного списка, следующим – наименьший элемент среди оставшихся $n-1$ элементов и т.д.

Поэтому мы начинаем сортировку выбором с поиска наименьшего элемента в списке и обмена его с первым элементом (таким образом, наименьший элемент помещается в окончательную позицию в отсортированном списке). Затем мы сканируем список, начиная со второго элемента, в поисках наименьшего среди оставшихся $n-1$ элементов и обмениваем найденный наименьший элемент со вторым, т.е. помещаем второй наименьший элемент в окончательную позицию в отсортированном списке. В общем случае, на $i$ -ом проходе по списку ( $0 <= i <= n-2$ ) алгоритм ищет наименьший элемент среди последних $n-i$ элементов и обменивает его с $A_i$ .

	$\ darr bar { quad quad quad quad } darr$
$A_0 <= A_1 <= ... <=A_{i-1}$	\| $A_i, ..., A_{mi n}, ..., A_{n-1}$
$"Элементы в окончательных позициях"$	$quad "Последние " n-i " элементов"$

После выполнения $n-1$ проходов список оказывается отсортирован.

Алгоритм SelectionSort( $A$ )
// Входные данные: Массив $A[0...n-1]$
// Выходные данные: Массив $A[0...n-1]$ ,
// отсортированный в неубывающем порядке
for $i in [0...n-2]$ do
$quad m larr i$
$quad$ for $j in [i + 1...n-1]$ do
$quad quad$ if $A[j] < A[m]$
$quad quad quad quad m larr j$
$quad "Обмен " A[i] " и " A[m]$

Анализ сортировки выбором выполняется достаточно просто. Размер входных данных определяется количеством $n$ элементов в списке. Основной операцией алгоритма является сравнение элементов $A[j] < A[m]$ . Общее количество сравнений зависит только от размера массива и определяется следующей суммой:

$C(n)=sum_{i=0}^{n-2} sum_{j=i+1}^{n-1} 1 = {n(n-1)}/2 in Theta(n^2)$

Заметим, что количество обменов элементов массива равно $n-1 in Theta(n)$ – один раз для каждой итерации цикла. Это особенность выделяет сортировку выбором среди многих других алгоритмов сортировки.

Пузырьковая сортировка

Другим способом применения грубой силы к задаче сортировки состоит в сравнении соседних элементов и их обмене, если они находятся не в надлежащем порядке. Неоднократно выполняя это действие, мы заставляем наибольший элемент ("пузырёк") "всплывать" к концу списка. Следующий проход приведет к "всплыванию" второго наибольшего элемента, и так до тех пор, пока после $n-1$ итерации список не будет полностью отсортирован, $i$ -й проход ( $0 <= i <= n-2$ ) пузырьковой сортировки можно представить следующей диаграммой:


$A_0, ..., A_j overset("?")(harr) A_{j+1}, ..., A_{n-i-1}$	\| $overarc(A_{n-i} <= ... <= A_{n-1})$
	$quad "Элементы в окончательных позициях"$

Алгоритм BubbleSort ( $A$ )
// Входные данные: Массив $A[0...n-1]$
// Выходные данные: Массив $A[0...n-1]$ ,
// отсортированный в неубывающем порядке
for $i in [0...n-2]$ do
$quad$ for $j in [0...n-2-i]$ do
$quad quad$ if $A[j] > A[j+1]$
$quad quad quad "Обмен " A[j] " и " A[j+1]$

Количество сравнений в данной версии пузырьковой сортировки одинаково для всех массивов размером $n$ . Оно представляется суммой, практически идентичной сумме для сортировки выбором:

$C(n)=sum_{i=0}^{n-2} sum_{j=0}^{n-2-i} 1 = {n(n-1)}/2 in Theta(n^2)$

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

Эта версия алгоритма может быть усовершенствована ценой достаточно скромных усилий. В частности, приведенную сырую версию пузырьковой сортировки можно улучшить, воспользовавшись следующим наблюдением: если при проходе по списку не сделано ни одного обмена, значит, список отсортирован, и выполнение алгоритма можно прекратить. Однако, хотя новая версия и выполняется быстрее для некоторых входных данных, в наихудшем и среднем случае она все равно принадлежит $Theta(n^2)$ .

Задания для практики

Устойчива ли сортировка выбором? Устойчива ли пузырьковая сортировка?
Является ли реализация пузырьковой сортировки для связных списков столь же эффективной, что и для массивов?

Назад