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


 

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

3604. Відношення і пропорції. 149.18 KB
  Тема. Відношення і пропорції. Мета: узагальнити і систематизувати знання учнів з теми; показати застосування математичних пропорцій у мистецтві та архітектурі;розвивати вміння застосовувати математику в проблемних ситуаціях; виховувати ерудова...
3605. КАЧЕСТВО САХАРА И ПУТИ ЕГО ПОВЫШЕНИЯ 4.64 MB
  Введение Увеличение производства сахара в мире, в том числе в Республике Беларусь, связано одновременно с возрастающими требованиями к его качеству. Имея отличные вкусовые качества и высокую калорийность, сахар является одним из самых важных пр...
3606. Водні ресурси України 8.51 MB
  Водні ресурси – це природне багатство, яке вимагає збереження і охорони особливо в теперішній час коли суспільство змінює свої погляди, розширює можливості. У сільськогосподарському виробництві використувується 72,2% території країни, а 57,5%...
3607. ВАНТАЖОПІДЙОМНА, ТРАНСПОРТУЮЧА ТА ТРАНСПОРТНА ТЕХНІКА 9.59 MB
  В посібнику описані сучасні конструкції вантажопідйомної, транспортуючої та транспортної техніки, яка використовується при переміщенні великої кількості вантажів в процесі виробництва в різних галузях народного господарства, в будівництві промислово...
3609. Банкротство предприятий и антикризисный менеджмент в современных российских условиях 887.5 KB
  Объективным процессом рыночной экономики, основанной на конкуренции, является постоянный переток капиталов в наиболее доходные сферы, перераспределение собственности от неэффективных хозяйствующих субъектов к эффективным. Осуществляется дан...
3610. Инженерная графика 9.34 MB
  Учебно-методическое пособие представляет базовый курс инженерной графики. Приводится необходимая информация для освоения курса инженерной графики и выполнения расчетно-графических работ. Содержатся основные положения нормативно-технической документа..
3611. Исследование некоторых эксплуатационных показателей трелевочных тракторов ОТЗ различной энергонасыщенности 8.82 MB
  Введение Основной задачей технического прогресса в лесозаготовительной промышленности на перспективный период является увеличение производительности труда за счет интенсификации общественного производства, т.е., за счет роста его энерговооруженности...