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


 

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

29134. Отступное в гражданском праве 29.5 KB
  По какимлибо причинам вы ничем кроме честного слова должника свой договор не обеспечили. Пришел час расплаты а денег у должника нет. Первый подать в суд потребовать продажи имущества должника и обязать его расплатиться с вами деньгами вырученными от продажи его имущества. Получив имущество вы отступаете от должника со своими требованиями о возврате долга.
29135. Прекращение обязательства зачетом. Недопустимость зачета 27 KB
  Обязательство прекращается полностью или частично зачетом встречного однородного требования срок которого наступил либо срок которого не указан или определен моментом востребования. Не допускается зачет требований: если по заявлению другой стороны к требованию подлежит применению срок исковой давности и этот срок истек; о возмещении вреда причиненного жизни или здоровью; о взыскании алиментов; о пожизненном содержании; в иных случаях предусмотренных законом или договором. Зачет производится если требование возникло по основанию...
29136. Новация 26 KB
  Новация. Новация обязательство прекращается соглашением сторон о замене первоначального обязательства существовавшего между ними другим обязательством между теми же лицами предусматривающим иной предмет или способ исполнения. Новация не допускается в отношении обязательств по возмещению вреда причиненного жизни или здоровью и по уплате алиментов. Новация прекращает дополнительные обязательства связанные с первоначальным если иное не предусмотрено соглашением сторон.
29137. Понятие и виды договоров. Существенные условия договора 29.5 KB
  Существенные условия договора. К договорам применяются правила о двух и многосторонних сделках. Граждане и юридические лица свободны в заключении договора. Условия договора определяются по усмотрению сторон.
29138. Толкование договора 22 KB
  Толкование договора. Форма договора закрепляет и правильно отражает согласованное волеизъявление участников договора. Форма для того и нужна чтобы правильно выражать и закреплять согласованное волеизъявление всех участников этого договора. Но как бы тщательно стороны при заключении договора ни работали над смыслом договора всетаки иногда встречаются определенные сложности в выявлении смысла этого договора и тех условий на которых заключен договор.
29139. Заключение договора. Заключение договора в обязательном порядке. Заключение договора на торгах 26.5 KB
  Заключение договора. Заключение договора в обязательном порядке. Заключение договора на торгах. Основные положения о заключении договора Договор считается заключенным если между сторонами в требуемой в подлежащих случаях форме достигнуто соглашение по всем существенным условиям договора.
29140. Оферта и ее виды 25 KB
  Офертой признается адресованное одному или нескольким конкретным лицам предложение которое достаточно определенно и выражает намерение лица сделавшего предложение считать себя заключившим договор с адресатом которым будет принято предложение.
29141. Акцепт и его виды 24.5 KB
  Акцептом признается ответ лица которому адресована оферта о ее принятии. Акцепт должен быть полным и безоговорочным. Молчание не является акцептом если иное не вытекает из закона обычая делового оборота или из прежних деловых отношений сторон. Виды акцепта: вексельный банковский чековый по ценным бумага.
29142. Основания, порядок и последствия изменения и расторжения договора 29 KB
  Основания порядок и последствия изменения и расторжения договора. Изменение и расторжение договора возможны по соглашению сторон. По требованию одной из сторон договор может быть изменен или расторгнут по решению суда только: В случае одностороннего отказа от исполнения договора полностью или частично когда такой отказ допускается законом или соглашением сторон договор считается соответственно расторгнутым или измененным. Соглашение об изменении или о расторжении договора совершается в той же форме что и договор.