53453

Оптимизация процедуры Quick_sort, особенности

Доклад

Информатика, кибернетика и программирование

Быстрая сортировка (англ. quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Русский

2014-04-01

22.82 KB

1 чел.

Оптимизация процедуры Quick_sort, особенности.

Быстрая сортировка (англ. quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известныйалгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году. Один из самых быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов).QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что в первую очередь производятся перестановки на наибольшем возможном расстоянии и после каждого прохода элементы делятся на две независимые группы.Общая идея алгоритма состоит в следующем:

  1. Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива.
  2. Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом — «меньшие опорного», «равные» и «большие».
  3. Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.На практике массив обычно делят не на три, а на две части, например, «меньшие опорного» и «равные и большие».

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

  1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить.
  2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный — справа от него. Обычный алгоритм операции:
  3. Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.
  4. Вычисляется индекс опорного элемента m.
  5. Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному.
  6. Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
  7. Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.

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

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

Особенности быстрой сортировки:

  1. Один из самых быстродействующих (на практике) из алгоритмов внутренней сортировки общего назначения.
  2. Прост в реализации.
  3. Требует лишь дополнительной памяти для своей работы. (Не улучшенный рекурсивный алгоритм в худшем случае памяти)
  4. Хорошо сочетается с механизмами кэширования и виртуальной памяти.


 

А также другие работы, которые могут Вас заинтересовать

12150. Модель 2-х процессорной системы 83.5 KB
  Лабораторная работа № 4 Модель 2х процессорной системы Блоксхема 2 процессорной системы Код отвечающий за моделирование: Memo2.Lines.Add Начало моделирования while flag0 do begin Memo2. Lines. AddinttostrTime {Проверка процессора 1 на наличие задач и решение з
12151. Форма расчёта равномерного и гиперекспоненциального распределения 474 KB
  Отчет по лабораторной работе № 12 Равномерное распределение распределение характеризующееся тем что вероятность любого интервала зависит только от его длины. Равномерное распределение выбирается когда предполагается что все варианты прогнозируемого показ
12152. КОМПОНЕНТЫ, ИСПОЛЬЗУЕМЫЕ ДЛЯ СВЯЗИ С БАЗАМИ ДАННЫХ 66 KB
  КОМПОНЕНТЫ ИСПОЛЬЗУЕМЫЕ ДЛЯ СВЯЗИ С БАЗАМИ ДАННЫХ Обзор компонентов используемых для связи с базами данных Компоненты Delphi используемые для работы с базами данных расположены в библиотеке компонентов на страницах Data Access доступ к данным и Data Control управл
12153. Знакомство с интегрированной средой Delphi 136 KB
  Лабораторная работа № 1 Знакомство с интегрированной средой Delphi Загрузка Delphi возможна одним из следующих способов: кнопка Пуск раздел Программы и далее в соответствии с названием программного продукта; ярлык на рабочем столе; быстрая кнопк
12154. СОЗДАНИЕ ОТЧЕТОВ. Система «Быстрый отчет» (Quick Report) 96.18 KB
  СОЗДАНИЕ ОТЧЕТОВ 6.1 Система Быстрый отчет Quick Report Для создания отчетов в Delphi включена система QuickReport все компоненты которой размещены на странице QReport палитры компонентов. Быстрый отчет использует генератор отчетов состоящий из множества полос. Полоса band э
12155. ПРОГРАММИРОВАНИЕ РАБОТЫ С БАЗАМИ ДАННЫХ 70.04 KB
  ПРОГРАММИРОВАНИЕ РАБОТЫ С БАЗАМИ ДАННЫХ Состояние набора данных Основным свойством компонента Table является свойство State определяющее состояние набора данных. Это свойство доступно только во время выполнения и только для чтения. Набор данных может находиться...
12156. ПРИЛОЖЕНИЯ С НЕСКОЛЬКИМИ СВЯЗАННЫМИ ТАБЛИЦАМИ 31.5 KB
  ПРИЛОЖЕНИЯ С НЕСКОЛЬКИМИ СВЯЗАННЫМИ ТАБЛИЦАМИ Рассмотрим принципы построения приложения с несколькими связанными друг с другом таблицами. 8.1 Связь головной и вспомогательной таблиц Две таблицы могут быть связаны друг с другом по ключу. Одна из этих связанных табл...
12157. ТИПЫ ПОЛЕЙ. НЕКОТОРЫЕ СВОЙСТВА ТАБЛИЦЫ 61.5 KB
  ТИПЫ ПОЛЕЙ. НЕКОТОРЫЕ СВОЙСТВА ТАБЛИЦЫ Типы полей реляционной базы данных Проектирование приложения работающего с базами данных предполагает наличие самих баз данных. Вместе с BDE в Delphi поставляется программа Database Desktop которая позволяет создавать таблицы ба...
12158. ОБЩЕЕ ПОНЯТИЕ О БАЗЕ ДАННЫХ. МОДЕЛИ ДАННЫХ. СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ 182.07 KB
  ОБЩЕЕ ПОНЯТИЕ О БАЗЕ ДАННЫХ. МОДЕЛИ ДАННЫХ. СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ База данных Всегда когда возникает потребность манипулирования большими массивами данных используются базы данных. В общем случае под данными понимается информация наход...