Внешняя сортировка


Внешняя сортировка

Проще всего отсортировать файл так: загрузить его, отсортировать его в памяти, затем записать результат. Если файл настолько велик, что загрузить его в оперативную память не удается, приходится применять разнообразные методы внешней сортировки. Мы рассмотрим здесь внешнюю сортировку, использующую выбор с замещением для получения начальных отрезков, за которым следует многофазное слияние для слияния отрезков в один отсортированный файл. Очень рекомендую книжку Кнута [1998] — неисчерпаемый источник дополнительной информации.

Теория

Для определенности я буду считать, что данные располагаются на одной или более бобин магнитной ленты. На рис. 4-1 иллюстрируется трехпутевое многофазное слияние. В начале, на фазе А, все денные находятся на лентах Т1 и Т2. Предполагается, что начало каждой ленты — внизу картинки. Имеется два упорядоченных отрезка на Т1: 4-8 и 6-7. На ленте Т2 — один отрезок 5-9. На фазе B мы сливаем первый отрезок с ленты Т1 (4-8) с первым отрезком Т2 (5-9) и получаем более длинный отрезок на ленте Т3 (4-5-8-9). На фазе С мы просто переименовываем ленты, так чтобы можно было повторить слияние. На фазе D мы повторяет слияние, получив результат на ленте Т3.

Фаза T1 T2 T3
A 7
6
8
4
9
5
B 7
6
9
8
5
4
C 9
8
5
4
7
6
D 9
8
7
6
5
4

Рис. 4-1: Сортировка слиянием

В приведенном тексте опущены некоторые интересные детали. Например, как были созданы начальные возрастающие отрезки? Кроме того, вы обратили внимание: они слиты так, что не потребовалось создавать дополнительные отрезки? Перед тем, как я объясню, каким образом были созданы начальные отрезки, позвольте мне слегка отвлечься.

В 1202 Леонардо Фибоначчи в книге Liber Abbaci (Книга об абаке) рассмотрел следующую задачу: Сколько пар кроликов можно получить за год, если в начале была лишь одна пара? Предположим, что каждая пара кроликов производит потомство каждый месяц, становится способной к воспроизводству также за один месяц, а также, что кролики не мрут. Спустя один месяц у нас будет 2 пары кроликов, спустя 2 месяца — 3 пары. Спустя еще месяц исходная пара и пара, рожденная в 1-й месяц, дадут каждая по паре, так что всего у нас будет 5 пар. Ряд, в котором каждый член является суммой двух предыдущих членов, называется последовательностью Фибоначчи:

Вспомним, что сначала у нас был один отрезок на ленте Т2 и два — на ленте Т1. Обратите внимание — числа <1,2>являются двумя последовательными членами ряда Фибоначчи. После первого слияния у нас появился один отрезок на Т1 и один на Т2. Заметим, что числа <1,1>— тоже два последовательных члена ряда Фибоначчи, только на шаг раньше. Мы, таким образом, готовы предсказать, что если бы у нас было 13 отрезков на Т2 и 21 на Т1 <13,21>, то после одного прохода у нас было бы 8 отрезков на Т1 и 13 на Т3 <8,13>. Последовательные проходы привели бы нас к отрезкам <5,8>, <3,5>, <2,3>, <1,1>и <0,1>, т.е. всего понадобилось бы 7 проходов. Этот порядок идеален, при нем требуется минимальное число проходов. Если данные действительно находятся на ленте, минимизация числа проходов очень важна, поскольку ленты может понадобиться снимать и устанавливать после каждого прохода. В случае, когда имеется более двух лент, применяются числа Фибоначчи высшего порядка.

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

  • Выбрать запись с наименьшим ключом, т.е. с ключом, значение которого >= значения ключа последней прочитанной записи.
  • Если все «старые» ключи меньше последнего ключа, то мы достигли конца отрезка. Выбираем запись с наименьшим ключом в качестве первого элемента следующего отрезка.
  • Записываем выбранную запись.
  • Заменяем выбранную и записанную запись на новую из входного файла.

На рис. 4-2 выбор с замещением иллюстрируются для совсем маленького файла. Начало файла — справа. Чтобы упростить пример, считается, что в буфер помещается всего лишь 2 записи. Конечно, в реальных задачах в буфер помещаются тысячи записей. Мы загружаем буфер на шаге В и записываем в выходной файл запись с наименьшим номером >= 6 на шаге D. Ею оказалась запись с ключом 7. Теперь мы заменяем ее на новую запись из входного файла — с ключом 4. Процесс продолжается до шага F, где мы оказывается, что последний записанный ключ равен 8 и все ключи меньше 8. В этот момент мы заканчиваем формирование текущего отрезка и начинаем формирование следующего.

Шаг Вход Буфер Выход
A 5-3-4-8-6-7
B 5-3-4-8 6-7
C 5-3-4 8-7 6
D 5-3 8-4 7-6
E 5 3-4 8-7-6
F 5-4 3 | 8-7-6
G 5 4-3 | 8-7-6
H 5-4-3 | 8-7-6

Рис. 4-2: Выбор с замещением

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

Прочитав из входного файла очередную запись, мы ищем наименьший ключ, который >= последнего считанного. При этом мы, конечно, можем просто сканировать записи в буфере. Однако, если таких записей тысячи, время поиска может оказаться недопустимо большим. Если на этом этапе использовать двоичные деревья, нам понадобится всего лишь lg n сравнений.

Реализация

В кодах внешней сортировки на ANSI-C функция makeRuns вызывает readRec для чтения очередной записи. В функции readRec используется выбор с замещением (с двоичными деревьями) для получения нужной записи, а makeRuns распределяет записи согласно ряду Фибоначчи. Если количество отрезков оказывается вне последовательности Фибоначчи, в начало каждого файла добавляются пустые отрезки. Затем вызывается функция mergeSort, которая производит многофазное слияние отрезков.

Внешняя сортировка с слиянием

Сначала считываются первые 4 числа, из них какое-то записывается в 5 файл, потом считываем следующее число из файла, в котором был минимальный, и вновь выбираем наименьшее из 4 чисел, где 3 числа останутся теми же, а 1 будет новое.

(2) Потом из 5 файла числа распределяются по 4 файлам, и сливаются заново. Каждый раз длина отрезка упорядоченных чисел увеличивается.
Проблемы:
— не происходит запись в 5 файл;
— не понял, как сделать (2)

24.04.2020, 16:58

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом?
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит сортировка и каким.

Сортировка Слиянием vs Быстрая Сортировка — что лучше
Народ, помогите разобраться какой из методов сортировки лучше «Сортировка Слиянием» или «Быстрая.

2 сортировки: пирамидальная сортировка и сортировка слиянием
Реализовать два улучшенных алгоритма сортировки. Для каждого алгоритма вычислить показатель.

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

Внешняя сортировка
Подскажите, как реализовать внещную сортировку массива?

Естественное слияние последовательностей. Внешняя сортировка

Естественное слияние последовательностей

Алгоритм слияния можно использовать и для сортировки массивов, если последовательно применить его несколько раз ко все более длинным упорядоченным последовательностям. Для этого:

  1. в исходном наборе выделяются две подряд идущие возрастающие подпоследовательности (серии)
  2. эти подпоследовательности (серии) сливаются в одну более длинную упорядоченную последовательность так, как описано выше
  3. шаги 1 и 2 повторяются до тех пор, пока не будет достигнут конец входного набора
  4. шаги 1 –3 применяются к новому полученному набору, т.е. выделяются пары серий, которые сливаются в еще более длинные наборы, и.т.д. до тех пор, пока не будет получена единая упорядоченная последовательность.

Пример. Пусть имеется входной неупорядоченный набор чисел:
24, 08, 13, 17, 06, 19, 20, 11, 07, 55, 33, 22, 18, 02, 40
Этап 1. Выделяем в нем серии (показаны скобками) и попарно сливаем их:
(24), (08, 13, 17), (06, 19, 20), (11), (07, 55), (33), (22), (18), (02, 40)
(24) + (08, 13, 17) = (08, 13, 17, 24)
(06, 19, 20) + (11) = (06, 11, 19, 20)
(07, 55) + (33) = (07, 33, 55)
(22) + (18) = (18, 22)
Новый набор чисел:
08, 13, 17, 24, 06, 11, 19, 20, 07, 33, 55, 18, 22, 02, 40
Этап 2. Выделяем в новом наборе серии и попарно сливаем их (число серий уменьшилось):
(08, 13, 17, 24), (06, 11, 19, 20), (07, 33, 55), (18, 22), (02, 40)
(08, 13, 17, 24) + (06, 11, 19, 20) = (06, 08, 11, 13, 17, 19, 20, 24)
(07, 33, 55) + (18, 22) = (07, 18, 22, 33, 55)
Новый набор:
06, 08, 11, 13, 17, 19, 20, 24, 07, 18, 22, 33, 55, 02, 40
Этап 3. Выделяем в новом наборе серии (всего три) и сливаем их:
(06, 08, 11, 13, 17, 19, 20, 24), (07, 18, 22, 33, 55), (02, 40)
(06, 08, 11, 13, 17, 19, 20, 24) + (07, 18, 22, 33, 55) = (06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 55)
Новый набор и его две серии:
(06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 55), (02, 40)
Этап 4. После слияния этих двух серий получим полностью упорядоченный набор:
02, 06, 07, 08, 11, 13, 17, 18, 19, 20, 22, 24, 33, 40, 55
Данный метод сортировки называется естественным слиянием. Его особенностью является то, что для его реализации на каждом шаге достаточно сравнивать только два элемента. Именно это позволяет хранить все основные элементы в дисковых файлах, загружая в ОП только небольшое число элементов из каждой серии.
Алгоритм слияния эффективно работает на длинных сериях и неэффективно на коротких. Поэтому его нецелесообразно применять с самого начала сортировки, поскольку для случайного входного набора на первых шагах будут получаться очень короткие серии, что приведет к неоправданно большому числу обращений к дисковой памяти.

Внешняя сортировка

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

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

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

Внешняя сортировка

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

Илон Маск рекомендует:  AssignPrn - Процедура Delphi


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

Например, пусть имеются две упорядоченные числовые последовательности: (5, 11, 17) и (8, 9, 19, 25).

Их слияние выполняется следующим образом:

  • · сравниваются первые числа 5 и 8, наименьшее (5) помещается в выходной набор: (5)
  • · сравниваются 11 и 8, наименьшее (8) — в выходной набор: (5, 8)
  • · сравниваются 11 и 9, наименьшее (9) — в выходной набор: (5, 8, 9)
  • · сравниваются 11 и 19, наименьшее (11) — в выходной набор: (5, 8, 9, 11)
  • · сравниваются 17 и 19, наименьшее (17) — в вых. набор: (5, 8, 9, 11, 17)
  • · остаток второй последовательности (19, 25) просто копируется в выходной набор с получением окончательного результата: (5, 8, 9, 11, 17, 19, 25)

В общем виде алгоритм слияния можно представить следующим образом. Пусть А=i> и B=j> — две исходные упорядоченные последовательности, R — результирующая последовательность.

Внешняя сортировка Внешние сортировки Внешние сортировки

Внешние сортировки • Внешние сортировки применяются к данным, которые хранятся во внешней памяти (данные, расположены на внешних устройствах последовательного доступа). • Внешние сортировки применяются, если объем сортируемых данных превосходит допустимое место в ОЗУ. • Для файлов, расположенных на таких устройствах в каждый момент времени доступен только один компонент последовательности данных, что является существенным ограничением по сравнению с сортировкой массивов, где всегда доступен каждый элемент.

Наиболее известные алгоритмы внешней сортировки: • 1. Сортировка слиянием. 2. Многопутевое слияние и выбор с замещением. 3. Многофазное слияние. 4. Каскадное слияние. 5. Осциллирующая сортировка. 6. Внешняя поразрядная сортировка (или распределяющая сортировка).

Определения • Серия (упорядоченный отрезок) – это последовательность элементов, которая упорядочена по ключу. – Количество элементов в серии называется длиной серии. – Серия, состоящая из одного элемента, упорядочена всегда. – Последняя серия может иметь длину меньшую, чем остальные серии файлов. – Максимальное количество серий в файле N (все элементы не упорядочены). – Минимальное количество серий одна (все элементы упорядочены).

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

• Фаза – это действия по однократной обработке всей последовательности элементов. • Двухфазная сортировка – это сортировка, в которой отдельно реализуется две фазы: распределение и слияние. • Однофазная сортировка – это сортировка, в которой объединены фазы распределения и слияния в одну.

• Двухпутевым слиянием называется сортировка, в которой данные распределяются на два вспомогательных файла. Многопутевым слиянием называется сортировка, в которой данные распределяются на N (N > 2) вспомогательных файлов.

Общий алгоритм сортировки слиянием • Сначала серии распределяются на два или более вспомогательных файлов. • Данное распределение идет поочередно: первая серия записывается в первый вспомогательный файл, вторая – во второй и так далее до последнего вспомогательного файла. Затем опять запись серии начинается в первый вспомогательный файл.

• После распределения всех серий, они объединяются в более длинные упорядоченные отрезки, то есть из каждого вспомогательного файла берется по одной серии, которые сливаются. • Если в каком-то файле серия заканчивается, то переход к следующей серии не осуществляется.

• В зависимости от вида сортировки сформированная более длинная упорядоченная серия записывается либо в исходный файл, либо в один из вспомогательных файлов. • После того как все серии из всех вспомогательных файлов объединены в новые серии, потом опять начинается их распределение. И так до тех пор, пока все данные не будут отсортированы.

Основные характеристики сортировки слиянием • количество фаз в реализации сортировки; • количество вспомогательных файлов, на которые распределяются серии.

Сортировка простым слиянием • В данном алгоритме длина серий фиксируется на каждом шаге. • В исходном файле все серии имеют длину 1, • после первого шага она равна 2, • после второго – 4, • после третьего – 8, • после k -го шага – 2 k.

Алгоритм сортировки простым слиянием • Шаг 1. Исходный файл f разбивается на два вспомогательных файла f 1 и f 2. • Шаг 2. Вспомогательные файлы f 1 и f 2 сливаются в файл f, при этом одиночные элементы образуют упорядоченные пары. • Шаг 3. Полученный файл f вновь обрабатывается, как указано в шагах 1 и 2. При этом упорядоченные пары переходят в упорядоченные четверки. • Шаг 4. Повторяя шаги, сливаем четверки в восьмерки и т. д. , каждый раз удваивая длину слитых последовательностей до тех пор, пока не будет упорядочен целиком весь файл

• Признаками конца сортировки простым слиянием являются следующие условия: – длина серии не меньше количества элементов в файле (определяется после фазы слияния); – количество серий равно 1 (определяется на фазе слияния). – при однофазной сортировке второй по счету вспомогательный файл после распределения серий остался пустым.

Анализ • После выполнения i проходов получаем два файла, состоящих из серий длины 2 i. Окончание процесса происходит при выполнении условия 2 i>=n. Следовательно, процесс сортировки простым слиянием требует порядка O(log n) проходов по данным. Исходный и вспомогательные файлы будут O(log n) раз прочитаны и столько же раз записаны. • O(n log n) • Для выполнения внешней сортировки методом простого слияния в оперативной памяти требуется расположить всего лишь две переменные – для размещения очередных элементов (записей) из вспомогательных файлов. • Устойчивость? • Естественность?

Однофазная сортировка простым слиянием • Для работы алгоритма понадобятся четыре рабочие последовательности F 1, F 2, F 3 и F 4 и входная последовательность F. • Сначала элементы из последовательности F распределяются в последовательности F 1 и F 2. Затем элементы из F 1 и F 2 сливаются и одновременно распределяются в последовательности F 3 и F 4. Далее этот процесс повторяется, но теперь сливаются элементы из F 3 и F 4 и распределяются в F 1 и F 2.

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

Сортировка естественным слиянием • Сортировка, при которой всегда сливаются две самые длинные из возможных последовательностей, является естественным слиянием. В данной сортировке объединяются серии максимальной длины.

Алгоритм сортировки естественным слиянием • Шаг 1. Исходный файл f разбивается на два вспомогательных файла f 1 и f 2. • Распределение происходит следующим образом: – Поочередно считываются записи ai исходной последовательности (неупорядоченной) таким образом, что если значения ключей соседних записей удовлетворяют условию f(ai ) f(ai+1), то записи ai+1 копируются во второй вспомогательный файл f 2. – Процедура повторяется до тех пор, пока все записи исходной последовательности не будут распределены по файлам.

• Признаками конца сортировки естественным слиянием являются следующие условия: – количество серий равно 1 (определяется на фазе слияния). – при однофазной сортировке второй по счету вспомогательный файл после распределения серий остался пустым.

• Естественное слияние, у которого после фазы распределения количество серий во вспомогательных файлах отличается друг от друга не более чем на единицу, называется сбалансированным слиянием, в противном случае – несбалансированное слияние(зачем).

Анализ • Число чтений или перезаписей файлов при использовании метода естественного слияния будет не хуже, чем применении метода простого слияния, а в среднем – даже лучше. • Но в этом методе увеличивается число сравнений за счет тех, которые требуются для распознавания концов серий. • Помимо этого, максимальный размер вспомогательных файлов может быть близок к размеру исходного файла, так как длина серий может быть произвольной.

• Временные затраты на любую последовательную сортировку пропорциональны длине последовательностей и числу проходов, т. к. при каждом проходе копируются все данные. Один из способов сократить затраты – распределять серии в более чем 2 последовательности (2 пути). • Если p – число последовательностей, то число проходов K = logpn. • Так как в каждом проходе выполняется n операций копирования, то в худшем случае: O(t)

n logpn. • Такие алгоритмы называются алгоритмами многопутевого слияния. • Многопутевое сбалансированное слияние (см методичку)

Внутренняя сортировка с внешним слиянием • Рассмотрим алгоритм сортировки, который использует как внутреннюю сортировку одним из изученных ранее способов, так и слияние, присущее внешним сортировкам. • Пусть предназначенный для сортировки файл содержит 40000 записей R 1…R 10000. Пусть во внутренней памяти машины помещается одновременно только 10000 записей. • В этом случае необходимо отсортировать во внутренней памяти каждый из четырех подфайлов R 1…R 10000, R 10001…R 20000, …, R 30001…R 40000 по отдельности, а затем слить полученные подфайлы.

• Рассмотрим работу описанного выше алгоритма на примере алгоритма сбалансированного 4 х-путевого слияния. Нам потребуется четыре дополнительных файла. • Файл 1 – R 1…R 10000. • Файл 2 – R 10001…R 20000. • Файл 3 – R 20001…R 30000. • Файл 4 – R 30001…R 40000.

• Читаем из каждого файла (1 -4) по очередной записи, выбираем из них минимальный элемент и помещаем в результирующий файл. Считываем очередной элемент из того файла, в котором был найден минимальный элемент. Процесс продолжается до тех пор, пока записи из всех 4 файлов не будут перемещены в результирующий файл. • В этом случае алгоритм проще, чем алгоритм многопутевого сбалансированного слияния. Так каждый из файлов (1 -4) содержит по одной упорядоченной серии.

Сортировка слиянием

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

Основной применяемый метод для сортировки файлов — сортировка слиянием .
Сортировка слиянием — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке.


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

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

Операция, которая однократно обрабатывает множество данных, называется фазой .

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

Процедура слияния предполагает объединение двух предварительно упорядоченных подпоследовательностей размерности n/2 в единую последовательность размерности n. Начальные элементы предварительно упорядоченных последовательностей сравниваются между собой, и из них выбирается наименьший. Соответствующий указатель перемещается на следующий элемент. Процедура повторяется до тех пор, пока не достигнут конец одной из подпоследовательностей. Оставшиеся элементы другой подпоследовательности при этом передаются в результирующую последовательность в неизменном виде.

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

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

Недостатки метода заключаются в том, что он требует дополнительной памяти по объему равной объему сортируемого файла. Поэтому для больших файлов проблематично организовать сортировку слиянием в оперативной памяти.

В случаях, когда гарантированное время сортировки важно и размещение в оперативной памяти, возможно, следует предпочесть метод сортировки слиянием.

Алгоритм двухпутевого слияния

Исходная последовательность разбивается на две подпоследовательности:

Эти две подпоследовательности объединяются в одну, содержащую упорядоченные пары.

Полученная последовательность снова разбивается на две, и пары объединяются в упорядоченные четверки:

Илон Маск рекомендует:  Выравнивание элементов форм

Полученная последовательность снова разбивается на две и собирается в упорядоченные восьмерки.

Данная операция повторяется до тех пор, пока полученная упорядоченная последовательность не будет иметь такой же размер, как у сортируемой.

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

Реализация метода двухпутевого слияния на Си

Метод нисходящего слияния

Исходная последовательность рекурсивно разбивается на половины, пока не получим подпоследовательности по 1 элементу. Из полученных подпоследовательностей формируем упорядоченные пары методом слияния, затем — упорядоченные четверки и т.д.

Разбиваем последовательность на 2 половины (рекурсивно, пока не получим пары).

Каждую подпоследовательность упорядочиваем методом слияния и получаем готовую последовательность.

Реализация метода нисходящего слияния на Си

Метод восходящего слияния

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

Реализация метода восходящего слияния на Си

Большая Энциклопедия Нефти и Газа

Внешняя сортировка

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

Внешняя сортировка выполняется в несколько этапов, и внешняя память при этом неоднократно используется для размещения данных. [2]

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

Внешняя сортировка , при которой на первом этапе группы записей сортируются в оперативной памяти и записываются па несколько лент, а на втором этапе упорядоченные группы сливаются с нескольких лент на одну. [4]

Внешняя сортировка с помощью многофазного слияния осуществляется следующим образом. [5]

Внешняя сортировка , при которой на первом этапе группы записей сортируются в оперативной памяти и записываются на несколько лент; на втором этапе упорядоченные группы сливаются с нескольких лент на одну. [6]

Вид внешней сортировки , при которой производится группировка сортируемых записей, причем каждая группа хранится в виде отдельного блока ( В. Различные блоки будут, вероятно, находиться при этом в разных запоминающих устройствах. Тогда все записи, которые могут содержать требуемый ключ, будут извлекаться из внешней памяти за одно обращение. [7]

Метод внешней сортировки , позволяющий выполнить слияние п последовательных файлов, если имеется п 1 рабочий файл. Является разновидностью метода слияния. [8]


Разделение методов внешней сортировки отражает основные различия в построении и оценках методов. В основе классификационного деления методов ( см. рис. 4.2, 2 — й уровень) лежит способ разделения сортируемого массива на группы при обмене с внешней памятью. [9]

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

Большая часть методов внешней сортировки соблюдает следующие принципы общего характера. Выполняется первый проход по сортируемому файлу, в процессе которого производится его разбиение на блоки, размер которых примерно соответствует пространству оперативной памяти, после чего выполняется сортировка этих блоков. Затем осуществляется слияние отсортированных блоков, при необходимости с этой целью выполняются несколько проходов файла, при этом с каждым проходом степень упорядоченности возрастает, пока весь файл не окажется отсортированным. Такой подход называется сортировкой-слиянием ( sort-merge), он с успехом применяется на практике с тех пор, когда компьютеры получили широкое распространение в коммерческих приложениях в пятидесятых годах прошлого столетия. [11]

Классификационная схема методов внешней сортировки ( рис. 4.2) учитывает эту особенность. [12]

Наиболее общей формой внешней сортировки является сортировка-слияние. [13]

Раздел 7.2 посвящен внешней сортировке , представляющей собой задачу полной сортировки для случая такой большой таблицы, что доступ к ней организован по частям, расположенным на внешних запоминающих устройствах. Наконец, задачи частичной сортировки — задачи выбора j — ro наибольшего имени и слияния двух упорядоченных таблиц — обсуждаются в разд. [14]

Разработать подход к внешней сортировке , который основан на разделении, подобном используемому в быстрой сортировке или в поразрядной сортировке MSD ( сначала по старшей цифре), проанализировать его и сравнить с многопутевой сортировкой. Вы можете перейти на более высокий уровень абстракции, использованный при описании сортировки-слияния в этом разделе, однако вы должны стремиться к тому, чтобы быть способными спрогнозировать время выполнения для заданного числа устройств и заданного объема оперативной памяти. [15]

TURBO PASCAL

Цель: изучение внешней сортировки

Из мира «электронных» скоростей переместимся в мир меньших скоростей, мир с механическими перемещениями и влиянием инерции. Хотя диск и делает сотни оборотов в секунду, проходят миллисекунды до момента, когда нужный запоминающий элемент окажется под головкой чтения/записи. Поэтому если любой известный нам способ упорядочения в памяти применить «механически» к данным на диске, затраты времени окажутся, скорее всего, неприемлемыми.

Сортировку данных на магнитных дисках называют внешней.

Сложности при сортировке на диске.

Исследовать, а тем более конструировать внешнюю сортировку невозможно, не представляя, мало — мальски, специфики дисков.

Диски имеют запоминающие магнитные поверхности и вращаются с| большой постоянной скоростью под головками чтения/записи. Головка обслуживает одну поверхность.

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

Головки крепятся на штанге, подобной «коромыслу» проигрывателя. После перемещения блока головок (поворота штанги) текущим становится следующий цилиндр. Цилиндры нумеруются в порядке их прохождения блоком головок при движении штанги в одну сторону. Расстоянием между элементами данных назовем разность номеров цилиндров, где они размещены.

Адресация (нумерация) элементов памяти на диске идет в пределах цилиндра с переходом по исчерпании его объема на следующий, потом на третий и т. д. Файл данных записывается по порядку адресов, но если свободного участка не хватило, продолжается в другом участке и, возможно, на другом цилиндре (случай фрагментации файла).

Изложена весьма упрощенная модель диска, но ее достаточно.

Хотя диски называют памятью прямого доступа, время обращения к данным гораздо большего порядка, чем время чтения/записи в основной памяти, по причине

а) задержки, связанной с ожиданием момента, когда нужный элемент цилиндра пройдет под головкой;
б) перемещения головок, когда требуются данные не из текущего цилиндра.

Прогон — это прохождение файла в одном направлении со считыванием данных в память и, возможно, их возвратом в файл.

Применительно к внешней сортировке это означает упорядочение возможно больших частей файла внутренней сортировкой: мы заменяем «быстрыми» перемещениями в памяти перемещения данных на диске. Уменьшая число актов их чтения и перезаписи, мы одновременно исключаем многочисленные задержки «а», «б».

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

Время внешней сортировки зависит от
а) внутренней сортировки частей файла;
б) многократного считывания и записи данных на диск;
в) ходов головки между актами считывания/записи;
г) действий в памяти при слиянии упорядоченных частей.

Сортировка методом поглощения.

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

Перед поглощением очередная часть файла считывается в зону «А» памяти, там упорядочивается и остается. Начало ранее упорядоченной части считывается в зону «В» и начинается слияние, прерываемое считыванием в зону «В», когда она опустошается. По мере заполнения зоны «С» записями акта слияния, содержимое ее переписывается в файл (на место поглощаемой части и далее в сторону конца файла). Если при слиянии взяты все записи поглощаемой части, поглощение завершается передачей в файл из зоны «С» остатка результата. Слияние также завершается, если исчерпана ранее упорядоченная часть. Поглощение ею очередной части произошло.

Ходов в данном методе будет мало и во время сортировки вы не услышите характерного поскрипывания механизма головок. Это дает экономию времени и при небольшом размере файла сортировка проходит быстро.

Челночное балансное слияние

На 1 этапе внутренней сортировки частей в файле создают М упорядоченных частей, по возможности большего размера R. К ним применяют прямое слияние.
Создают резервное дисковое пространство файла и располагают его непосредственно до или после сливаемых частей и перемещается к следующим частям по завершении слияния. Его размер не меньше размера R части. Резерв и пространство ближайшей части будут заполнено результатом слияния двух первых частей, при этом пространство 2-й части освободится и станет резервом, необходимым для слияния следующей пары частей и т. д.

По мере слияния частей резерв перемещается от начала файла к концу, потом обратно и т. д., как челнок. Поскольку место результата не удалено от сливаемых частей, ходы невелики, пока сами части небольшие. В процессе сортировки «челнок» увеличивают, ибо растут части:

а) слияние частей размером R (промежуточная ситуация)

Стрелками показано перемещение данных при слиянии.

Заметим, что резерв можно увеличивать, когда он в конце файла; это происходит один раз за 2 прогона челнока.

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

Хорошо бы ограничить рост размера «челнока», ибо этот рост увеличивает размер ходов.


Путем модификации конечных этапов слияния добьемся, чтобы этот рост остановился на размере D = 1/6 размера файла.

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

в) этап слияния (с подэтапами), когда в файле 6 частей.

г) этап слияния «по половинам » (естественное слияние), когда частей 3. Концевая часть файла на этом этапе не используется.

д) заключительный этап слияния; сначала берем для слияния первую половину конечной части и всю начальную часть:

По окончании слияния 1 выясняется, надо ли сместить остаток начальной части, чтобы освободить место для конца результата и продолжить слияние («подслияние»). Подслияние не нужно, если в ходе слияния начальная часть исчерпана, надо лишь вытеснить резерв в конец файла, переписав окончание.

И при слиянии 1, и при под слиянии размер резерва не меньше минимально требуемого.

Итак, на сегодняшнем занятии мы рассмотрели внешнюю сортировку

(с)Все права защищены

По всем интересующим вопросам прошу писать на электронный адрес

ru.knowledgr.com

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

Внешний вид слияния

Один пример внешней сортировки — внешний алгоритм вида слияния, какие куски видов, что каждый помещается в RAM, затем сливают сортированные куски вместе. Например, для сортировки 900 мегабайтов данных, используя только 100 мегабайтов RAM:

  1. Прочитайте 100 МБ данных в главной памяти и виде некоторым обычным методом, как quicksort.
  2. Напишите сортированные данные диску.
  3. Повторите шаги 1 и 2, пока все данные не находятся в сортированных кусках на 100 МБ (есть 900 МБ / 100 МБ = 9 кусков), который теперь должен быть слит в один единственный файл продукции.
  4. Прочитайте первые 10 МБ (= 100 МБ / (9 кусков + 1)) каждого сортированного куска во входные буфера в главной памяти и ассигнуйте остающиеся 10 МБ для буфера продукции. (На практике это могло бы обеспечить лучшую работу, чтобы заставить продукцию буферизовать больше и входные немного меньшего размера буфера.)
  5. Выполните слияние с 9 путями и сохраните результат в буфере продукции. Каждый раз, когда буфер продукции заполняется, напишите, что он к финалу сортировал файл, и освободите его. Каждый раз, когда любая 9 входной порожней тары буферов, заполнитесь, это со следующими 10 МБ его связанных 100 МБ сортировало кусок, пока больше данных от куска не доступно. Это — ключевой шаг, который заставляет внешний вид слияния работать внешне — потому что алгоритм слияния только делает один проход последовательно через каждый из кусков, каждый кусок не должен быть загружен полностью; скорее последовательные части куска могут быть загружены по мере необходимости.
Илон Маск рекомендует:  Что такое код domxml_open_mem

Дополнительные проходы

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

Однако есть согласование с использованием меньшего количества проходов слияния. Как число увеличений кусков, объем данных мы можем читать от каждого куска за один раз во время уменьшений процесса слияния. Для сортировки, скажем, 50 ГБ в 100 МБ RAM, используя единственный проход слияния не эффективно: диск ищет требуемый заполнить входные буфера данными от каждого из этих 500 кусков (мы читаем 100 МБ / 501

, 200 КБ от каждого куска за один раз) занимают большую часть времени вида. Используя два слияния проходы решает проблему. Тогда процесс сортировки мог бы быть похожим на это:

  1. Управляйте начальным сортирующим кусок проходом как прежде.
  2. Управляйте первым проходом слияния, объединяющим 25 кусков за один раз, приводя к 20 большим сортированным кускам.
  3. Управляйте вторым проходом слияния, чтобы слить 20 больших сортированных кусков.

Как виды в памяти, эффективные внешние виды требуют O (n, регистрируют n), время: показательные увеличения размера данных требуют линейных увеличений числа проходов. Если Вы делаете либеральное использование гигабайтов RAM обеспеченным современными компьютерами, логарифмический фактор растет очень медленно: под разумными предположениями можно было сортировать по крайней мере 500 ГБ данных, используя 1 ГБ главной памяти, прежде чем третий проход стал выгодным, и мог сортировать много раз, что, прежде чем четвертый проход стал полезным.

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

Настройка работы

Оценка Вида, созданная программистом Джимом Грэем, сравнивает внешние алгоритмы сортировки, осуществленные, используя точно настроенное аппаратное и программное обеспечение. Завоевание внедрений использует несколько методов:

  • Используя параллелизм

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

  • Увеличение скорости аппаратных средств

  • Используя большее количество RAM для сортировки может сократить количество диска, ищет, и избегите потребности в большем количестве проходов.
  • Быстро внешняя память, как 15K RPM диски или твердотельные накопители, может ускорить виды (но добавляет существенные затраты, пропорциональные размеру данных).
  • Много других факторов могут затронуть максимальную сортировку аппаратных средств скорости: скорость центрального процессора и число ядер, время ожидания доступа RAM, полоса пропускания ввода/вывода, дисковая скорость чтения-записи, диск ищет время и других. «Балансирование» аппаратных средств, чтобы минимизировать узкие места является важной частью проектирования эффективной системы сортировки.
  • Экономическая эффективность, а также абсолютная скорость может быть важной, особенно в окружающей среде группы, где более низкие затраты узла позволяют покупать больше узлов.

  • Увеличение скорости программного обеспечения

  • Некоторые Эталонные участники Вида используют изменение на виде корня для первой фазы сортировки: они разделяют данные на одно из многих «мусорных ведер», основанных в начале его стоимости. Исходные данные вида случайные и особенно подходящие к этой оптимизации.
  • Уплотняя вход, промежуточные файлы и продукция могут уменьшить время, проведенное на вводе/выводе, но не позволены в Оценке Вида.
  • Поскольку Эталонные виды Вида длинные (100-байтовые) отчеты, используя короткие (10-байтовые) ключи, сортируя программное обеспечение иногда перестраивают ключи отдельно от ценностей, чтобы уменьшить объем ввода/вывода памяти.

Другие алгоритмы

Внешний вид слияния не единственный внешний алгоритм сортировки; есть также виды распределения, которые работают, деля несортированные ценности в «ведра» меньшего размера, которые могут быть сортированы в главной памяти. Как вид слияния, у внешнего вида распределения также есть родной брат главной памяти; посмотрите вид ведра. Есть дуальность или фундаментальное подобие, между слиянием — и основанными на распределении алгоритмами, которые могут помочь в размышлении о сортировке и других внешних алгоритмах памяти. Есть оперативные алгоритмы для внешнего вида, которые не требуют больше дискового пространства, чем оригинальные данные.


Внешняя сортировка

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

Наиболее часто внешняя сортировка используется в СУБД. Основным понятием при использовании внешней сортировки является понятие отрезка. Отрезком длины K является последовательность записей A_i , A_ ,…, A_ , что в ней все записи упорядочены по некоторому ключу. Максимальное количество отрезков в файле N (все элементы не упорядочены). Минимальное количество отрезков 1 (все элементы являются упорядоченными).

Например, в некотором файле А есть одномерный массив:

12 35 65 0 24 36 3 5 84 90 6 2 30

Поделим массив на отрезки:

12 35 65 | 0 24 36 | 3 5 84 90 | 6 | 2 30

Можно сказать, что массив в файле А состоит из 5 отрезков.

Например, в некотором файле B есть одномерный массив:

1 2 3 4 5 6 7 8 9 10

Поделим массив на отрезки:

| 1 2 3 4 5 6 7 8 9 10 |

Можно сказать, что массив в файле B состоит из 1 отрезка.

Например, в некотором файле А есть одномерный массив:

20 17 16 14 13 10 9 8 6 4 3 2 0

Поделим массив на отрезки:

| 20 | 17 | 16 | 14 | 13 | 10 | 9 | 8 | 6 | 4 | 3 | 2 | 0 |

Можно сказать, что массив в файле А состоит из 13 отрезков.

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

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

Основные методы сортировок:

  1. Естественная сортировка (метод естественного слияния)
  2. Сортировка методом двухпутевого сбалансированного слияния
    1. Сортировка методом n-путевого слияния.
  3. Многофазная сортировка (Фибоначчиевая)

Напишите отзыв о статье «Внешняя сортировка»

Литература

  • Ричард Форсайт. Паскаль для всех = Pascal at Work and Play. An Introduction to Computer Programming in Pascal. — М .: Машиностроение, 1986. — 288 с.
  • Роберт Седжвик. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб. : ДиаСофтЮП, 2003. — 672 с. — ISBN 5-93772-081-4.
  • Никлаус Вирт. Алгоритмы и структуры данных. Новая версия для Оберона. — М .: ДМК Пресс, 2012. — 272 с. — ISBN 978-5-94074-734-5.
Это заготовка статьи по информатике. Вы можете помочь проекту, дополнив её.
Без сравнений
Непрактичные

Отрывок, характеризующий Внешняя сортировка

На краю дороги стоял дуб. Вероятно в десять раз старше берез, составлявших лес, он был в десять раз толще и в два раза выше каждой березы. Это был огромный в два обхвата дуб с обломанными, давно видно, суками и с обломанной корой, заросшей старыми болячками. С огромными своими неуклюжими, несимметрично растопыренными, корявыми руками и пальцами, он старым, сердитым и презрительным уродом стоял между улыбающимися березами. Только он один не хотел подчиняться обаянию весны и не хотел видеть ни весны, ни солнца.
«Весна, и любовь, и счастие!» – как будто говорил этот дуб, – «и как не надоест вам всё один и тот же глупый и бессмысленный обман. Всё одно и то же, и всё обман! Нет ни весны, ни солнца, ни счастия. Вон смотрите, сидят задавленные мертвые ели, всегда одинакие, и вон и я растопырил свои обломанные, ободранные пальцы, где ни выросли они – из спины, из боков; как выросли – так и стою, и не верю вашим надеждам и обманам».
Князь Андрей несколько раз оглянулся на этот дуб, проезжая по лесу, как будто он чего то ждал от него. Цветы и трава были и под дубом, но он всё так же, хмурясь, неподвижно, уродливо и упорно, стоял посреди их.
«Да, он прав, тысячу раз прав этот дуб, думал князь Андрей, пускай другие, молодые, вновь поддаются на этот обман, а мы знаем жизнь, – наша жизнь кончена!» Целый новый ряд мыслей безнадежных, но грустно приятных в связи с этим дубом, возник в душе князя Андрея. Во время этого путешествия он как будто вновь обдумал всю свою жизнь, и пришел к тому же прежнему успокоительному и безнадежному заключению, что ему начинать ничего было не надо, что он должен доживать свою жизнь, не делая зла, не тревожась и ничего не желая.

По опекунским делам рязанского именья, князю Андрею надо было видеться с уездным предводителем. Предводителем был граф Илья Андреич Ростов, и князь Андрей в середине мая поехал к нему.
Был уже жаркий период весны. Лес уже весь оделся, была пыль и было так жарко, что проезжая мимо воды, хотелось купаться.
Князь Андрей, невеселый и озабоченный соображениями о том, что и что ему нужно о делах спросить у предводителя, подъезжал по аллее сада к отрадненскому дому Ростовых. Вправо из за деревьев он услыхал женский, веселый крик, и увидал бегущую на перерез его коляски толпу девушек. Впереди других ближе, подбегала к коляске черноволосая, очень тоненькая, странно тоненькая, черноглазая девушка в желтом ситцевом платье, повязанная белым носовым платком, из под которого выбивались пряди расчесавшихся волос. Девушка что то кричала, но узнав чужого, не взглянув на него, со смехом побежала назад.
Князю Андрею вдруг стало от чего то больно. День был так хорош, солнце так ярко, кругом всё так весело; а эта тоненькая и хорошенькая девушка не знала и не хотела знать про его существование и была довольна, и счастлива какой то своей отдельной, – верно глупой – но веселой и счастливой жизнию. «Чему она так рада? о чем она думает! Не об уставе военном, не об устройстве рязанских оброчных. О чем она думает? И чем она счастлива?» невольно с любопытством спрашивал себя князь Андрей.

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL