Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Алгоритм простого обмена (обменная сортировка)






Основан на обмене после сравнения пары соседних элементов. Перебор элементов осуществляется по всему массиву, начиная с последнего элемента. При этом на каждом шаге каждый раз всплывает на очередное место элементы сортировки. Иначе говоря, на каждом шаге «наиболее легкий» элемент не отсортированной части как бы всплывает. Именно поэтому этот метод называют методом «пузырька», или методом «камушка», т.к. после завершения просмотра всего массива самый «тяжелый» элемент займет свое законное место. Поэтому размер неотсортированной части можно уменьшить на единицу. Затем все начинается заново. Процесс завершается, когда при очередном просмотре не будет сделано ни одной перестановки.

На i –ом шаге делится на уже отсортированную и еще неотсортированную части. На каждом шаге один элемент переходит из неотсортированной части в отсортированную. i = 2… n.

 

Алгоритм:

procedure BubbleSort;

var i, j: integer; x: typel;

Begin

for i: =2 to n do

for j: = n downto 1 do

if a [ j ] < a [ j –1] then

Begin

x: = a [ j ];

a [ j ]: = a [ j –1];

a [ j –1]: = x;

end;

end;

Число сравнений . В худшем случае на одно сравнение имеется 3 перемещения.

Число перемещений:

T n = O (n 2) – общая оценка.

Алгоритм не реагирует на предварительную сортировку.

Улучшение метода пузырька за счет следующих моментов.

1. Алгоритм модифицированной пузырьковой сортировки.

Запомним место, где производится последний обмен шага, что позволит остановить просмотр элементов; на последнем месте перестановки все элементы до этого места отсортированы, если не произошло ни одной перестановки следовательно – последний уже отсортирован. Введем flag для отметки этого. Алгоритм реагирует на предварительную сортировку.

procedure BubbleSortMod;

var i, j: integer;

x: typel;

flag: boolean;

begin

flag: =false; i: =2;

while (i< =n) and (not flag) do

begin

flag: =true;

for j: =n downto i do

if a[j] < a[j–1] then

begin

x: =a[j]; a[j]: = a[j–1]; a[j–1]: =x;

flag: =false;

end;

i: =i+1;

end;

end;

2. Шейкерная сортировка

Если учесть, что наименьший элемент из конца последовательности всплывет на нужное место за один проход, а самый больший элемент от начала последовательности встанет на свое место за n –1 шаг, то меняя направление прохода (назад, вперед) можно улучшить алгоритм сортировки. При этом на каждом шаге фиксируется место перестановки. Данный метод называется Шейкер–сортировка:

Недостатком является то, что сравнение и перемещение на соседние элементы.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.