Быстрая сортировка большого массива данных

В предыдущей статье был рассмотрен способ хранения большого массива данных. Использование стандартного алгоритма сортировки не целесообразно, поскольку для его сложность есть величина O(N^2), где N – количество элементов в сортируемом массиве. Для большого N будет алгоритм сортировки будет работать очень медленно. Дя сортировки больших массивов часто используют различные алгоритмы сортировки временная сложность которых O(N Log2N), эта величина при больших N. Для сравнения при N = 1 000 000 стандартному алгоритму сортировки потребуется не более чем 1012 действий, а для альтернативного алгоритма потребуется не более чем 10^7, поскольку Log2 1000000 приблизительно равен 10. Таким образом, выигрыш во времени очевиден.
Рассмотрим один из алгоритмов, который позволяет быстро отсортировать большой массив данных.
Быстрая сортировка (quick sort) - это рекурсивный алгоритм, который использует подход «разделяй и властвуй». Даже если массив элементов, который нужно отсортировать, имеет некоторый минимальный размер, процедура быстрой сортировки делит его на два под массива, а затем рекурсивно вызывает себя для их сортировки.
Исходная версия рассматриваемого алгоритма быстрой сортировки весьма проста. Если алгоритм вызывается для подмассива, содержащего нуль или один элемент, подмассив уже отсортирован и процедура заканчивается. В противном случае процедура выбирает элемент массива и использует его для разбиения массива на два подмассива. Она помещает элементы, которые меньше, чем разделяющий элемент, в первый подмассив, а оставшиеся элементы – во второй подмассив. Затем она рекурсивно вызывает себя для сортировки обоих подмассивов.
Напомним, что p – указатель на область памяти, выделенную при помощи функции GetMem , в которую был загружен большой массив. Обращение к i – ому элементу массива осуществляется следующим образом lValue:= pointer(integer(p) + I * SizeOf(TMyRecord)); копирование
procedure Quicksort(p: Pointer; min, max : LLowngint);
var
lUpper, lLow: LLowngint;
med_value: TMyRecord
begin
// Если массив содержит 0 или 1 элемент, заканчиваем.
if (min >= max) then exit;
// Определение разделяющего значения.
pointer(integer(p) + lLow * SizeOf(TMyRecord))
med_value := pointer(integer(p) + min * SizeOf(TMyRecord))^;
lLow := min
lUpper := max
repeat // Бесконечный цикл.
// Просматриваем массив от lUpper в поисках значения < med_value.
while (pointer(integer(p) + lUpper * SizeOf(TMyRecord))>= med_value) do
begin
lUpper := lUpper – 1;
if (lUpper <= lLow) then break;
end;
if (lUpper <= lLow) then
begin
pointer(integer(p) + lLow * SizeOf(TMyRecord))^:= med_value^;
break; .
end;
// Меняем значения lLow и lUpper.
Move(lUpper, lLow, SizeOf(TMyRecord));
// Просматриваем массив от lLow в поисках значения >= med_value.
lLow := lLow + 1;
while (pointer(integer(p) + lLow * SizeOf(TMyRecord)) < med_value) do
begin
lLow := lLow + 1;
if (lLow >= lUpper) then break;
end;
if (lLow >= lUpper) then begin
lLow := lUpper;
pointer(integer(p) + lUpper * SizeOf(TMyRecord)):= med_value;
break;
end;
// Меняем значения 1о и lUpper.
Move(lLow, lUpper, SizeOf(TMyRecord));
until (False);
// Сортировка двух под массивов.
Quicksort(p,min,lLow – 1);
Quicksort(p,lLow + l,max) ;
end;
В этой версии алгоритма есть несколько важных моментов, о которых стоит упомянуть. Во-первых, разделяющийся элемент med_value не включен ни в один подмассив. Это означает, что в двух под массивах содержится на один элемент меньше, чем в первоначальном массиве. Поскольку общее количество рассматриваемых элементов становится меньше, алгоритм в конечном счете закончит работу. Данная версия алгоритма использует в качестве разделителя первый элемент массива. В идеале это значение должно быть где-нибудь в середине массива, так что два подмассива будут иметь приблизительно равный размер. Однако если элементы изначально отсортированы, первый элемент будет наименьшим. В первый подмассив алгоритм не поместит ни одного элемента, и все элементы окажутся во втором. Последовательность действий алгоритма будет примерно такой, как показано далее.
1. QuickSort( 1-2-3-4-5)
2. QuickSort() и QuickSort(2-3-4-5)
3. QuickSort() и QuickSort(3-4-5)
4. QuickSort() и QuickSort(4-5)
5. QuickSort() и QuickSort(5)
В этом случае каждый вызов процедуры занимает O(N) шагов для перемещения всех элементов во второй подмассив. Поскольку алгоритм должен рекурсивно вызывать себя всего N-1 раз, сложность его равна О(N^2), что не быстрее, чем у ранее рассмотренных алгоритмов. Еще хуже тот факт, что рекурсия погружается на N-1 уровней. Для больших массивов огромная глубина рекурсии приведет к переполнению стека и аварийному завершению программы.
Существует много способов выбора разделительного элемента. Программа может использовать элемент, который на данный момент находится в середине массива. Но может случиться так, что им окажется наименьший или наибольший элемент массива. При этом один под массив будет намного больше другого, и в случае большого количества неудачных выборов, что приведет к сложности алгоритма О(N^2) и вызовет глубокую рекурсию.
Другой вариант состоит в том, чтобы просматривать массив, вычислять среднее арифметическое всех значений и использовать его как разделитель. Этот подход обычно дает неплохие результаты, но требует много дополнительной работы. Еще один проход со сложностью порядка O(N) не изменит теоретическое время выполнения алгоритма, но снизит общую производительность.
Третья стратегия заключается в том, чтобы выбрать средний из элементов в начале, конце и середине массива. Этот метод обладает значительным преимущество в скорости, так как потребуется выбрать только три элемента. Кроме того, гарантируется, что выбранный элемент не обязательно будет самым большим или самым маленьким элементом и скорее всего окажется где-нибудь в середине массива. И наконец, последний способ состоит в том, чтобы выбрать разделительный элемент случайным образом. Возможно, подходящий элемент будет получен с первой же попытки. Даже если это не так, в следующий раз, когда алгоритм поделит массив, вероятно, будет сделан лучший выбор. Вероятность постоянного выпадения наихудшего случая очень мала.
Интересно, что этот метод превращает ситуацию «небольшая вероятность того, что всегда будет плохая производительность» в ситуацию «всегда небольшая вероятность плохой производительности». Попробуем пояснить это довольно запутанное утверждение.
Когда разделяющая точка выбирается одним из способов, описанных ранее, есть небольшой шанс, что при определенной организации массива время выполнения будет О(N^2). В то время как вероятность такого начального упорядочения массива очень мала, если вы все же столкнетесь с таким распределением элементов, время выполнения алгоритма в любом случае будет O(N^2). Именно это и называется «небольшой вероятностью того, что всегда будет плохая производительность». Если точка разделения выбирается случайным образом, то начальное распределение элементов не влияет на работу алгоритма. Существует небольшая вероятность неудачного выбора элемента, однако вероятность такого выбора каждый раз чрезвычайно мала. Это и есть «всегда небольшая вероятность плохой производительности». Независимо от первоначальной организации массива существует очень маленький шанс, что время выполнения алгоритма будет порядка O(N^2).
Все же есть еще одна ситуация, которая может вызвать трудности при использовании любого из вышеперечисленных методов. Если в массиве очень мало различных значений, то алгоритм при каждом вызове будет помещать много идентичных значений в один подмассив. Например, если каждый элемент массива имеет значение 1, последовательность выполнения алгоритма будет такой, как показано далее.
1. QuiekSort(1-1-1-1-1)
2. QuickSort() и QuickSort(1-1-1-1)
3. QuickSort() и QuickSort(1-1-1)
4. QuickSort() и QuickSort(1-1)
5. QuickSort() и QuickSort(l)
Это приводит к большому уровню вложенности рекурсии и дает производительность порядка О(N^2).
Такая же ситуация возникает, если существует множество дубликатов некоторых значений. Если массив из 10 000 элементов содержит только значения от 1 до 10, то алгоритм быстро поделит массив на подмассивs, в которых будет находиться только одно значение.
Самый простой способ справиться с этой проблемой – просто игнорировать ее. Если вы знаете, что данные не имеют такого распределения, то ничего изменять не надо. Если данные имеют небольшой диапазон значений, то вам стоит рассмотреть другой алгоритм сортировки. Алгоритмы сортировки подсчетом и блочной сортировки очень эффективны для массивов, где диапазон значений данных невелик. Можно внести еще одно небольшое улучшение в алгоритм быстрой сортировки. Как и многие другие более сложные алгоритмы, данный алгоритм – не самый лучший способ для небольших списков. Например, сортировка выбором выполняется быстрее при обработке небольшого количества элементов. Вы можете улучшить работу алгоритма быстрой сортировки, останавливая рекурсию перед тем, как подсписки будут пусты, и использовать сортировку выбором, чтобы завершить процесс.
Следующий код демонстрирует алгоритм быстрой сортировки с описанными изменениями:
procedure Quicksort (list : PLLownglnt Array;min, max : LLowngint) ;
var
med_value, lUpper, lLow, i : LLowngint;
begin
// Если в списке менее Cutoff элементов, останавливаем рекурсию
// и начинаем сортировку выбором.
if (max – min < Cutoff) then begin
Selectionsort (list, min, max) ;
Exit;
end;
// Определение разделяющего значения.
i := min + Trunc (Random (max – min + 1));
// Помещаем его в начало.
med_value^ := pointer(integer(p) + i * SizeOf(TMyRecord));:= pointer(integer(p) + min * SizeOf(TMyRecord))^;
lLow := min;
lUpper:= max ;
repeat
// Бесконечный цикл.
// Просмотр списка от lUpper в поисках значения < med_value.
while (pointer(integer(p) + lUpper * SizeOf(TMyRecord))>= med_value) do
begin
lUpper := lUpper – 1;
if (lUpper <= lLow) then break;
end;
if (lUpper <= lLow) then begin
pointer(integer(p) + lLow * SizeOf(TMyRecord)) := med_value;
break;
end;
// Меняем значения lLow и lUpper.
pointer(integer(p) + lLow * SizeOf(TMyRecord)): = pointer(integer(p) + lUpper * SizeOf(TMyRecord))>=;
// Просмотр списка от lLow в поисках значения >= med_value.
lLow := lLow + 1;
while (pointer(integer(p) + lLow * SizeOf(TMyRecord)) < med_value) do
begin
lLow := lLow + 1;
if (lLow >= lUpper) then break;
end;
if (lLow >= lUpper) then begin
lLow := lUpper;
pointer(integer(p) + lUpper * SizeOf(TMyRecord)):= med_value;
break;
end;
// Меняем значения lLow и lUpper.
pointer(integer(p) + lUpper * SizeOf(TMyRecord)):= pointer(integer(p) + lLow * SizeOf(TMyRecord));
until (False) ;
// Сортировка двух подсписков.
Quicksort (list,min,lLow – 1);
Quicksort (list, lLow + l,max) ;
end;

Share

Tags: ,

22 Responses to “Быстрая сортировка большого массива данных”

  1. Soviet пишет:

    Ссылки как то непонятно отображаются…

  2. PrireHimbmore пишет:

    отличный сайт, мне очень понравился, спасибо автору

  3. seoblogst пишет:

    horoshiy post! retwitnu!

  4. Avewlyrer пишет:

    Присоединяюсь. И я с этим столкнулся.

  5. seomaestro пишет:

    Шикарный пост! Очень понравился)

  6. cipaffite пишет:

    у вашего сайта приятный дизайн, сами верстали?

    российская родословная

  7. Paradi пишет:

    Почем у вас верхний баннер на сутки?

  8. 30 $ в месяц. Если вас это интересует, то напишите в коментариях, а далее обсудим в личной переписке по e-mail

  9. Паради пишет:

    Отличный пост! поставлю ссылку на вас……

    У вас в RSS картинки не показывает……

  10. мы обновили скрипты нашего сайта. попробуйте сей час и сообщите нам если у вас не получилось.

  11. topfacebookgames пишет:

    fk-uran.com.ua is my top site, i love to come back here

  12. legalsteroids пишет:

    I like fk-uran.com.ua , bookmarked !

  13. legalsteroids пишет:

    fk-uran.com.ua is cool !
    whey protein plus

  14. Аноним пишет:

    Давно эта тема не поднималась)
    Смотрю народ оживился

  15. Аноним пишет:

    Полезная информация.

  16. Аноним пишет:

    Не жалею, что потратил пару минут на чтение. Пишите почаще, еще непременно зайду почитать что-то новенькое.

  17. Аноним пишет:

    Спасибо за статью, всегда рад почитать вас!

  18. aaCderseShace пишет:

    Hey I like your blog. I actually just started one of my own, learned a lot from this website. Thank you

  19. Destroy пишет:

    Спасибо, за статью)

  20. Аноним пишет:

    дааааа. не плохие уже

  21. Аноним пишет:

    В этом что-то есть. Понятно, большое спасибо за помощь в этом вопросе.

  22. Robertlala пишет:

    славный вебресурс Обувь Step3000.

Leave a Reply