Алгоритмы сортировки. Быстрая сортировка (quicksort). Сортировка с помощью кучи (heapsort). Сортировки за линейное время

Лекция 2: Алгоритмы сортировки

0  Intro

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

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

Предполагается, что вам известны общеизвестные алгоритмы сортировки, работающие за время O(n²). Это такие сортировки, как сортировка вставками, обменные сортировки, сортировка выбором и прочие.

За рамки данной лекции также выходит ознакомление с некоторыми интересными более в исследовательском плане сортировками (например, сортировка Шелла).

1  Быстрая сортировка (quicksort)

Эта сортировка известна всем. Даже те, кто о ней ничего не знают, всё же слышали это название. Она очень популярна. Чрезмерно популярна. Потому что эта сортировка действительно является быстрой. Ожидаемое время её работы равно Θ(nlogn), причём константа при nlogn мала по сравнению с алгоритмами с аналогичной асимптотической оценкой. Поэтому-то алгоритм быстрой сортировки и обходит в общем случае практически все остальные алгоритмы сортировки, хотя в худшем случае он срабатывает за время O(n²).

1.1  Описание алгоритма

Быстрая сортировка работает по принципу «разделяй и властвуй», поэтому является рекурсивной.

Сортировка участка A[p..r] массива A происходит так:

§  Разделение (partition). Элементы массива A переставляются так, чтобы любой из элементов A[p], ..., A[q] был не больше любого из элементов A[q + 1], ..., A[r], где q – некоторое число (p <= q < r).

§  Процедура сортировки рекурсивно вызывается для массивов A[p..q] и A[q+1..r].

По окончании работы алгоритма массив A[p..r] отсортирован.

Как видно, данный алгоритм достаточно прост. Осталось только разобраться с разделением массива на части.

1.1.1  Разделение массива

Для разделения из массива берётся некое число x, относительно которого будет производиться сравнение (берётся первый или средний или последний или случайный элемент сортируемого массива).

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

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

1.2  Реализация алгоритма на C++

//Функция обменивает местами элементы по адресам n1 и n2

inline void swap(int* n1, int* n2)

{

  *n1 ^= *n2;

  *n2 ^= *n1;

  *n1 ^= *n2;

}

//Функция сортирует массив A от позиции p до r включительно

void quickSort(int* A, int p, int r)

{

  //Сортируем, если текущий кусок массива содержит >1 элемента

  if (p < r) {

    //Сначала разбиваем массив

    int q = partition(A, p, r);

    //А потом рекурсивно вызываем сортировку для частей массива

    quickSort(A, p, q);

    quickSort(A, q + 1, r);

  }

}

//Функция разбивает массив A от позиции p до r включительно,

//возвращая границу разбиения q

int partition(int* A, int p, int r)

{

  //Выберем из массива число, с которым будем сравнивать

  int x = A[p];

  //Установим указатели за пределы массива

  int i = p - 1;

  int j = r + 1;

  for (;;) {

    //Продвинем оба указателя до элементов, которые надо обменять

    while (A[++i] < x);

    while (A[--j] > x);

    //Закончим работу, если указатели встретились

    //Иначе обменяем элементы и продолжим обработку

    if (i < j)

      swap(A + i, A + j);

    else

      return j;

  }

}

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

К сожалению, для алгоритма быстрой сортировки в общем случае нет асимптотически точной оценки времени выполнения. Математическое ожидание времени выполнения равно Θ(nlogn), но в худшем случае алгоритм работает за O(n²).

Алгоритм работает так нестабильно из-за того, что массив, как правило, разбивается не на две равные части, а на две части, равные лишь в идеале. На характер разбиения особенно сильно влияет выбор основы сравнения – числа x.

На практике может случиться такое, что массив будет биться на две части, размер одной из которых не пропорционален размеру массива n, а равен некой константе a >= 1. Тогда время работы алгоритма будет выражаться рекуррентным соотношением

T(n) = T(a) + T(n - a) + Θ(n),

поскольку разбиение отрабатывает за время Θ(n), где n = r – p + 1. Несложно показать, что в таком случае T(n) = Θ(n²).

Если же размер обеих частей массива пропорционален n, мы имеем соотношение

T(n) = T(n/b) + T((b - 1) n / b) + Θ(n),

где b >= 1 – константа. В этом случае T(n) = Θ(nlogn).

Доказать приведённые выше оценки алгоритма быстрой сортировки предлагается самостоятельно.

2  Сортировка с помощью кучи (heapsort)