53453

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

Доклад

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

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

Русский

2014-04-01

22.82 KB

2 чел.

Оптимизация процедуры 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. Хорошо сочетается с механизмами кэширования и виртуальной памяти.


 

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

25447. Тенденции изменения практики социальной работы в современном обществе 18.17 KB
  Такой теорией и является теория социальной работы что со всей очевидностью вытекает из ее характера как системы видов деятельности по защите слабых общественных групп. Теория социальной работы составляет органическую часть тех социологоориентированных и психологоориентированных теорий которые связывают социальную теорию в целом с прикладными исследованиями этого круга проблем. Учеб заведения по подготовке соц работников и возникла необходимость разработки теоретических основ СР.
25448. Основные современные государственные концепции и модели социальной работы 30.46 KB
  основные современные государственные концепции и модели социальной работы. Основные модели теоретического обоснования практики социальной работы отражают не только результаты научных поисков ученых разных школ но и ее эволюцию изменения в самом содержании и формах социальной работы. Каждая модель содержит некоторые теоретические положения связь со смежными науками о человеке и обществе естественными и социокультурными основами жизни а также предполагает вполне определенное содержание социальной работы методы и формы содействия...
25449. Психолого-ориентированные модели 18.08 KB
  Получили распространение в связи с тем что ее современная стратегия ориентирует соц.работников на то чтобы помочь клиентам оптимизировать собственные усилия по изменению ситуации возникшей на личностном и соц. Основные понятия психодинамической модели опирающиеся на психоанализ вошли в ранг категорий соц. Выполняет функцию универсальной технологии применяемой ко всем сферам соц.
25450. Надзор и контроль за соблюдением законодательства об охране труда 148.5 KB
  Контроль за состоянием охраны труда и его виды. Органы государственного надзора за охраной труда. Компетенция Госгорпромнадзора в сфере надзора и контроля за соблюдением законодательства об охране труда. Права и ответственность должностных лиц специально уполномоченного центрального органа исполнительной власти по надзору за охраной труда.
25451. Социальные перспективы и вариативность моделей социальной работы 19.29 KB
  Социальные перспективы и вариативность моделей социальной работы Основные модели теоретического обоснования практики соц.работы отражают не только результаты научных поисков ученых разных поколений но и ее эволюцию изменения в самом содержании и формах соц. Каждая модель содержит некоторые теоретические положения связь со смежными науками о человеке и обществе естественными социокультурными основами жизни а так же предполагает вполне определенное содержание соц. соц.
25452. ОРГАНИЗАЦИЯ ОХРАНЫ ТРУДА НА ПРЕДПРИЯТИИ 134 KB
  Обязанности работника и работодателя по охране труда. Финансирование охраны труда. Организация проведения медицинских осмотров. Служба охраны труда: основные задачи, компетенция. Комиссия по вопросам охраны труда предприятия: порядок создания, обязанности и права комиссии.
25453. Комплексно-ориентированные модели 18.17 KB
   Ролевая теория основа психологическое знание компоненты социологического знания. Соц.роль это поведение которое от человека ожидают люди при выполнении им соц. Ролевую игру соц.
25454. Применение теории систем в практике социальной работы 11.83 KB
  применение теории систем в практике социальной работы Теория систем и системные идеи в социальной работе восходят к общей теории социальных систем Р. В первоначальном своем варианте эта теория как известно была разработана на биологическом материале и доказывала что все организмы являются системами составленными из подсистем а сами они в свою очередь есть часть сверхсистем. В соответствии с основными положениями теории систем социальная система представляет собой не нечто целое а определенный набор абстракций из конкретных форм...
25455. Государственное управление охраной труда 104.5 KB
  Система управления охраной труда. Функции, задачи управления охраной труда. Основные принципы государственной политики в области охраны труда. Система органов государственного управления охраной труда. Полномочия КМУ в области охраны труда.