Алгоритм пузырька

Простые алгоритмы сортировки.

И в эту переменную записан указатель на выделенную с помощью оператора new память под n элементов типа ElemType, где n некоторое натуральное число.

Краткое описание алгоритмов сортировки.

Теоретическая часть.

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

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

Предположим, что имеется следующее описание на языке C++:

typedef <тип элемента> ElemType;

ElemType *Ar;

При выполнении сортировки важным действием является обмен двух элементов в массиве. Это действие можно выполнить следующим образом.

Пусть необходимо обменять i и j элементы массива Ar. Для этого следует выполнить такие действия:

tmp = Ar[i];

Ar[i] = Ar[j];

Ar[j] = tmp;

где tmp – вспомогательная переменная, тип которой совпадает с типом элемента массива.

Также следует обратить внимание, что в случае выполнения операции целочисленного деления на 2, ее следует заменять сдвигом вправо на 1 разряд (операция >>) что приводит к повышению быстродействия программы.

Эти алгоритмы отличаются следующими особенностями:

1. В среднем невысокой эффективностью для работы с массивами, когда нет априорных данных об отсортированности элементов.

2. Наличием 2-ух циклов: внешнего и внутреннего (предположим, что внешний цикл имеет счетчик i, а внутренний – j).

3. Простотой алгоритма.

4. Неплохой эффективностью при работе со спискообразными структурами, т.е. со структурами данных, которые характеризуются последовательным доступом к элементам.

К простым алгоритмам сортировки относятся алгоритмы пузырька, минимумов (максимумов) и вставок.

Рассмотрим эти 3 алгоритма.

Суть этого алгоритма состоит в следующем: на каждом шаге внешнего цикла выбирается очередной элемент неотсортированной части массива (от 0-ого до n – 2-ого). Внутренний цикл осуществляет поочередное сравнение текущего и следующего элемента. Если текущий элемент больше следующего, то происходит обмен элементов местами. Внутренний цикл перебирает элементы от 0-ого до n – i – 1 - ого.

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

Алгоритм минимумов (максимумов).

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

Внешний цикл перебирает элементы от 0-ого до n – 2 – ого. Внутренний цикл перебирает элементы от i +1–ого до n - 1-ого - сортировка минимумами или от 0-ого до n – i – 2–ого – сортировка максимумами.

Алгоритм минимумов – максимумов.

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

Соответственно, счетчик внешнего цикла перебирает значения индексов только до середины массива.

Дата добавления: 2017-01-14