Действие III, явление VI

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

Метод Шелла

Методы сортировки

Быстрые (улучшенные)

Шейкерная сортировка

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

Шейкерная сортировка хороша тогда, когда элементы последовательности почти упорядочены.

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

Метод Шелла является улучшением метода сортировки с помощью прямого включения и основан на сортировке посредством включений с уменьшающимися расстояниями. Сначала отдельно группируются и сортируются методом прямых включений элементы, отстоящие друг от друга на некотором расстоянии h₁, затем на расстоянии h_2< h₁ и т.д., последнее расстояние должно быть равно 1. Таким образом, если для сортировки будет использовано t расстояний, то h_t =1, h_i+1<h_i. Желательно, чтобы расстояния обеспечивали бы взаимодействие различных цепочек как

можно чаще.

Имеет смысл использовать такие последовательности (записаны в обратном порядке):

1) 1, 4, 13, 40, 121,...,т.e h_k-1 = 3 h_k +1, h_t= 1, t = [log₃n]- 1

2) 1,3,7, 15,31,..., т.е. h_k-1 =2 h_k + 1, h_t = 1, t= [log₂ n ] - 1. В последнем случае для сортировки п элементов методом Шелла затраты пропорциональны n ^1,2, что значительно лучше n ², но хуже n *log₂ n.

3) часто используют h₁= п/2, h₂ = n /4,..., и т.д.

На каждом шаге методом включения сортируются группы a₁ ,a_1+h, a_1+2h,…., a_1+kh,1+kh< = n; a₂,a_2+h ….Так как начальный шаг является наибольшим, то число элементов массива в начальной группе является наименьшим, например, если h = n/2, то группируются только два элемента, При втором проходе шаг уменьшается, а число элементов в группе увеличивается, и при h = 1 группа включает всю последовательность целиком.

Рассмотрим процесс сортировки последовательности из n=8 целых чисел:

5, 6, 2, 4, 8, 3, 1, 7.

При h ₁=n/2=4 получим четыре группы по два элемента в каждой: 5, 8; 6, 3; 2, 1; 4, 7.

Сортируем каждую последовательность, в результате получим: 5, 8; 3, 6; 1, 2; 4, 7.

Затем группируем первые элементы с первыми, вторые – со вторыми, получаем последовательность 5, 3, 1, 4, 8, 6, 2, 7.

Принимаем h₂ = h ₁/2=2. Получим две последовательности по 4 элемента в каждой, объединяя первый, третий, пятый и седьмой элементы, и второй, четвертый, шестой и восьмой:

5, 1, 8, 2; 3, 4, 6, 7. Сортируем каждую последовательность, в результате получим:

1, 2, 5, 8; 3, 4, 6, 7. Группируем первые элементы с первыми, вторые – со вторыми, третьи – с третьими, четвертые – с четвертыми: 1, 3, 2, 4, 5, 6, 8, 7. Данная последовательность уже частично отсортирована.

И, наконец, h₃ = h₂ /2=1. Сортируем данную последовательность и получаем:

1, 2, 3, 4, 5, 6, 7, 8.

Методика «быстрой сортировки» взята из повседневного опыта. Чтобы отсортировать большую стопку алфавитных карточек по именам, можно разбить ее на две меньшие стопки относительно какой-нибудь буквы, например К. Все имена, меньшие или равные К идут в одну стопку, а остальные – в другую. Затем каждая стопка снова делится на две и т.д.

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

Принцип сортировки:

1. Выбирается центральный элемент массива. Все элементы массива просматриваются поочередно слева направо и справа налево. При движении слева направо ищем элемент A[scanUp], который будет больше или равен центральному и запоминаем его позицию. При движении справа налево ищем элемент A[scanDown], который будет меньше или равен центральному, и также запоминаем его позицию. Найденные элементы меняем местами и продолжаем поиск пока встречные индексы scanUp и scanDown не пересекутся. После выполнения первого этапа элементы исходного массива окажутся разделенными на две части относительно центрального значения.

2. На втором этапе повторяются действия первого этапа для правой и левой частей массива в отдельности.

3. На третьем этапе все повторяется для четырех частей массива. И т.д.

Для обработки подсписков используется рекурсия.

Пример:

Пусть дан массив, состоящий из 10 целых чисел:800, 150, 300, 600, 550, 650, 400, 350, 450, 700

Массив простирается от индекса low=0 до индекса high=9. Его середина приходится на индекс mid=4. Первым центральным элементом является A[mid]=550.

Все элементы массива А разбиваются на два подсписка: S1 и S2. S1 – будет содержать элементы, меньшие или равные центральному, S2 – будет содержать элементы большие, чем центральный. Сканируем подсписок A[0] – A[9] при помощи двух индексов: scanUp и scanDown. Начальное значение scanUp=0 (low), переменная scanDown имеет начальное значение 9 (high).

Индекс scanUp перемещается вверх по списку и ищет элемент, б о льший, чем центральный (т.е. 550), а индекс scanDown перемещается вниз по списку и ищет элемент, меньший, чем центральный, или равный ему. Таким образом, находятся элементы, расположенные не в своих подсписках, и их можно поменять местами. Этот процесс продолжается до тех пор, пока scanUp и scanDown не зайдут друг за друга (scanUp=6, scanDown=5).

В результате получился подсписок A[0] – A[5], элементы которого меньше элементов подсписка A[6] – A[9].

Затем оба подсписка обрабатываются по одному и тому же алгоритму – рекурсивная фаза.

Одним и тем же методом обрабатываются два подсписка: S1 (A[0] – A[5]) и S2 (A[6] – A[9]).

Подсписок S1:

Определяется диапазоном от индекса low=0 до индекса high=5.

Середина приходится на индекс mid=2.

Центральным элементом является A[mid]=300.

Сканирование вверх останавливается на индексе 0 (A[0] > A[mid])

Сканирование вниз останавливается на индексе 2 (A[2] <= A[mid])

Затем они меняются местами и процесс сканирования останавливается.

При этом scanDown является точкой разделения двух еще меньших подсписков: A[0] – A[1] и A[2] – A[6].

Подсписок S2:

Определяется диапазоном от индекса low=6 до индекса high=9.

Середина приходится на индекс mid=7.

Центральным элементом является A[mid]=600.

Сканирование вверх останавливается на индексе 6 (A[6] > A[mid]=600)

Сканирование вниз останавливается на индексе 7 (A[7] <= A[mid])

Затем они меняются местами и процесс сканирования останавливается.

При этом scanDown является точкой разделения двух еще меньших подсписков: A[6] и A[7] – A[9].

Обработать подсписок A[0] – A[1] (300, 150). Центральный элемент A[0]=300. После обработки числа выстраиваются в порядке 150, 300.

Обработать подсписок A[2] – A[5] (450, 350, 550, 400). Центральный элемент 350. После сканирования элементы выстраиваются в порядке 350, 450, 550, 400 и образуют два подсписка: 350 и 450, 550, 400.

Для обработки подсписка 450, 550, 400 требуется еще два рекурсивных вызова: первый из них даст последовательность элементов 450, 400, 550. Следующий вызов даст последовательность 400, 450, 550.

Рекурсивный процесс прекращается на пустом или одноэлементном подсписке.

«Быстрая сортировка» завершена. Результатом является следующий отсортированный список:

А = 150, 300, 350, 400, 450, 550, 600, 650, 700, 800.

Те же, Анна Андреевна и Марья Антоновна.

Анна Андреевна.... Я думаю, после столицы вояжировка вам показалась очень неприятною.

Хлестаков. Чрезвычайно неприятна. Привыкши жить, comprenez vous, в свете, и вдруг очутиться в дороге: грязные трактиры, мрак невежества... Если б, признаюсь, не такой случай, который меня... (посматривает на Анну Андреевну и рисуется перед ней) так вознаградил за все...

Анна Андреевна. В самом деле, как вам должно быть неприятно.

Хлестаков. Впрочем, сударыня, в эту минуту мне очень приятно.

Анна Андреевна. Как можно-с! Вы делаете много чести. Я этого не заслуживаю.

Хлестаков. Отчего же не заслуживаете?

Анна Андреевна. Я живу в деревне...

Хлестаков. Да деревня, впрочем, тоже имеет свои пригорки, ручейки... Ну, конечно, кто же сравнит с Петербургом! Эх, Петербург! что за жизнь, право! Вы, может быть, думаете, что я только переписываю; нет, начальник отделения со мной на дружеской ноге. Этак ударит по плечу: "Приходи, братец, обедать!" Я только на две минуты захожу в департамент, с тем только, чтобы сказать: "Это вот так, это вот так!" А там уж чиновник для письма, этакая крыса, пером только - тр, тр... пошел писать. Хотели было даже меня коллежским асессором сделать, да, думаю, зачем. И сторож летит еще на лестнице за мною со щеткою: "Позвольте, Иван Александрович, я вам, говорит, сапоги почищу". (Городничему.) Что вы, господа, стоите? Пожалуйста, садитесь!

Вместе.{ Городничий. Чин такой, что еще можно постоять.

Артемий Филиппович. Мы постоим.

Лука Лукич. Не извольте беспокоиться.

Хлестаков. Без чинов, прошу садиться.

Городничий и все садятся.

Хлестаков. Я не люблю церемонии. Напротив, я даже всегда стараюсь проскользнуть незаметно. Но никак нельзя скрыться, никак нельзя! Только выйду куда-нибудь, уж и говорят: "Вон, говорят, Иван Александрович идет!" А один раз меня даже приняли за главнокомандующего: солдаты выскочили из гауптвахты и сделали ружьем. После уже офицер, который мне очень знаком, говорит мне: "Ну, братец, мы тебя совершенно приняли за главнокомандующего".

Анна Андреевна. Скажите как!

Хлестаков. С хорошенькими актрисами знаком. Я ведь тоже разные водевильчики... Литераторов часто вижу. С Пушкиным на дружеской ноге. Бывало, часто говорю ему: "Ну что, брат Пушкин?" - "Да так, брат, - отвечает, бывало, - так как-то все..." Большой оригинал.

Анна Андреевна. Так вы и пишете? Как это должно быть приятно сочинителю! Вы, верно, и в журналы помещаете?

Хлестаков. Да, и в журналы помещаю. Моих, впрочем, много есть сочинений: "Женитьба Фигаро", "Роберт-Дьявол", "Норма". Уж и названий даже не помню. И все случаем: я не хотел писать, но театральная дирекция говорит: "Пожалуйста, братец, напиши что-нибудь". Думаю себе: "Пожалуй, изволь братец!" И тут же в один вечер, кажется, все написал, всех изумил. У меня легкость необыкновенная в мыслях. Все это, что было под именем барона Брамбеуса, "Фрегат Надежды" и "Московский телеграф"... все это я написал.

_____

Хлестаков. Я, признаюсь, литературой существую. У меня дом первый в Петербурге. Так уж и известен: дом Ивана Александровича. (Обращаясь ко всем.) Сделайте милость, господа, если будете в Петербурге, прошу, прошу ко мне. Я ведь тоже балы даю.

Анна Андреевна. Я думаю, с каким там вкусом и великолепием дают балы!

Хлестаков. Просто не говорите. На столе, например, арбуз - в семьсот рублей арбуз. Суп в кастрюльке прямо на пароходе приехал из Парижа; откроют крышку - пар, которому подобного нельзя отыскать в природе. Я всякий день на балах. Там у нас и вист свой составился: министр иностранных дел, французский посланник, английский, немецкий посланник и я. И уж так уморишься, играя, что просто ни на что не похоже. Как взбежишь по лестнице к себе на четвертый этаж - скажешь только кухарке: "На, Маврушка, шинель..." Что ж я вру - я и позабыл, что живу в бельэтаже. У меня одна лестница сто'ит... А любопытно взглянуть ко мне в переднюю, когда я еще не проснулся: графы и князья толкутся и жужжат там, как шмели, только и слышно: ж... ж... ж... Иной раз и министр...

Городничий и прочие с робостью встают со своих стульев.

Мне даже на пакетах пишут: "ваше превосходительство". Один раз я даже управлял департаментом. И странно: директор уехал, - куда уехал, неизвестно. Ну, натурально, пошли толки: как, что, кому занять место? Многие из генералов находились охотники и брались, но подойдут, бывало, - нет, мудрено. Кажется, и легко на вид, а рассмотришь - просто черт возьми! После видят, нечего делать, - ко мне. И в ту же минуту по улицам курьеры, курьеры, курьеры... можете представить себе, тридцать пять тысяч одних курьеров! Каково положение? - я спрашиваю. "Иван Александрович ступайте департаментом управлять!" Я, признаюсь, немного смутился, вышел в халате: хотел отказаться, но думаю: дойдет до государя, ну да и послужной список тоже... "Извольте, господа, я принимаю должность, я принимаю, говорю, так и быть, говорю, я принимаю, только уж у меня: ни, ни, ни!.. Уж у меня ухо востро! уж я..." И точно: бывало, как прохожу через департамент, - просто землетрясенье, все дрожит и трясется как лист.

Городничий и прочие трясутся от страха. Хлестаков горячится еще сильнее.

О! я шутить не люблю. Я им всем задал острастку. Меня сам государственный совет боится. Да что в самом деле? Я такой! я не посмотрю ни на кого... я говорю всем: "Я сам себя знаю, сам." Я везде, везде. Во дворец всякий день езжу. Меня завтра же произведут сейчас в фельдмарш... (Поскальзывается и чуть-чуть не шлепается на пол, но с почтением поддерживается чиновниками.)

Городничий (подходя и трясясь всем телом, силится выговорить). А ва-ва-ва... ва...

Хлестаков (быстрым, отрывистым голосом). Что такое?

Городничий. А ва-ва-ва... ва...

Хлестаков (таким же голосом). Не разберу ничего, все вздор.

Городничий. Ва-ва-ва... шество, превосходительство, не прикажете ли отдохнуть?.. вот и комната, и все что нужно.

Хлестаков. Вздор - отдохнуть. Извольте, я готов отдохнуть. Завтрак у вас, господа, хорош... Я доволен, я доволен. (С декламацией.) Лабардан! лабардан! (Входит в боковую комнату, за ним городничий.)

Для выполнения задания 1.1—1.2 запишите сначала номер задания, а затем на каждый вопрос дайте развернутый связный ответ (примерный объем 3—5 предложений), аргументируя свою точку зрения, опираясь на текст произведения.

1.1

Как Хлестаков выдаёт своё истинное положение в обществе? Почему этого не замечают чиновники?

1.2

Какова роль в данном фрагменте приёма сатирического преувеличения, основанного на сочетании реального и фантастического?

Для выполнения задания 1.3 запишите сначала номер задания, а затем дайте развернутый связный ответ (примерный объем — 5—8 предложений), аргументируя свою точку зрения, опираясь на художественный текст и обращаясь (по памяти) к другим произведениям.

1.3

Сравните фрагмент с фрагментом из комедии А.С. Грибоедова «Горе от ума». Чем похожи Хлестаков и Молчалин?

Дата добавления: 2017-01-14; Просмотров: 143; Нарушение авторских прав?; Мы поможем в написании вашей работы!