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


 

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

41465. Особенности учёта расчетов с учредителями 22.84 KB
  Расчеты с учредителями осуществляются по вкладам в уставный капитал, по выплате доходов и другим операциям. Учет ведется на активно-пассивном счете 75 «Расчеты с учредителями». Аналитический учет ведется по каждому учредителю
41466. Методы начисления амортизации основных средств и отражение ее в учете 53.98 KB
  Начисление амортизационных сумм осуществляется в порядке, установленном ст. 259 НК РФ. Амортизируемым имуществом признается имущество, результаты интеллектуальной деятельности и иные объекты интеллектуальной собственностисуда с выраженными в них государственновластными суждениями относительно разрешения материальноправовых и процессуальноправовых вопросов. Отличие судебного решения от определения: решение дает ответ по существу дела определение не разрешает дело а дает ответ на вопрос процессуальноправового характера п.12 постановление ВС О судебном решении не...
41467. Учет затрат на восстановление основных средств 25.08 KB
  Виды ремонта – текущий, средний и капитальный. Основным первичным документом, согласно которому определяются объем работ по капитальному ремонту, его продолжительность, сметная стоимость, является дефектная ведомость. Ремонт объектов ОС может быть проведен подрядным, хозяйственным или смешанным способом.
41468. Порядок проведения и учёт результатов инвентаризации основных средств и учёт их результатов 60.49 KB
  Основные средства — неотъемлемая часть имущества большинства организаций. В отношении таких объектов, как и любого другого имущества, должны быть обеспечены учет и контроль. Соответствие фактического наличия имущества данным бухгалтерского учета регулярно проверяется инвентаризацией. О методике проведения инвентаризации основных средств и оформлении ее результатов рассказывается в данной статье.
41469. Экономическое содержание, принципы, оценка и задачи учёта материально-производственных запасов 26.53 KB
  Понятие и сущность ОП установление фактов имеющих юридическое значение в ОП признание гражданина безвестно отсутствующим и объявление гражданина умершим признание гражданина ограниченно дееспособным или недееспособным ограничение или лишение несовершеннолетнего в возрасте от 14 до 18 лет права самостоятельно распоряжаться своими доходами. Отмена судом ограничения дееспособности Эмансипация Принудительная госпитализация гражданина в психиатрический стационар и принудительное освидетельствование семейный кодекс гражданский...
41470. Изучение организации и методики анализа выполнения сметы доходов и расходов бюджетного учреждения 168.34 KB
  Объектом исследования курсовой работы является смета доходов и расходов Бахчисарайского районного центра социальных служб для семьи, детей и молодежи. Предмет исследования – организация и методика анализа выполнения сметы доходов и расходов данного бюджетного учреждения
41471. Создание информационной системы управления заказами для МБУЗ ЦРБ 2.29 MB
  Провести анализ структуры предприятия и обосновать потребность создания для неёMRPсистемы; Рассмотреть существующие варианты реализации информационной системы; Произвести анализ из существующих средств разработки СУБД и сделать выбор для реализации информационной системы;
41472. РИМСКОЕ ПРАВО. Методические материалы 340.5 KB
  Настоящие методические материалы предназначены для подготовки к семинарским и практическим занятиям по дисциплине «Римское право» для студентов факультета внебюджетного образования (заочная форма обучения), обучающихся по направлению подготовки «Юриспруденция». Данная учебная дисциплина относится к вариативной части профессионального цикла
41473. Особенности сексуального поведения современной молодежи 106.8 KB
  В общем и целом, социологическое исследование является отправной точкой для определения общественного мнения по разным насущным и актуальным вопросам. Итоги подобных исследований зачастую используются для формирования стратегии регулирования культурных ценностей у разных социальных слоев общества.