4876

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

Лекция

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

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

Русский

2012-11-28

72.5 KB

20 чел.

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

Быстрая сортировка (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


 

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

77509. Землетрясения и сейсмическая опасность 31.5 KB
  При недостаточной прочности сейсмостойкости конструкций происходят их повреждения различной степени или разрушения. Анализ последствий землетрясений показывает что здания различной конструкции получают следующие повреждения если сейсмические воздействия превышают расчетные для зданий запроектированных с учетом требований...
77510. ПОЖАРЫ И ВЗРЫВЫ 29.08 KB
  Результат распределения энергии по видам характеризует степень опасности для человека и окружающей территории далее объекта безопасности которая обусловлена негативным воздействием на объект безопасности и заключается в формировании опасных факторов часть из которых может быть поражающими Объекты на которых могут возникать опасные явления со взрывами и пожарами относят к классу взрывопожароопасных. В физикохимической основе пожара лежит процесс горения. Продвижение людей и техники по застроенной территории между отдельными пожарами...
77511. Повышение устойчивости объектов экономики 25.02 KB
  Принципы разработки и реализации мероприятий по повышению устойчивости объекта экономики. Поскольку на промышленном объекте с течением времени условия обстановка характеристики отдельных элементов оборудование технологический процесс могут меняться то необходимо периодически по планам министерств и ведомств в установленные сроки проводить исследования и оценку устойчивости функционирования объекта в ЧС в том числе в военное время. Цель исследования состоит в том чтобы выявить уязвимые места в функционировании объекта в ЧС особенно в...
77512. Природные факторы опасности 27.27 KB
  Классификация природных факторов опасности. Стихийные бедствия и явления. Геологические ЧС. Метеорологические опасности. Гидрологические опасности. Природные пожары. Лесные пожары. Торфяные пожары. Степные пожары.
77513. Оценка обстановки при природных ЧС 23.4 KB
  Планирование и заблаговременное проведение предупредительных мероприятий по борьбе с заторами льда необходимо осуществлять на основе прогнозирования максимальных уровней воды при ледоходе. В основном мероприятия связаны со способами влияния на толщину льда перед вскрытием. Подобное воздействие на процесс образования зажоров позволит снизить уровни воды периода ледостава а также снизить толщину льда в местах где традиционно образуются зажоры а затем заторы. В случае установления ледостава с высоким уровнем воды зажорно заторного характера...
77514. Техногенные ЧС. Классификация АХОВ 30.9 KB
  Классификация АХОВ. Классификация АХОВ. Выбросы аварийных химически опасных веществ АХОВ могут произойти при повреждениях и разрушениях емкостей при хранении транспортировке или переработке. Кроме того некоторые нетоксичные вещества в определенных условиях взрыв пожар в результате химической реакции могут образовать АХОВ Химически опасный объект ХОО предприятие народного хозяйства при аварии или разрушении которого могут произойти массовые поражения людей животных и растений АХОВ.
77515. Внутривидовые взаимоотношения, опосредованные сигнальными веществами 380.5 KB
  Первая группа вещества участвующие во внутривидовых взаимодействиях: аутотоксины отбросы токсичные для организмапродуцента и не приносящие пользы другим видам; аутоингибиторы адаптации сдерживают численность популяции в таких пределах чтобы она находилась в равновесии с окружающей средой; феромоны выполняют различные функции например половые феромоны общественные феромоны феромоны тревоги и обороны феромоныметчики. К ним можно отнести экохемомедиаторы различного типа: половые феромоны и аттрактанты обнаруженные у грибов...
77516. Межвидовые взаимоотношения, опосредованные сигнальными веществами. Алломоны и кайромоны 547 KB
  Межвидовые взаимоотношения опосредованные сигнальными веществами. К первой группе относятся: метаболиты выделяемые потенциальным грибомхозяином индуцирующие и направляющие рост гиф паразита; вещества выделяемые паразитическим грибом и вызывающие рост гиф хозяина по направлению к колонии микопаразита. Ко второй группе относятся вещества с помощью которых оказывается противодействие паразитам: антифунгальные вещества и антибиотики обладающие антифунгальным действием синтезируются как грибами которые являются непосредственными...
77517. Химические основы коммуникации у человека 461 KB
  Химические основы коммуникации у человека. Вомероназальный орган его происхождение и функции у позвоночных и человека. Феромонная коммуникация у человека. У млекопитающих животных и человека вкусовые органы помещаются главным образом на сосочках языка и отчасти на мягком нёбе и задней стенке глотки.