Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Пузырьковая сортировка
|
|
Алгоритмы Сортировки. Часть 1
Все из существующих ныне способов сортировки отличаются друг от друга по скорости выполнения, понятности и длине кода, по красоте решения. Зачастую в код уже разработанного алгоритма вносятся какие-либо изменения и так возникает множество решений, некоторые и с которых мы и попробуем сейчас рассмотреть.
Однако, следует отметить что изучение алгоритмов совсем не лёгкая задача, здесь требуется внимательное рассмотрение каждой строчки. Конечно если Вы воспользуетесь кнопками Ctrl+C и Ctrl+V Ваша программа не станет хуже работать, но на мой взгляд, нет ничего хуже когда программист сам до конца не понимает, как работает его программа.
Итак, начнём.
Сортировка выбором
И начнём мы с сортировки выбором. Хотя этот алгоритм и не является самым быстрым, но я решил начать с него потому что, на мой взгляд он наиболее прост для понимания. Суть алгоритма состоит в том, что бы в исходном массиве найти наименьший элемент, а затем поменять местами первый элемент в списке с найденным. После того, находиться наименьший их оставшихся и меняется со вторым элементом. И так до тех пор пока весь список не будет отсортирован.
Таким образом понадобиться N+(N-1)+(N-2)+...+1 или N*N проходов чтобы отсортировать список.
| Листинг 1.Сортировка выбором |
| procedureSellectionSort(vara: arrayof integer; min, max: Integer); var i, j, best_value, best_j: longint; begin fori: =min tomax do begin best_value: =a[i]; best_j: =i; forj: =i+1 tomax do begin ifa[j]< best_value then begin best_value: =a[j]; best_j: =j; end; end; a[best_j]: =a[i]; a[i]: =best_value; end; end; |
Переменными min и mах можно ограничить область списка в которой, будет выполнена сортировка. Что бы отсортировать весь массив необходимо записать следующее
| Листинг 2.Код Delphi/Pascal |
| SellectionSort(a, 0, high(a)); |
Сортировка вставкой
Это тоже предельно простой для понимания алгоритм. Идея в том что бы создать новый массив, а затем последовательно вставлять в новый массив элементы из старого массива, чтобы созданный массив был всё время упорядоченным.
| Листинг 3.Сортировка вставкой |
| procedureInsertionSort(vara: arrayof integer; N: integer); var B: array[0..10000] of integer; i, j: integer; begin fori: =0 toN do begin j: =i; while(j> 1) and (B[j-1]> A[i]) do begin B[j]: =B[j-1]; j: =j-1; end; B[j]: =A[i]; end; fori: =0 toN do A[i]: =b[i]; end; |
Если внимательно посмотреть на реализацию алгоритма, то сразу же заметим что для его выполнения необходимо больше,, чем N*N проходов, поэтому в приложениях, где скорость выполнения кода критична, подобный алгоритм использовать не актуально.
Пузырьковая сортировка
Чаще всего используется для сортировки частично упорядоченных списков, так как именно для них скорость выполнения максимальна и может равняться O(N), где N количество элементов массива, а O время одного прохода через цикл. Этот алгоритм в исходном списке ищет пары цифр, которые следуют не по порядку и затем меняет их местами.Процесс повторяется до тех пор пока весь список не будет отсортированным. На рисунке изображен пример сортировки данным методом.
На рисунке можно проследить за перемещение элемента, который изначально был ниже чем после сортировки. Во время прохода цикла, элемент изменяет свою позицию на одну позицию ближе к своему конечному месту. На рисунке элемент двигается к вершине, как пузырёк воздуха к поверхности воды. Этот эффект и дал название алгоритму пузырьковой сортировке.
| Листинг 4.Пузырьковая сортировка |
| procedureBubbleSort(vara: arrayof integer; min, max: Integer); var i, j, tmp: integer; begin fori: =min tomax do forj: =min tomax-i do ifA[j]> A[j+1] then begin {Обмен элементов} tmp: =A[j]; A[j]: =A[j+1]; A[j+1]: =tmp; end; end; |