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


 

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

12020. Финансовое состояние кредитной организации - ОАО КБ «Спутник» 560 KB
  Содержание Введение 1. Теоретические основы оценки финансового состояния кредитной организации 1.1 Сущность оценки финансового состояния кредитной организации 1.2 Методы оценки финансового состояния кредитной организации 1.3 Экономическая эффективность деятел...
12021. Финансовые аспекты деятельности Фонда социального страхования РФ (на примере Воронежского регионального отделения Фонда) 116.87 KB
  2 ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА НА ТЕМУ: Финансовые аспекты деятельности Фонда социального страхования РФ на примере Воронежского регионального отделения Фонда СОДЕРЖАНИЕ Введение 1 Теоретические основы финансов Фонда социального стр
12022. Основы банковского дела 786.5 KB
  Т.М. Иванова Основы банковского дела Учебно-методический комплекс Челябинск Содержание Методические указания 3 Тема 1. История возникновения и развития банков
12023. Виды банковских услуг и проблемы их развития 794 KB
  В настоящее время происходит изменение структуры дохода коммерческих банков. Пора получения сверхвысоких прибылей от спекулятивных операций на рынке про
12024. Пример проведения оценки финансового состояния коммерческого банка с точки зрения рейтинговой системы CAMEL(S) 739.5 KB
  PAGE 7 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 EMBED Equation.3 ВВЕДЕНИЕ Наблюдавшаяся в последнее десятилетие нестабильность мировых финансовокредитных отно
12025. Регулирования информационных и телекоммуникационных рисков на примере ОАО АКИБАНК 750.5 KB
  Содержание Введение 1.Банковские риски роль и место риска использования информационных и телекоммуникационных систем в кредитных организациях РФ 1.1 Понятие и сущность операционного риска 1.2 Управление банковскими рисками 2. Оценка и анализ рисков использов
12026. Банкротство и санация банков: целевые приоритеты и методы реализации 564.5 KB
  ДИПЛОМНАЯ РАБОТА На тему: Банкротство и санация банков: целевые приоритеты и методы реализации СОДЕРЖАНИЕ ВЕДЕНИЕ Несостоятельность банкротство кредитной организации Развитие законодательства о банк...
12027. Інфляція: суть, причини та соціально-економічні наслідки 633.5 KB
  КУРСОВА РОБОТА З дисципліни: Політична економія На тему: Інфляція: суть причини та соціальноекономічні наслідки І. Вступ Перехід нашої економіки на ринкові відносини різко підвищив значення грошей. Проблеми грошового господарства с
12028. Анализ действующей практики предоставления услуг коммерческими банками в Республики Казахстан 670 KB
  СОДЕРЖАНИЕ ВВЕДЕНИЕ Теоретические аспекты предоставления услуг коммерческими банками Сущность банковских услуг и продуктов Классификация банковских услуг Анализ действующей практики предоставления услуг коммерческ