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


 

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

82344. Проект реконструкции участка диагностики автосервиса с целью увеличения количества обслуживаемых клиентов 1.31 MB
  Цель дипломного проекта заключается в реконструкции участка диагностики связанной с совершенствованием технологического процесса внедрением нового оборудования улучшением условий труда с целью увеличения количества обслуживаемых клиентов...
82345. Технология приготовления скомплектованного обеда из трех блюд 2.6 MB
  Неотъемлемой частью культуры каждого народа является кухня. Недаром этнографы начинают исследование жизни любого народа с изучения его кухни, ибо в ней в концентрированном виде отражается история, быт и нравы народа. Русская кухня в этом смысле не исключение, она так же является частью нашей культуры, нашей истории.
82346. Манипулятивный потенциал бренда в рекламной коммуникации (на примере деятельности LTD IKEA) 470 KB
  Актуальность темы данного дипломного проекта заключается в том, что для успешного развития бизнеса необходимо понимать изменение в массовой психологии восприятия, а так же уметь использовать этот фактор. В современном обществе, перенасыщенном информацией, становится все сложнее донести сообщение до потенциального...
82347. Специфика психолого-педагогической диагностики детей 5-7 лет с нарушениями зрения в условиях ПМПК 370.5 KB
  В этом возрасте к ребенку уже предъявляется система внешне нормированных требований, как к социальному индивиду. В данном случае речь идет о социально-психологическом аспекте адаптации, которая служит, с одной стороны, довольно точным индикатором различных дефицитов и отклонений в развитии...
82348. Совершенствование кадровой политики ООО «Колинз Ритейл» 1.26 MB
  Для сферы управления персоналом характерно наличие специфического понятийного аппарата отличительных характеристик и показателей деятельности специальных процедур и методов аттестации эксперимента и других; методов изучения и направления анализа содержания труда различных категорий персонала.
82349. Содержание и психологическая характеристика представлений гагаузских первоклассников о России 574.18 KB
  Представления накладывают отпечаток на весь процесс психического развития. Так немецкий психолог Вильям Штерн определял представления детей 6лет как конгломерат впечатлений в котором смешиваются объективные и аффективные моменты опыта ребёнка указывал что образ возникающий при взаимодействии ребёнка...
82350. Способы образования бизнес-терминов в русском языке и особенностей их функционирования 73.36 KB
  Исследование различных терминосистем способствует совершенствованию русской терминологии в целом выявлению общих закономерностей развития терминологических единиц в системе современного русского языка. Материалом исследования послужили лексические единицы взятые из печатных и электронных словарей...