Начало
Учебные материалы
Методы грубой силы
Идея методов грубой силы Последовательный поиск Исчерпывающий перебор Сортировки методом грубой силы
Сортировки методом грубой силы
Рассмотрим задачу
сортировки, которая заключается в следующем: дан список из `n` элементов
(чисел или символьных строк), которые надо разместить в неубывающем порядке.
Сортировка выбором основана на определении упорядоченного списка -- первым элементом
в нём должен быть наименьший элемент среди элементов исходного списка, следующим --
наименьший элемент среди оставшихся `n-1` элементов и т.д.
--
Поэтому мы начинаем сортировку выбором с поиска наименьшего элемента в списке
и обмена его с первым элементом (таким образом, наименьший элемент
помещается в окончательную позицию в отсортированном списке). Затем мы сканируем
список, начиная со второго элемента, в поисках наименьшего среди оставшихся
`n-1` элементов и обмениваем найденный наименьший элемент со вторым, т.е.
помещаем второй наименьший элемент в окончательную позицию в
отсортированном списке. В общем случае, на `i`-ом проходе по списку (`0 <= i <= n-2`)
алгоритм ищет наименьший элемент среди последних `n-i` элементов и обменивает его с `A_i`.
--
||.nodraw|| ` ` | `\ 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`) пузырьковой сортировки
можно представить следующей диаграммой:
||.nodraw|| ` ` | ` `
--:|:--
`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)`.
---
##### Задания для практики
1. Устойчива ли сортировка выбором? Устойчива ли пузырьковая сортировка?
2. Является ли реализация пузырьковой сортировки для связных списков столь же эффективной, что и для массивов?
