Студопедия

КАТЕГОРИИ:

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



Алгоритм. Быстрая сортировка использует стратегию «разделяй и властвуй»




Читайте также:
  1. A) Словесный, графический, формально - словесный, алгоритмический язык
  2. Алгоритм
  3. АЛГОРИТМ АНАЛИЗА ПЕДАГОГИЧЕСКОЙ СИТУАЦИИ
  4. Алгоритм БПФ.
  5. Алгоритм выбора лиц, принимающих решения
  6. Алгоритм выбора монтажного крана.
  7. Алгоритм выявления признаков преднамеренного банкротства
  8. Алгоритм действия мед. Сестры при проведении УВЧ терапии.
  9. Алгоритм действия медсестры при проведении УВЧ терапии.

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

1.Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.

2.Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции:

1. Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.

2. Вычисляется индекс опорного элемента m.

3. Индекс l последовательно увеличивается до тех пор, пока l-й элемент не превысит опорный.

4. Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.

5. Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.

6. Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.

3.Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.

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

"Быстрая сортировка", хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов.

Метод основан на подходе "разделяй-и-властвуй". Общая схема такова:

1. из массива выбирается некоторый опорный элемент a[i],



2. запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] - вправо,

3. теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого,

4. для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.

В конце получится полностью отсортированная последовательность.

Рассмотрим алгоритм подробнее.


Дата добавления: 2015-04-18; просмотров: 17; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2020 год. (0.004 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты