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

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

Визуализация алгоритма быстрой сортировки. Горизонтальные линии обозначают опорные элементы.
Предназначение	Алгоритм сортировки
Худшее время	O(n2)
Лучшее время	O(n log n) (обычное разделение) или O(n) (разделение на 3 части)
Среднее время	O(n log n)
Затраты памяти	O(n) вспомогательных O(log n) вспомогательных (Седжвик 1978)

Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем <math>O(n \log n)</math> обменов при упорядочении <math>n</math> элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

Общее описание

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

Общая идея алгоритма состоит в следующем:

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

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

Хоар разработал этот метод применительно к машинному переводу; словарь хранился на магнитной ленте, и сортировка слов обрабатываемого текста позволяла получить их переводы за один прогон ленты, без перемотки её назад. Алгоритм был придуман Хоаром во время его пребывания в Советском Союзе, где он обучался в Московском университете компьютерному переводу и занимался разработкой русско-английского разговорника.

Алгоритм

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

1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. Для корректности алгоритма значение этого элемента должно быть между максимальным и минимальным значениями в массиве (включительно). С точки зрения повышения эффективности алгоритма выгоднее всего выбирать медиану; но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом. Часто хороший результат даёт выбор в качестве опорного элемента среднего арифметического между минимальным и максимальным элементами массива, особенно для целых чисел (в этом случае опорный элемент не обязан быть элементом сортируемого массива).
2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный — справа от него. Обычный алгоритм операции:
   1. Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.
   2. Вычисляется значение опорного элемента m по одной из стратегий.
   3. Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше или равен опорному.
   4. Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше или равен опорному.
   5. Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
   6. Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, так же изменяется индекс опорного элемента и алгоритм продолжает своё выполнение.
3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
4. Базой рекурсии являются наборы: пустой или состоящий из одного элемента, которые возвращаются в исходном виде. Все такие отрезки уже упорядочены в процессе разделения.

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

Оценка сложности алгоритма

Ясно, что операция разделения массива на две части относительно опорного элемента занимает время <math>O(n)</math>. Поскольку все операции разделения, проделываемые на одной глубине рекурсии, обрабатывают разные части исходного массива, размер которого постоянен, суммарно на каждом уровне рекурсии потребуется также <math>O(n)</math> операций. Следовательно, общая сложность алгоритма определяется лишь количеством разделений, то есть глубиной рекурсии. Глубина рекурсии, в свою очередь, зависит от сочетания входных данных и способа определения опорного элемента.

Лучший случай.

В наиболее сбалансированном варианте при каждой операции разделения массив делится на две почти одинаковые части, следовательно, максимальная глубина рекурсии, при которой размеры обрабатываемых подмассивов достигнут 1, составит <math>\log_2 n</math>. В результате количество сравнений, совершаемых быстрой сортировкой, было бы равно значению рекурсивного выражения <math>C_n = 2 \cdot C_{n/2} + n</math>, что даёт общую сложность алгоритма <math>O(n \cdot \log_2 n)</math>.

Среднее.

Среднюю сложность при случайном распределении входных данных можно оценить лишь вероятностно.

Прежде всего необходимо заметить, что в действительности необязательно, чтобы опорный элемент всякий раз делил массив на две одинаковых части. Например, если на каждом этапе будет происходить разделение на массивы длиной 75 % и 25 % от исходного, глубина рекурсии будет равна <math>\log_{4/3} n</math>, а это по-прежнему даёт сложность <math>O(n \log n)</math>. Вообще, при любом фиксированном соотношении между левой и правой частями разделения сложность алгоритма будет той же, только с разными константами.

Будем считать «удачным» разделением такое, при котором опорный элемент окажется среди центральных 50 % элементов разделяемой части массива; ясно, вероятность удачи при случайном распределении элементов составляет 0,5. При удачном разделении размеры выделенных подмассивов составят не менее 25 % и не более 75 % от исходного. Поскольку каждый выделенный подмассив также будет иметь случайное распределение, все эти рассуждения применимы к любому этапу сортировки и любому исходному фрагменту массива.

Удачное разделение даёт глубину рекурсии не более <math>\log_{4/3} n</math>. Поскольку вероятность удачи равна 0,5, для получения <math>k</math> удачных разделений в среднем потребуется <math>2 \cdot k</math> рекурсивных вызовов, чтобы опорный элемент k раз оказался среди центральных 50 % массива. Применяя эти соображения, можно заключить, что в среднем глубина рекурсии не превысит <math>2 \cdot \log_{4/3} n</math>, что равно <math>O(\log n)</math> А поскольку на каждом уровне рекурсии по-прежнему выполняется не более <math>O(n)</math> операций, средняя сложность составит <math>O(n \log n)</math>.

Худший случай.

В самом несбалансированном варианте каждое разделение даёт два подмассива размерами 1 и <math>n-1</math>, то есть при каждом рекурсивном вызове больший массив будет на 1 короче, чем в предыдущий раз. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых. При простейшем выборе опорного элемента — первого или последнего в массиве, — такой эффект даст уже отсортированный (в прямом или обратном порядке) массив, для среднего или любого другого фиксированного элемента «массив худшего случая» также может быть специально подобран. В этом случае потребуется <math>n-1</math> операций разделения, а общее время работы составит <math>\textstyle\sum_{i=0}^n (n-i) = O(n^2)</math> операций, то есть сортировка будет выполняться за квадратичное время. Но количество обменов и, соответственно, время работы — это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти (переполнению стека) во время работы программы.

Достоинства и недостатки

Достоинства:

• Один из самых быстродействующих (на практике) из алгоритмов внутренней сортировки общего назначения.
• Прост в реализации.
• Требует лишь <math>O(\lg n)</math> дополнительной памяти для своей работы. (Не улучшенный рекурсивный алгоритм в худшем случае <math>O(n \log n)</math> памяти)
• Хорошо сочетается с механизмами кэширования и виртуальной памяти.
• Допускает естественное распараллеливание (сортировка выделенных подмассивов в параллельно выполняющихся подпроцессах).
• Допускает эффективную модификацию для сортировки по нескольким ключам (в частности — алгоритм Седжвика для сортировки строк): благодаря тому, что в процессе разделения автоматически выделяется отрезок элементов, равных опорному, этот отрезок можно сразу же сортировать по следующему ключу.
• Работает на связных списках и других структурах с последовательным доступом, допускающих эффективный проход как от начала к концу, так и от конца к началу.

Недостатки:

• Сильно деградирует по скорости (до <math>O(n^2)</math>) в худшем или близком к нему случае, что может случиться при неудачных входных данных.
• Прямая реализация в виде функции с двумя рекурсивными вызовами может привести к ошибке переполнения стека, так как в худшем случае ей может потребоваться сделать <math>O(n)</math> вложенных рекурсивных вызовов.
• Неустойчив.

Улучшения

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

Что касается первой проблемы, то она элементарно решается путём расширения ключа исходным индексом элемента в массиве. В случае равенства основных ключей сравнение производится по индексу, исключая, таким образом, возможность изменения взаимного положения равных элементов. Эта модификация не бесплатна — она требует дополнительно O(n) памяти и одного полного прохода по массиву для сохранения исходных индексов.

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

• Выбор среднего элемента. Устраняет деградацию для предварительно отсортированных данных, но оставляет возможность случайного появления или намеренного подбора «плохого» массива.
• Выбор медианы из трёх элементов: первого, среднего и последнего. Снижает вероятность возникновения худшего случая, по сравнению с выбором среднего элемента.
• Случайный выбор. Вероятность случайного возникновения худшего случая становится исчезающе малой, а намеренный подбор — практически неосуществимым. Ожидаемое время выполнения алгоритма сортировки составляет O(n lg n).

Недостаток всех усложнённых методов выбора опорного элемента — дополнительные накладные расходы; впрочем, они не так велики.

Во избежание отказа программы из-за большой глубины рекурсии могут применяться следующие методы:

• При достижении нежелательной глубины рекурсии переходить на сортировку другими методами, не требующими рекурсии. Примером такого подхода является алгоритм Introsort или некоторые реализации быстрой сортировки в библиотеке STL. Можно заметить, что алгоритм очень хорошо подходит для такого рода модификаций, так как на каждом этапе позволяет выделить непрерывный отрезок исходного массива, предназначенный для сортировки, и то, каким методом будет отсортирован этот отрезок, никак не влияет на обработку остальных частей массива.
• Модификация алгоритма, устраняющая одну ветвь рекурсии: вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры. С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит <math>O(\lg n)</math>, а в худшем случае вырожденного разделения она вообще будет не более 2 — вся обработка пройдёт в цикле первого уровня рекурсии. Правда, применение этого метода не спасёт от катастрофического падения производительности, но переполнения стека не будет.
• Разбивать массив не на две, а на три части.

Применение

• в JDK 1.8 (и ниже) утилитный метод java.util.Arrays#sort() , перегруженый для примитивных типов (Dual Pivot Quicksort реализация). Из-за неустойчивости (unstable) для сложных типов (Object) применяются другие алгоритмы (например, сортировка слиянием или timsort)
• C++ STL qsort функция www.cplusplus.com/reference/cstdlib/qsort/ = Timsort =

См. также

• Список алгоритмов сортировки

Литература

• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 7. Быстрая сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 198-219. — ISBN 5-8459-0857-4.

Ссылки

• [www.sorting-algorithms.com/quick-sort Анимированное сравнение алгоритмов сортировки]
• Визуализаторы: [rain.ifmo.ru/cat/view.php/vis/sorts/quicksort-2004], [rain.ifmo.ru/cat/view.php/vis/sorts/quicksort-2000], [prototype-nk.ru/quicksort.html]
• [airtucha.github.io/SortVis/ Динамическая визуализация 7 алгоритмов сортировки с открытым исходным кодом]

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

– Ничего, ничего, разве не все равно! На один день мы в гостиную перейдем. Можно всю нашу половину им отдать.
– Ну, уж вы, барышня, придумаете! Да хоть и в флигеля, в холостую, к нянюшке, и то спросить надо.
– Ну, я спрошу.
Наташа побежала в дом и на цыпочках вошла в полуотворенную дверь диванной, из которой пахло уксусом и гофманскими каплями.
– Вы спите, мама?
– Ах, какой сон! – сказала, пробуждаясь, только что задремавшая графиня.
– Мама, голубчик, – сказала Наташа, становясь на колени перед матерью и близко приставляя свое лицо к ее лицу. – Виновата, простите, никогда не буду, я вас разбудила. Меня Мавра Кузминишна послала, тут раненых привезли, офицеров, позволите? А им некуда деваться; я знаю, что вы позволите… – говорила она быстро, не переводя духа.
– Какие офицеры? Кого привезли? Ничего не понимаю, – сказала графиня.
Наташа засмеялась, графиня тоже слабо улыбалась.
– Я знала, что вы позволите… так я так и скажу. – И Наташа, поцеловав мать, встала и пошла к двери.
В зале она встретила отца, с дурными известиями возвратившегося домой.
– Досиделись мы! – с невольной досадой сказал граф. – И клуб закрыт, и полиция выходит.
– Папа, ничего, что я раненых пригласила в дом? – сказала ему Наташа.
– Разумеется, ничего, – рассеянно сказал граф. – Не в том дело, а теперь прошу, чтобы пустяками не заниматься, а помогать укладывать и ехать, ехать, ехать завтра… – И граф передал дворецкому и людям то же приказание. За обедом вернувшийся Петя рассказывал свои новости.
Он говорил, что нынче народ разбирал оружие в Кремле, что в афише Растопчина хотя и сказано, что он клич кликнет дня за два, но что уж сделано распоряжение наверное о том, чтобы завтра весь народ шел на Три Горы с оружием, и что там будет большое сражение.
Графиня с робким ужасом посматривала на веселое, разгоряченное лицо своего сына в то время, как он говорил это. Она знала, что ежели она скажет слово о том, что она просит Петю не ходить на это сражение (она знала, что он радуется этому предстоящему сражению), то он скажет что нибудь о мужчинах, о чести, об отечестве, – что нибудь такое бессмысленное, мужское, упрямое, против чего нельзя возражать, и дело будет испорчено, и поэтому, надеясь устроить так, чтобы уехать до этого и взять с собой Петю, как защитника и покровителя, она ничего не сказала Пете, а после обеда призвала графа и со слезами умоляла его увезти ее скорее, в эту же ночь, если возможно. С женской, невольной хитростью любви, она, до сих пор выказывавшая совершенное бесстрашие, говорила, что она умрет от страха, ежели не уедут нынче ночью. Она, не притворяясь, боялась теперь всего.


M me Schoss, ходившая к своей дочери, еще болоо увеличила страх графини рассказами о том, что она видела на Мясницкой улице в питейной конторе. Возвращаясь по улице, она не могла пройти домой от пьяной толпы народа, бушевавшей у конторы. Она взяла извозчика и объехала переулком домой; и извозчик рассказывал ей, что народ разбивал бочки в питейной конторе, что так велено.
После обеда все домашние Ростовых с восторженной поспешностью принялись за дело укладки вещей и приготовлений к отъезду. Старый граф, вдруг принявшись за дело, всё после обеда не переставая ходил со двора в дом и обратно, бестолково крича на торопящихся людей и еще более торопя их. Петя распоряжался на дворе. Соня не знала, что делать под влиянием противоречивых приказаний графа, и совсем терялась. Люди, крича, споря и шумя, бегали по комнатам и двору. Наташа, с свойственной ей во всем страстностью, вдруг тоже принялась за дело. Сначала вмешательство ее в дело укладывания было встречено с недоверием. От нее всё ждали шутки и не хотели слушаться ее; но она с упорством и страстностью требовала себе покорности, сердилась, чуть не плакала, что ее не слушают, и, наконец, добилась того, что в нее поверили. Первый подвиг ее, стоивший ей огромных усилий и давший ей власть, была укладка ковров. У графа в доме были дорогие gobelins и персидские ковры. Когда Наташа взялась за дело, в зале стояли два ящика открытые: один почти доверху уложенный фарфором, другой с коврами. Фарфора было еще много наставлено на столах и еще всё несли из кладовой. Надо было начинать новый, третий ящик, и за ним пошли люди.
– Соня, постой, да мы всё так уложим, – сказала Наташа.
– Нельзя, барышня, уж пробовали, – сказал буфетчнк.
– Нет, постой, пожалуйста. – И Наташа начала доставать из ящика завернутые в бумаги блюда и тарелки.
– Блюда надо сюда, в ковры, – сказала она.
– Да еще и ковры то дай бог на три ящика разложить, – сказал буфетчик.
– Да постой, пожалуйста. – И Наташа быстро, ловко начала разбирать. – Это не надо, – говорила она про киевские тарелки, – это да, это в ковры, – говорила она про саксонские блюда.
– Да оставь, Наташа; ну полно, мы уложим, – с упреком говорила Соня.
– Эх, барышня! – говорил дворецкий. Но Наташа не сдалась, выкинула все вещи и быстро начала опять укладывать, решая, что плохие домашние ковры и лишнюю посуду не надо совсем брать. Когда всё было вынуто, начали опять укладывать. И действительно, выкинув почти все дешевое, то, что не стоило брать с собой, все ценное уложили в два ящика. Не закрывалась только крышка коверного ящика. Можно было вынуть немного вещей, но Наташа хотела настоять на своем. Она укладывала, перекладывала, нажимала, заставляла буфетчика и Петю, которого она увлекла за собой в дело укладыванья, нажимать крышку и сама делала отчаянные усилия.
– Да полно, Наташа, – говорила ей Соня. – Я вижу, ты права, да вынь один верхний.
– Не хочу, – кричала Наташа, одной рукой придерживая распустившиеся волосы по потному лицу, другой надавливая ковры. – Да жми же, Петька, жми! Васильич, нажимай! – кричала она. Ковры нажались, и крышка закрылась. Наташа, хлопая в ладоши, завизжала от радости, и слезы брызнули у ней из глаз. Но это продолжалось секунду. Тотчас же она принялась за другое дело, и уже ей вполне верили, и граф не сердился, когда ему говорили, что Наталья Ильинишна отменила его приказанье, и дворовые приходили к Наташе спрашивать: увязывать или нет подводу и довольно ли она наложена? Дело спорилось благодаря распоряжениям Наташи: оставлялись ненужные вещи и укладывались самым тесным образом самые дорогие.
Но как ни хлопотали все люди, к поздней ночи еще не все могло быть уложено. Графиня заснула, и граф, отложив отъезд до утра, пошел спать.
Соня, Наташа спали, не раздеваясь, в диванной. В эту ночь еще нового раненого провозили через Поварскую, и Мавра Кузминишна, стоявшая у ворот, заворотила его к Ростовым. Раненый этот, по соображениям Мавры Кузминишны, был очень значительный человек. Его везли в коляске, совершенно закрытой фартуком и с спущенным верхом. На козлах вместе с извозчиком сидел старик, почтенный камердинер. Сзади в повозке ехали доктор и два солдата.
– Пожалуйте к нам, пожалуйте. Господа уезжают, весь дом пустой, – сказала старушка, обращаясь к старому слуге.
– Да что, – отвечал камердинер, вздыхая, – и довезти не чаем! У нас и свой дом в Москве, да далеко, да и не живет никто.
– К нам милости просим, у наших господ всего много, пожалуйте, – говорила Мавра Кузминишна. – А что, очень нездоровы? – прибавила она.
Камердинер махнул рукой.
– Не чаем довезти! У доктора спросить надо. – И камердинер сошел с козел и подошел к повозке.
– Хорошо, – сказал доктор.
Камердинер подошел опять к коляске, заглянул в нее, покачал головой, велел кучеру заворачивать на двор и остановился подле Мавры Кузминишны.
– Господи Иисусе Христе! – проговорила она.
Мавра Кузминишна предлагала внести раненого в дом.
– Господа ничего не скажут… – говорила она. Но надо было избежать подъема на лестницу, и потому раненого внесли во флигель и положили в бывшей комнате m me Schoss. Раненый этот был князь Андрей Болконский.


Наступил последний день Москвы. Была ясная веселая осенняя погода. Было воскресенье. Как и в обыкновенные воскресенья, благовестили к обедне во всех церквах. Никто, казалось, еще не мог понять того, что ожидает Москву.
Только два указателя состояния общества выражали то положение, в котором была Москва: чернь, то есть сословие бедных людей, и цены на предметы. Фабричные, дворовые и мужики огромной толпой, в которую замешались чиновники, семинаристы, дворяне, в этот день рано утром вышли на Три Горы. Постояв там и не дождавшись Растопчина и убедившись в том, что Москва будет сдана, эта толпа рассыпалась по Москве, по питейным домам и трактирам. Цены в этот день тоже указывали на положение дел. Цены на оружие, на золото, на телеги и лошадей всё шли возвышаясь, а цены на бумажки и на городские вещи всё шли уменьшаясь, так что в середине дня были случаи, что дорогие товары, как сукна, извозчики вывозили исполу, а за мужицкую лошадь платили пятьсот рублей; мебель же, зеркала, бронзы отдавали даром.
В степенном и старом доме Ростовых распадение прежних условий жизни выразилось очень слабо. В отношении людей было только то, что в ночь пропало три человека из огромной дворни; но ничего не было украдено; и в отношении цен вещей оказалось то, что тридцать подвод, пришедшие из деревень, были огромное богатство, которому многие завидовали и за которые Ростовым предлагали огромные деньги. Мало того, что за эти подводы предлагали огромные деньги, с вечера и рано утром 1 го сентября на двор к Ростовым приходили посланные денщики и слуги от раненых офицеров и притаскивались сами раненые, помещенные у Ростовых и в соседних домах, и умоляли людей Ростовых похлопотать о том, чтоб им дали подводы для выезда из Москвы. Дворецкий, к которому обращались с такими просьбами, хотя и жалел раненых, решительно отказывал, говоря, что он даже и не посмеет доложить о том графу. Как ни жалки были остающиеся раненые, было очевидно, что, отдай одну подводу, не было причины не отдать другую, все – отдать и свои экипажи. Тридцать подвод не могли спасти всех раненых, а в общем бедствии нельзя было не думать о себе и своей семье. Так думал дворецкий за своего барина.
Проснувшись утром 1 го числа, граф Илья Андреич потихоньку вышел из спальни, чтобы не разбудить к утру только заснувшую графиню, и в своем лиловом шелковом халате вышел на крыльцо. Подводы, увязанные, стояли на дворе. У крыльца стояли экипажи. Дворецкий стоял у подъезда, разговаривая с стариком денщиком и молодым, бледным офицером с подвязанной рукой. Дворецкий, увидав графа, сделал офицеру и денщику значительный и строгий знак, чтобы они удалились.
– Ну, что, все готово, Васильич? – сказал граф, потирая свою лысину и добродушно глядя на офицера и денщика и кивая им головой. (Граф любил новые лица.)
– Хоть сейчас запрягать, ваше сиятельство.
– Ну и славно, вот графиня проснется, и с богом! Вы что, господа? – обратился он к офицеру. – У меня в доме? – Офицер придвинулся ближе. Бледное лицо его вспыхнуло вдруг яркой краской.
– Граф, сделайте одолжение, позвольте мне… ради бога… где нибудь приютиться на ваших подводах. Здесь у меня ничего с собой нет… Мне на возу… все равно… – Еще не успел договорить офицер, как денщик с той же просьбой для своего господина обратился к графу.
– А! да, да, да, – поспешно заговорил граф. – Я очень, очень рад. Васильич, ты распорядись, ну там очистить одну или две телеги, ну там… что же… что нужно… – какими то неопределенными выражениями, что то приказывая, сказал граф. Но в то же мгновение горячее выражение благодарности офицера уже закрепило то, что он приказывал. Граф оглянулся вокруг себя: на дворе, в воротах, в окне флигеля виднелись раненые и денщики. Все они смотрели на графа и подвигались к крыльцу.
– Пожалуйте, ваше сиятельство, в галерею: там как прикажете насчет картин? – сказал дворецкий. И граф вместе с ним вошел в дом, повторяя свое приказание о том, чтобы не отказывать раненым, которые просятся ехать.
– Ну, что же, можно сложить что нибудь, – прибавил он тихим, таинственным голосом, как будто боясь, чтобы кто нибудь его не услышал.
В девять часов проснулась графиня, и Матрена Тимофеевна, бывшая ее горничная, исполнявшая в отношении графини должность шефа жандармов, пришла доложить своей бывшей барышне, что Марья Карловна очень обижены и что барышниным летним платьям нельзя остаться здесь. На расспросы графини, почему m me Schoss обижена, открылось, что ее сундук сняли с подводы и все подводы развязывают – добро снимают и набирают с собой раненых, которых граф, по своей простоте, приказал забирать с собой. Графиня велела попросить к себе мужа.
– Что это, мой друг, я слышу, вещи опять снимают?
– Знаешь, ma chere, я вот что хотел тебе сказать… ma chere графинюшка… ко мне приходил офицер, просят, чтобы дать несколько подвод под раненых. Ведь это все дело наживное; а каково им оставаться, подумай!.. Право, у нас на дворе, сами мы их зазвали, офицеры тут есть. Знаешь, думаю, право, ma chere, вот, ma chere… пускай их свезут… куда же торопиться?.. – Граф робко сказал это, как он всегда говорил, когда дело шло о деньгах. Графиня же привыкла уж к этому тону, всегда предшествовавшему делу, разорявшему детей, как какая нибудь постройка галереи, оранжереи, устройство домашнего театра или музыки, – и привыкла, и долгом считала всегда противоборствовать тому, что выражалось этим робким тоном.
Она приняла свой покорно плачевный вид и сказала мужу:
– Послушай, граф, ты довел до того, что за дом ничего не дают, а теперь и все наше – детское состояние погубить хочешь. Ведь ты сам говоришь, что в доме на сто тысяч добра. Я, мой друг, не согласна и не согласна. Воля твоя! На раненых есть правительство. Они знают. Посмотри: вон напротив, у Лопухиных, еще третьего дня все дочиста вывезли. Вот как люди делают. Одни мы дураки. Пожалей хоть не меня, так детей.
Граф замахал руками и, ничего не сказав, вышел из комнаты.
– Папа! об чем вы это? – сказала ему Наташа, вслед за ним вошедшая в комнату матери.
– Ни о чем! Тебе что за дело! – сердито проговорил граф.
– Нет, я слышала, – сказала Наташа. – Отчего ж маменька не хочет?
– Тебе что за дело? – крикнул граф. Наташа отошла к окну и задумалась.
– Папенька, Берг к нам приехал, – сказала она, глядя в окно.


Берг, зять Ростовых, был уже полковник с Владимиром и Анной на шее и занимал все то же покойное и приятное место помощника начальника штаба, помощника первого отделения начальника штаба второго корпуса.
Он 1 сентября приехал из армии в Москву.
Ему в Москве нечего было делать; но он заметил, что все из армии просились в Москву и что то там делали. Он счел тоже нужным отпроситься для домашних и семейных дел.