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


 

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

82331. Образование Казахского ханства 29.72 KB
  Вхождение отдельных казахских племен в разные государства, войны и раздоры между родами и племенами стали преградой на пути их объединения в единую народность. Преодолеть эту раздробленность, политическую разобщенность выпало на долю султанов Жаныбека и Керея
82332. Состояние жизненного уровня трудящихся в 50-е гг. События в Темиртау (1958г.) 35.21 KB
  События в Темиртау 1958г. Особенно крупный взрыв недовольства произошел летом 1959 года в городе Темиртау. Строящийся в Темиртау металлургический комбинат был объявлен ударной комсомольской стройкой и до конца 1958 года в область прибыли 132 тыс. например из двух тысяч болгар трудившихся в Казахстане свыше половины работали в Темиртау.
82333. Политика Тауке хана. «Жеты Жаргы» – свод норм обычного права казахского народа 34.49 KB
  Изменения политической структуры вызвали настоятельную необходимость переработки и правовой базы организации казахского общества. и включал в себя следующие основные разделы: земельное право; семейнобрачные отношения; военная организация; суд и судебный процесс; виды наказаний по уголовным преступлениям; введение куна выкуп; наследственное право. Первое место в нем занимает закон возмездия: за кровь мстить кровью за увечье увечьем; За воровство грабеж насилие прелюбодеяние казнить смертью; По сим постановлениям родственники...
82334. Изменение в социальной структуре и численности населения в начале 50-х-сер.60-х годов 29.09 KB
  Доля рабочих среди трудоспособного населения была невелика. По официальным данным на 1940 год доля рабочих в Казахстане было 634 тысячи колхозников – 912 тысяч. Проблема нехватки рабочих рук была решена за счет приезжих которые составляли 80 от общего числа рабочих. В 1960 году численность рабочих составляла 22 млн человек колхозников – 611 тысяч.
82335. Освободительная борьба казахского народа против джунгарских завоевателей (Ордабасы, Анракай, годы «великого бедствия») 33.09 KB
  Еще более усилилась агрессия джунгар после создания ими государства. Джунгарское ханство занимавшее территорию между Китаем и Казахстаном было образовано в 1640 году. В 1204 году ойраты как сами назвали себя джунгары вошли в состав государства Чингисхана.
82336. Казахстан и мировое сообщество в конце 50-х-сер.60-х годов 29.45 KB
  В СССР 12 марта 1951 года принят закон о защите мира пропаганда войны объявлялась тягчайшим преступлением против человечества. Осенью 1959 года состоялись переговоры глав правительств СССР и США. Расширился между СССР и КНР культурный и торговый обмен. Тысячи китайцев получали высшее образование в СССР в том числе в вузах Казахстана.
82337. Хан Абылай и его место в истории казахского народа 28.98 KB
  Его дед тоже Абылай был владетелем города Туркестана прославился воинскими доблестями и получил грозное прозвище Канишер кровопийца. В 13 лет Абылай лишился отца убитого во время междоусобиц рано поступил на службу. Абылай понимал что главный враг Казахстана – джунгары поэтому стремится держать пророссийскую ориентацию.
82338. Казахстан в середине 60-х нач. 80-х годов. Социально-политическое развитие 30.01 KB
  Состав депутатов Верховного Совета СССР где были представлены чабаны колхозники рабочие промышленных предприятий техническая интеллигенция люди науки и искусства партийные и хозяйственные руководители и служил якобы подтверждением этой новой общественнополитической ситуации в обществе. Группа деятелей высшего политического руководства СССР в глубокой тайне подготовила смещение Н. Суслов и председатель КГБ СССР В. Смена политического руководства СССР в октябре 1964 года вскоре стала сказываться и на состоянии культуры.
82339. Восстание Кенесары Касымова (причины, характер, движущие силы, итоги) 27.95 KB
  Движущие силы численность: все слои населения – крестьянешаруа бии батыры султаны 20 тысяч человек все слои населения – крестьянешаруа бии батыры султаны Ход восстания: осень 1837 – организация отрядов повстанцев; начало открытого сопротивления царскому правительству; весналето 1838 – вооруженные столкновения с царскими отрядами нападение на аулы ненавистных султанов; разгром Акмолинской крепости отрядом Кенесары; увеличение отрядов перемещение центра восстания из Среднего в Младший жуз; 1840 – вторжение Кенесары в Кокандское...