4876

Быстрая сортировка и способы ее реализации в программировании

Лекция

Информатика, кибернетика и программирование

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

Русский

2012-11-28

72.5 KB

19 чел.

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

Быстрая сортировка (quick sort) является одним из наиболее эффективных алгоритмов сортировки. В основе его лежит идея декомпозиции, т.е. поэтапного сведения исходной задачи к набору аналогичных, но более простых, вплоть до тривиальных, а затем объединения результатов. Подход можно описать в виде трех этапов:

 Разделение. Массив A[p,r] разбивается на два подмассива A[p,q] и A[q+1,r] (возможно, пустые) так, чтобы все элементы первого были меньше элементов второго. С этой целью в исходном массиве выбирается «опорный» элемент M, определяющий границу разбиения: все элементы со значениями меньшими M, перемещаются в первый подмассив, а элементы со значениями большими либо равными M, размещаются во втором.

 Решение подзадач. К каждому из двух полученных массивов рекурсивно применяется та же самая процедура. Поскольку все значения элементов первого массива меньше значений во втором массиве, исходный массив будет отсортирован правильно. В процессе последовательного разделения задача постепенно сведется к сортировке подмассивов, содержащих не более двух элементов, которая решается тривиально.

 Объединение результатов. В данном алгоритме подзадачи (т.е сортировка подмассивов) решаются «на месте», поэтому никаких специальных действий для объединения результатов не потребуется.

Существенным вопросом в этом алгоритме является выбор опорного элемента M. Нетрудно видеть, что наиболее эффективной стратегией был бы выбор медианного элемента массива, что обеспечивало бы разделение массива на две примерно равные части. Однако, определение медианного элемента повлекло бы дополнительные вычислительные затраты, поэтому чаще всего в качестве опорного выбирают элемент, расположенный посередине массива.

Рис. 1. Процедура разделения.

void quickSort( double * A, int first, int last )

{

   int i = first, j = last;

 // Выбираем "опорный" элемент

 double med = A[ (first + last) / 2 ];

 

 // Разбиваем массив на 2 части относительно

 // "опорного" элемента

do 

{

       while ( A[i] < med )

  i++;

       while ( A[j] > med )

  j--;

 

       if ( i <= j )

  {

           double tmp = A[i];

    A[i] = A[j];

  A[j] = tmp;

   

  i++;

           j--;

       }

   }

   while ( i <= j );

 

 // Рекурсивно применяем ту жу процедуру к

 // обеим частям массива

   if ( i < last )

       quickSort( A, i, last );

   if ( first < j )

       quickSort( A, first, j );

}

Несмотря на все положительные качества быстрой сортировки, базовый вариант алгоритма обладает недостатком: сортировка становится крайне неэффективной на некоторых часто встречающихся на практике типах входных данных. Например, если она применяется для сортировки уже отсортированной последовательности из N элементов, то все операции разделения вырождаются, и алгоритм рекурсивно вызовет сам себя N раз, перемещая за каждый вызов всего лишь один элемент. В этом, худшем, случае нетрудно оценить требуемое количество операций сравнения: N + (N-1) + …+ 2 + 1 = (N+1)N/2, что приводит к асимптотической оценке количества сравнений в худшем случае в O(N2).

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

CN = 2CN/2 + N.

Можно доказать, что решением этого соотношения будет CNN logN. Асимптотическая оценка среднего случая приводит к аналогичной величине.

Большая глубина рекурсивных вызовов может быть серьезной проблемой при использовании быстрой сортировки для очень длинных последовательностей. При использовании базового варианта алгоритма, даже короткие участки последовательности будут сортироваться по тому же принципу, при этом, количество вызовов алгоритма для коротких блоков на самых «глубоких» уровнях рекурсии будет очень велико. Сократить расходы на рекурсивный вызов алгоритма для коротких блоков можно простым способом – ввести ограничение на минимальный размер блока, для которого вместо алгоритма быстрой сортировки будет вызван другой, нерекурсивный, метод сортировки, например, сортировка вставками. Определение фактического значения этого порогового значения можно путем анализа скорости работы алгоритма на ожидаемых на практике последовательностях.

Ещё одно из возможных усовершенствований алгоритма быстрой сортировки заключается в использовании такого опорного элемента, который с большой вероятностью приводил к разделению последовательности на примерно равные части. Наиболее безопасный выбор, минимизирующий вероятность возникновения наихудшего случая, обеспечивается использованием в качестве разделяющего случайного элемента массива. Такой метод представляет собой пример вероятностного алгоритма, когда используется случайный характер величин для достижения высокой эффективности с большой вероятностью, независимо от степени упорядоченности входных данных.

Другой часто используемый способ нахождения подходящего разделяющего элемента заключается в том, что производится выборка трёх элементов из последовательности, а затем в качестве разделяющего используется медиана из этих трех элементов. Такой выбор основывается на том, что в среднем, медиана из трех элементов даст грубую оценку медианы всей последовательности.

Ещё один особый случай, в котором быстрая сортировка неэффективна – последовательность, содержащая большое количество (в предельном случае – все) дублирующихся элементов. В таком случае в качестве усовершенствования можно предложить разбивать последовательность не на две, а на три части: первая – для элементов меньших опорного, вторая – для элементов, равных ему, третья – для элементов, больших опорного. Однако, выполнение такого разделения реализуется гораздо сложнее.

Быстрая сортировка нашла широкое применение в связи с тем, что она эффективно работает в большинстве случаев. Другие методы работают лучше только в некоторых особых ситуациях, время от времени встречающихся на практике.


2

0

1

5

9

8

6

12

2

7

3

4

2

4

1

5

9

8

6

12

2

7

3

10

2

4

1

5

3

8

6

12

2

7

9

10

2

4

1

5

3

7

6

12

2

8

9

10

2

4

1

5

3

7

6

2

12

8

9

10


 

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

31886. Кассир. Должностные обязанности 23 KB
  Должен знать: постановления распоряжения приказы другие руководящие и нормативные документы вышестоящих и других органов касающиеся ведения кассовых операций; формы кассовых и банковских документов; правила приема выдачи учета и хранения денежных средств и ценных бумаг; порядок оформления приходных и расходных документов; лимиты остатков кассовой наличности установленной для организации; правила обеспечения их сохранности; порядок ведения кассовой книги составления кассовой отчетности; правила эксплуатации электронно вычислительной...
31887. Работа с формулами. Абсолютная и относительная адресация при работе с формулами 44.5 KB
  Вам необходимо определить стоимость каждой квартиры таким образом чтобы общая сумма полученных денег равнялась 7 млн. Известно что: дом 6ти этажный кирпичный; на каждом этаже по 4 квартиры 1но 2х 3х и 4х комнатные общей площадью 63; 90; 118; 146 соответственно; стоимость квартир зависит от этажа на первом и последнем дешевле; стоимость 1 м2 в центре Екатеринбурга 60. В ячейку G2 введите стоимость одного квадратного метра – 60. Выделите все ячейки связанные с суммами стоимость квартир и задайте Финансовый формат с двумя...
31888. Сердечно-легочная и церебральная реанимация 103 KB
  Проверить реакцию пострадавшего: аккуратно встряхнуть его за плечи и громко спросить Что с Вами€. Принять решение: если пострадавший реагирует – оставить его в том же положении попытаться выяснить причины происходящего и позвать на помощь регулярно оценивать состояние пострадавшего; если пострадавший не реагирует – громко позвать на помощь повернуть на спину и открыть дыхательные пути путем запрокидывания головы и подтягивания подбородка – рукой нужно надавить на лоб а другой рукой подтянуть подбородок. Альтернативный способ –...
31889. Русский язык и культура речи 247 KB
  ФОНЕТИЧЕСКИЙ УРОВЕНЬ Содержит задания отражающие проблемы связанные с нормами постановки ударения акцентологические нормы. СЛОВООБРАЗОВАТЕЛЬНЫЙ УРОВЕНЬ В заданиях необходимо найти ошибки допущенные при образовании слов и исправить их. ГРАММАТИЧЕСКИЙ УРОВЕНЬ В данном блоке представлен комплекс заданий на проверку знания морфологических норм нормы образования форм слов различных частей речи и синтаксических норм нормы употребления форм слов в словосочетании и предложении нормы построения предложений. ЛЕКСИЧЕСКИЙ УРОВЕНЬ Данный блок...
31890. ПЛАНЫ СЕМИНАРСКИХ ЗАНЯТИЙ И ТЕМЫ РЕФЕРАТОВ ПО ФИЛОСОФИИ 377.5 KB
  Горького Рассмотрены на заседании кафедры философии Протокол № 7 от 4 апреля 2005 г. Творческое усвоение студентами философии т. При творческом усвоении философии у студентов формируются следующие умения по различным блокам философского знания: историкофилософский блок: вычленять смысл философской системы: как в ней решаются вопросы метафизики антропологии гносеологии аксиологии культурологии социологии политологии праксиологии; определять педагогическую значимость той или иной философской системы и аргументировать ответ;...
31891. Методические рекомендации, планы семинарских занятий и темы контрольных работ по философии 198.5 KB
  Андреев Одобрены на заседании кафедры философии. кафедрой философии С. 2005 Введение При усвоении дисциплины студент должен иметь программу по философии в которой отражены цели задачи требования к уровню усвоения содержания дисциплины приведена основная и дополнительная литература по всем темам курса контрольные вопросы для подготовки к экзамену.
31892. Задания и методические указания для выполнения курсовых работ по дисциплине «Основы маркетинга» 77.5 KB
  Шапошников Одобрена на заседании кафедры менеджмента и маркетинга. Методические указания к написанию курсовой работы Главное условие успешного овладения студентами знаниями в области дисциплины Основы маркетинга заключается в самостоятельной систематической работе. При высоком уровне знаний проявленных при защите курсовой работы и другим контрольным мероприятиям а также на практических занятиях по дисциплине Основы маркетинга студент может быть освобожден от экзамена.
31893. Статистика. Задания к контрольным работам по дисциплине «Статистика» и методические указания для их выполнения 510 KB
  Группировкой называется расчленение множества единиц изучаемой совокупности на группы по определенным существенным для них признакам. Группировка выявляющая взаимосвязи между изучаемыми явлениями и их признаками называется аналитической группировкой. После определения признака положенного в основание группировки определяют количество групп на которые разбивают исследуемую совокупность. Число групп зависит от задач исследования типа группировки вида признака положенного в основание группировки численности совокупности степени вариации...
31894. ЭКОНОМИЧЕСКИЙ АНАЛИЗ 366.5 KB
  При изучении данной дисциплины и выполнении курсовой работы студенты должны быть знакомы с вопросами экономической статистики экономики предприятия бухгалтерского учета финансов предприятия изучаемыми на предыдущих курсах. Объектом изучения дисциплины выступает финансовохозяйственная деятельность предприятия соответственно курсовая работа направлена на выявление проблем в финансовохозяйственной деятельности определение резервов использования ресурсов и формулирование мероприятий по их реализации. Цель курсовой работы по дисциплине...