АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Быстрая сортировка

Читайте также:
  1. Кристэл – Экстраординарно быстрая демонесса - Мертвяк
  2. МЕДИЦИНСКАЯ СОРТИРОВКА.
  3. Медсортировка и эвакуация.
  4. Обменная поразрядная сортировка
  5. Сортировка бинарными вставками
  6. Сортировка и фильтрация данных.
  7. Сортировка массивов. Поиск элемента массива.
  8. Сортировка почты (это рациональнее, чем сразу отвечать на все письма)

(обменная сортировка с разделением)

 

Это улучшенный метод, основанный на принципе обмена. Неожиданно оказалось, что усовершенствованный «пузырёк» даёт лучший результат из всех известных до настоящего времени методов сортировки. Он обладает столь блестящими характеристиками, что его изобретатель Хоар окрестил его “быстрой сортировкой”, QuickSort (1962г.).

В методе Бетчера последовательность сравнений предопределена; она не зависит от фактического состояния файла (т.е. от того, насколько он уже упорядочен). Разумно предположить, что метод сортировки будет эффективнее, если последовательность сравнений элементов зависит от результатов предыдущих сравнений (т.е. будет учитываться состояние файла).

Q-sort основана на том факте, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях.

Алгоритм.

массив

     

 

i=1 → ← j=N

 

Пусть имеются два указателя i и j. Причём вначале: i=1, j=N.

Сравним k i и k j (k i: k j).

Если обмен не нужен, то уменьшаем j на 1 и повторяем этот процесс.

После первого обмена увеличим i на 1 и будем продолжать сравнения, увеличивая i, пока не произойдёт ещё один обмен, тогда уменьшим j и т.д., пока не станет i=j. К этому моменту запись Ri(Rj) займёт свою окончательную позицию, и исходный файл будет разделён на два подфайла:

(R1,…Ri -1)Ri(Ri+1,…,Rn).

Эти подфайлы надо сортировать независимо (тем же методом).

В процессе сортировки образуется множество подфайлов, которые можно сортировать параллельно, независимо друг от друга.

Если подфайлы будут образовываться последовательно, то информация о неотсортированных подфайлах сбрасывается в стек. При этом целесообразно при образовании двух подфайлов в стек скидывать больший из них.

Каждый из подфайлов сортируют методом Q-sort за исключением очень коротких.

 

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)