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


 

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

15233. Ғұрыптық фольклор лексикасы: идиоэтникалық 251.5 KB
  Қазақ тіл білімінде әсіресе соңғы жылдары көбірек көңіл бөліне бастаған антропоцентристік бағыттағы зерттеулердің нәтижесі этностың байырғы тұрмыс-тіршілігінің, қазіргі болмысы мен өткендегі өмір сүру тәжірибесінің, күнкөріс мәдениетінің, өзіндік ежелгі заттық және рухани құндылықтарының түрлі тілдік көріністері тек лексика мен фразеологияда ғана емес, ономасиологияда да
15234. Дискурс 46 KB
  Дискурс Дискурс ұғымы XX ғасырдың 70жылдарынан бастап философияда кеңінен қолданыла бастады. Тұңғыш болып дискурс ұғымын Ю. Хабермас өзінің Коммуникативтік компетенция теориясына дайындық атты еңбегінде қолданған болатын. Содан бері бұл термин батыстық философи...
15235. І.Есенберлиннің Көшпенділер романындағы жылқы атауларының этнолингвистикалық мәні 324 KB
  Еліміз егемендік алып, тіліміз мемлекеттік мәртебеге ие болуына байланысты қоғамда тарихи сана мен ұлттық таным көкжиегі кеңейе бастады. Осыған байланысты ұлттық рухани-мәдени мұраның тарихи маңызын саралап, қайта бағалау мүмкіндігі туып отыр
15236. Етістіктің лексика-грамматикалық сипаты 69 KB
  Етістіктің лексикаграмматикалық сипаты Етістік қазақ тіліндегі сөз таптарының ішіндегі ең күр делілерінің бірі. Оның күрделілігі лексикасемантикалық сипатынан грамматикалық формалары мен категорияларының көптігінен синтаксистік қізметінен айқын көрінеді. Е...
15237. Әбілғазы баһадүр ханның «Түркі шежіресіндегі» араб-парсы сөздерінің қолданылу ерекшелігі 277 KB
  Әбілғазы шығармасының тіл ғылымы үшін, оның ішінде түркітану ғылымы үшін маңызы зор екендігін Г.С.Саблуков өзінің аудармасының кіріспесінде былайша көрсетеді: «Исправно изданный Родословной был бы при скудости литературы на восточно-джагатайском наречии
15238. Әлем тілдерінің топтастырылуы 171.5 KB
  Әлем тілдерінің топтастырылуы Мазмұны 1. Тілдердің генеологиялық туыстық классификациясы. 2. Тілдердің типологиялық классификациясы. 5.1. Тілдердің генеологиялық туыстық классификациясы. Тілдердің генеологиялық ту...
15239. Әлемнің тілдік көрінісінің тіл мәдениетіндегі бейнесі 73.88 KB
  ӘЛЕМНІҢ ТІЛДІК КӨРІНІСІНІҢ ТІЛ МӘДЕНИЕТІНДЕГІ БЕЙНЕСІ О.Сапашев ШҚМУ Түркітану оқытуғылымизерттеу орталығының директоры филология ғылымдарының кандидаты Тілдің табиғилығы мен оның даму мәдениеті қадым заманнан бері көтеріліп келе жатқан мәселе бұл ұлт...
15240. Әңгімелеу мәтінінің тілдік-стилистикалық сипаты 283.5 KB
  Мәтін лингвистикасында зерттеуді аса қажет ететін маңызды мәселелердің бірі – әңгімелеу мәтінінің тілдік және стилистикалық ерекшелігін таныту. Әңгімелеу – тұтасым, байласым және мағыналық аяқталғандық, ақпарат беру категорияларына ие композициялық-сөйлеу формаларының бірі
15241. ИССЛЕДОВАНИЕ РАСПРЕДЕЛЕНИЙ СКОРОСТИ ПОТОКА НА ВХОДЕ В АКТИВНУЮ ЗОНУ РЕАКТОРА ВВЭР-1000, В УСЛОВИЯХ РАЗЛИЧНЫХ РАСХОДОВ ТЕПЛОНОСИТЕЛЯ В ОТДЕЛЬНЫХ ПЕТЛЯХ 1.23 MB
  Лабораторная работа №1 ИССЛЕДОВАНИЕ РАСПРЕДЕЛЕНИЙ СКОРОСТИ ПОТОКА НА ВХОДЕ В АКТИВНУЮ ЗОНУ РЕАКТОРА ВВЭР1000 В УСЛОВИЯХ РАЗЛИЧНЫХ РАСХОДОВ ТЕПЛОНОСИТЕЛЯ В ОТДЕЛЬНЫХ ПЕТЛЯХ Объект исследования: течение теплоносителя в кольцевом опускном тракте в части напорно...