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


 

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

33637. Актуальность проблемы обеспечения безопасности сетевых информационных технологий 13.99 KB
  Отставание в области создания непротиворечивой системы законодательноправового регулирования отношений в сфере накопления использования и защиты информации создает условия для возникновения и широкого распространения компьютерного хулиганства и компьютерной преступности. Особую опасность представляют злоумышленники специалисты профессионалы в области вычислительной техники и программирования досконально знающие все достоинства и слабые места вычислительных систем и располагающие подробнейшей документацией и самыми совершенными...
33638. Основные понятия информационной безопасности 31 KB
  В связи с бурным процессом информатизации общества все большие объемы информации накапливаются хранятся и обрабатываются в автоматизированных системах построенных на основе современных средств вычислительной техники и связи. Автоматизированная система АС обработки информации организационнотехническая система представляющая собой совокупность взаимосвязанных компонентов: технических средств обработки и передачи данных методов и алгоритмов обработки в виде соответствующего программного обеспечения информация массивов наборов баз...
33639. Классификация уязвимостей 37.5 KB
  Некоторые уязвимости подобного рода трудно назвать недостатками скорее это особенности проектирования. В Уязвимости могут быть следствием ошибок допущенных в процессе эксплуатации информационной системы: неверное конфигурирование операционных систем протоколов и служб использование нестойких паролей пользователей паролей учетных записей по умолчанию и др. по уровню в инфраструктуре АС К уровню сети относятся уязвимости сетевых протоколов стека TCP IP протоколов NetBEUI IPX SPX. Уровень операционной системы охватывает уязвимости...
33640. Основные механизмы защиты компьютерных систем 39 KB
  Основные механизмы защиты компьютерных систем Для защиты компьютерных систем от неправомерного вмешательства в процессы их функционирования и несанкционированного доступа НСД к информации используются следующие основные методы защиты защитные механизмы: идентификация именование и опознавание аутентификация подтверждение подлинности субъектов пользователей и объектов ресурсов компонентов служб системы; разграничение доступа пользователей к ресурсам системы и авторизация присвоение полномочий пользователям; регистрация и...
33641. Криптографические методы защиты информации, Контроль целостности программных и информационных ресурсов 37 KB
  Криптографические методы защиты информации Криптографические методы защиты основаны на возможности осуществления специальной операции преобразования информации которая может выполняться одним или несколькими пользователями АС обладающими некоторым секретом без знания которого с вероятностью близкой к единице за разумное время невозможно осуществить эту операцию. В классической криптографии используется только одна единица секретной информации ключ знание которого позволяет отправителю зашифровать информацию а получателю расшифровать...
33642. Защита периметра компьютерных сетей 48 KB
  В межсетевых экранах применяются специальные характерные только для данного вида средств методы защиты. Основные из них: трансляция адресов для сокрытия структуры и адресации внутренней сети; фильтрация проходящего трафика; управление списками доступа на маршрутизаторах; дополнительная идентификация и аутентификация пользователей стандартных служб на проходе; ревизия содержимого вложений информационных пакетов выявление и нейтрализация компьютерных вирусов; виртуальные частные сети для защиты потоков данных передаваемых по...
33643. Сетевые анализаторы и снифферы 63 KB
  Главный недостаток технологии Ethernet незащищенность передаваемой информации Метод доступа положенный в основу этой технологии требует от узлов подключенных к сети непрерывного прослушивания всего трафика. Узлы такой сети могут перехватывать информацию адресованную своим соседям. В общем смысле слово сниффер обозначает устройство подключенное к компьютерной сети и записывающее весь ее трафик подобно телефонным жучкам записывающим телефонные разговоры. В то же время сниффером программа запущенная на подключенном к сети узле и...
33644. Защита на канальном уровне 549.5 KB
  Технология создания защищенного виртуального канала по протоколу PPTP предусматривает как аутентификацию удаленного пользователя так и зашифрованную передачу данных. Программное обеспечение удаленного доступа реализующее PPTP может использовать любой стандарт криптографического закрытия передаваемых данных. Например сервер удаленного доступа Windows использует стандарт RC4 и в зависимости от версии 40 или 128разрядные сеансовые ключи которые генерируются на основе пароля пользователя. В протоколе PPTP определено три схемы его...
33645. ПРОТОКОЛЫ РАЗРЕШЕНИЯ АДРЕСОВ ARP 35.5 KB
  ПРОТОКОЛЫ РАЗРЕШЕНИЯ АДРЕСОВ RP. Для доставки дейтаграммы в локальной сети нужно определить физический адрес узла назначения. Именно для этого существует процедура автоматического определения физических адресов. Протокол разрешения адресов ddress Resolution Protocol RP обеспечивает метод динамической трансляции между IPадресом и соответствующим физическим адресом на основе широковещательных рассылок.