Предыдущая часть:
Сегодня у нас будет не куча песка, а куча камней. И задание на этот раз такое: отсортировать все камни по размеру. Какой ужас!
Вы наверное уже догадались, что "Программист с лопатой" это специальный цикл материалов, где мы рассматриваем прямую связь затрат времени и энергии в реальном мире и в программной модели.
Если нам удаётся найти способ сократить затраты в реальном мире, то этим же способом можно воспользоваться и в программировании – и для этого не нужно быть программистом.
Как поступит обычный человек?
Для начала возьмём из кучи любой камень.
Мы положим его на первое место, затем возьмём из кучи второй камень. И сравним с тем, который уже положили. Если второй камень меньше, мы положим его первым, а если больше, то вторым. Затем возьмём из кучи третий камень и сравним с этими двумя...
Нетрудно подсчитать, сколько действий надо совершить. Если в куче содержится N камней, то в первый раз мы сравниваем камень с 0 других камней, во второй раз с 1 камнем, в третий раз с 2 камнями, и в N-й раз с N-1 камнями. Это сумма последовательности 1+2+3+...+N-1.
Общее количество сравнений получается порядка N^2 / 2. То есть это квадратичная зависимость O(N^2), о которой я писал уже давно в отдельном материале:
Можно ли сортировать быстрее?
Быстрая сортировка
В реальном мире у нас есть огромное преимущество: мы можем навзгляд определить, какое примерно место должен занять наш очередной камень в отсортированном ряду, поэтому сравнивать его со всеми не понадобится. В программном коде нам в любом случае требуется прилежно сравнивать кандидата со всеми, кто уже занял место.
Как можно оптимизировать данный процесс? У нас нет возможности программно "на глазок" оценить размер камня и сразу найти ему подходящее место. Но мы можем сделать что-то подобное, руководствуясь опять же примером из реального мира.
Что, если у вас нет сил или желания сортировать всю кучу? Тогда, возможно, вы сделаете это по минимуму: выберете некий камень как образец, а затем все камни, которые больше него, перекидаете в отдельную кучу. Вы получите две кучи. Каждая из них внутри себя будет неотсортирована, но относительно друг друга они уже отсортированы, так как любой камень из первой кучи всегда будет меньше, чем любой камень из второй.
...и теперь можно повторить то же самое с каждой кучей. Снова выбрать любой камень и разделить кучу на две других. И опять они окажутся отсортированными друг относительно друга.
Мы можем так продолжать, пока в каждой образовавшейся куче не останется всего по одному камню. Куча становится отсортированной внутри себя, так как содержит только один камень. А между собой кучи уже и так отсортированы. И мы получаем общую кучу, уже полностью отсортированную.
Сколько же операций это займёт?
Для определённости будем считать, что куча всегда делится пополам. Сколько делений надо сделать, чтобы дойти до размера кучи в один камень?
- После первого деления мы имеем 2 кучи размером N/2.
- После второго деления – 4 кучи размером N/4.
- После третьего деления – 8 куч размером N/8.
В последнем делении получится N куч размером N/N, то есть 1.
Последовательность получается такая:
2, 4, 8, ..., N
Можно заметить, что 2, 4, 8 это степени двойки, так как на каждом следующем этапе количество куч увеличивается в 2 раза.
Значит, финальное количество куч N достигается на этапе, который равен какой-то степени двойки. Она вычисляется как log2 N.
log2 N это логарифм числа N по основанию 2, который означает, что 2 в этой степени будет равно N.
Посмотрим пример. Допустим, N = 64. Тогда 2 в степени 6 равно 64. Значит, логарифм числа 64 по основанию 2 это 6. И для сортировки кучи из 64 камней потребуется 6 этапов деления.
Но это ещё не всё. На каждом этапе мы берём из каждой кучи один камень и сравниваем с ним все остальные камни. Значит, делаем N-1 сравнений. Чтобы не загромождать изложение, я буду считать просто N.
Итак, посмотрим:
- Первый этап: есть 1 куча, мы делаем N сравнений.
- Второй этап: есть 2 кучи, делаем N/2 сравнений в каждой, то есть 2 * N/2 = N
- Третий этап: есть 4 кучи, делаем N/4 сравнений в каждой, то есть 4 * N/4 = N
Как видим, на любом этапе всегда происходит N сравнений.
Итого, общее количество сравнений:
N * log2 N
Сравним оценки двух методов при N = 64:
Простая сортировка: N^2 / 2 = 64 * 64 / 2 = 2048 сравнений
Быстрая сортировка: N * log2 N = 64 * 6 = 384 сравнения
Итак, быстрая сортировка работает в разы быстрее. Этот алгоритм так и называется: quicksort. И вы можете применять его не только в программировании, но и в реальной жизни.
Но есть нюанс
Оценка N * log2 N справедлива только для случая, когда куча всякий раз уменьшает свой размер в 2 раза. Но это идеальный случай. Чтобы куча поделилась на 2 равные части, нужно выбрать такой камень, чтобы половина оставшихся камней была меньше, а другая половина больше.
Первая проблема это выбор правильного камня. Опять же, не имея возможности сделать оценку на глазок, мы выбираем какой-нибудь камень, а дальше нам повезёт или нет. Если это оказался самый маленький или самый большой камень в куче, то естественно, что куча поделится не на 2 равные части, а на один этот камень и всю остальную кучу. Из этой кучи мы опять выберем камень и опять можем выбрать неудачно. Так как размер кучи будет на каждом шаге уменьшаться не в 2 раза, а всего лишь на 1, то там придётся сделать не log2 N шагов, а N шагов, чтобы прийти к размеру кучи 1.
И тогда количество операций опять станет квадратичного порядка.
Вторая проблема это разнообразие камней в куче. Если скажем все они имеют одинаковый размер, то какой камень ни выбирай, а результат снова окажется плачевным. Куча просто не захочет делиться пополам.
В среднем, статистически, алгоритм quicksort работает очень хорошо и приближается к своим идеальным оценкам.
Но нужно понимать, когда он просто не будет работать. Для решения возникающих проблем применяют дополнительные методы, ну а мы пока остановимся здесь и порадуемся, что в реальной жизни мы сразу поймём, как правильно начать сортировку.
