Сортировка

Лекция 3. Сортировка

Сортировка в программировании – расположение объектов в порядке возрастания или убывания, то есть упорядочение. В общелексическом значении слово «сортировка» имеет другое значение: разделение объектов по виду или сорту.

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

Формальная постановка задачи.

Дана последовательность элементов R1R2R3…RN. Каждому элементу Ri соотвествует некоторый ключ Ki.

Определим отношение порядка «<» (отношение линейного, или совершенного, упорядочения): для любых трех значений a, b и c выполняются следующие условия:

а) справедливо одно и только одно из соотношений a<b, a=b, b<a (закон трихотомии);

б) если a<b и b<c, то a<c (закон транзитивности).

Задача перестановки: найти такую перестановку записей p1p2p3…pN после которой ключи расположились бы в порядке неубывания: Kp1 <= Kp2 <= Kp3 <= … <= KpN.

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

pi < pj для любых Kpi = Kpj и i < j.

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

Методы сортировки подразделяют на два класса: внутренние и внешние.

Классы алгоритмов сортировки:

а) сортоировка методом вставок – элементы просматриваются по одному, и каждый новый элемент вставляется в подходящее место среди ранее упорядоченных;

б) обменная сортировка – если два элемента расположены не по порядку, то они меняются местами;

в) сортировка посредством выбора – сначала выделяется наименьший (или наибольший) элемент и каким-то образом отделяется от остальных, затем выбирается наименьший (наибольший) из оставшихся и т.д.;

г) сортировка путем подсчета – каждый элемент сравнивается со всеми остальными, окончательное положение элемента определяется после подсчета числа меньших ключей;

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

Физическая сорировка: записи перемещаются в памяти.

Сортировка таблицы адресных ссылок: сортировку описывает таблица адресныхссылок на записи; записи в памяти не перемещаются.

Сортировка списка: изменяются связи, записи не перемещаются.

Сортировка посредство подсчета.

Основная идея алгоритма: j-ый ключ в упорядоченной последовательности превышает ровно j-1 других ключей.

Способ подсчета числа ключей, меньших заданного очевиден:

((сравнить Kj с Ki) при 1 <= j <= N) при 1 <= i <= N.

И, избегая избыточных сравнений:

((сравнить Kj с Ki) при 1 <= j < i) при 1 <= i <= N.

Программа на С++ (обратите внимания, что индексация с 0 до N-1, а не как выше в формулах!)

(Алгоритм А - сортировка подсчетом сравнений)

int N; // число элементов сортируемого массива.

int* K;               // ключи.

int* sort (int* K, int N)

              {

int* count = new [N];

for (int i = 0; i < N; i++)

              {

              count[i] = 0;

              }

for (int i = N-1; i >= 0; i--)

              {

              for (int j = i-1; j >= 0; j--)

                            {

                            if (K[i] < K[j])

                                          count[j]++;

                            else

                                          count[i]++;                                         

                            }

              }

return count;

}

              В результате работы программы записи не перемещаются (массив K не изменяется), но формируется адресная таблица count. Теперь count[i] – позиция элемента i в упорядоченном массиве. Этот массив при необходимости можно легко получить:

              int* sortedK = new int[N];

              for (int i = 0; i < N; i++)

                            sortedK[count[i]] = K[i];

Метод пузырька.

              Основная идея: сравнивать попарно 1 со 2-ым, 2-ой с 3-им и т.д. меняя элементы местами, если они расположены в неверном порядке; в результате одного прохода происходит «всплывание» наибольшего элемента. Операция повторяется пока массив не будет полностью отсортирован.

Сортировка посредством простого выбора.             

              void sort (int* K, int N)

                            {

                            for (int i = N-1; i > 0; i--)

                                          {

                                          int imax = 0;

                                          for (int j = 0; j <= i; j++)

                                                        {

                                                        if (K[j] > K[imax])

                                                                      imax = j;

                                                        }

                                          int k = K[i];

                                          K[i] = K[imax];

                                          K[imax] = k;

                                          }

                            }

Лемма. В любом алгоритме нахождения максимума среди n элементов, основанном на сравнении пар элементов, необходимо выполнить, по крайней мере, n-1 сравнений.

Доказательство. Если выполнено менее n-1 сравнений, то найдутся хотя бы два элемента, для которых не было обнаружено ни одного элемента, превосходящего их по величине. Следовательно, мы так и не узнаем, какой из этих двух элементов больше, а значит, не сможем определить максимум.

(ДОПОЛНИТЕЛЬНО*)

Сортировка методом простых вставок.

              Основная идея: при рассмотрении записи Rj записи R1,… Rj-1 уже упорядочены и мы выбираем место среди них для записи Rj. Алгоритм также называеют «просеиванием» или «погружением».

              (Алгоритм Б)             

              void sortB (int* K, int N)

                            {

                            for (int i = 1; i < N; i++)

                                          {

                                          int v = K[i];

                                          for (int j = i-1; j>=0; j--)

                                                        {

if (K[j] < v)

                                                                      {

                                                                      K[j+1] = v;

                                                                      break;

                                                                      }

                                                        else

                                                                      {

                                                                      K[j+1] = K[j];

                                                                      }

                                                        }

                                          }

                            }             

Сортировка Шелла.

              Основная идея: сначала сортируются записи в группах, образуемых каждой k1-ой записью, где k – шаг; далее сортируются записи в группах, образуемых каждой k2-ой записью. И т.д., где km = 1.  На каждом этапе сортируются либо сравнительно короткие либо уже хорошо упорядоченные массивы, поэтому на каждом этапе можно пользоваться методом простых вставок.

              (Алгоритм В)

              int* K;

              int N;

              int* h;              // массив шагов размера m.

              int m;

              void Shellsort (int* K, int N, int* h, int m)

                            {

                            for (int k = 0; k < m; k++)

                                          {

                                          for (int i = h[k]; i < N; i+= h[k])

                                                        {

                                                        int v = K[i];

                                                        for (int j = i-h[k]; j>=0; j -= h[k])

                                                                      {

if (K[j] < v)

                                                                                    {

                                                                                    K[j+h[k]] = v;

                                                                                    break;

                                                                                    }

                                                                      else

                                                                                    {

                                                                                    K[j+h[k]] = K[j];

                                                                      }

                                                        }

                                          }             

                            }             

Литература

1.       Кнут, Д.Э. Искусство программирования, том 3. Сортировка и поиск, 2-е изд.: Пер. с англ. – М.: Издательский дом «Вильямс», 2001.

Задачи

[1] Докажите, что из законов трихотомии и транзитивности вытекает единственность перестановки p1p2…pN, если сортировка устойчива.

[2] Обеспечивает ли алгоритм А устойчивую сортировку?

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

[4] Попытайтесь подсчитать минимальное и максимальное число сравнений, необходимых для каждого рассмотренного алгоритма.

[5] Сделайте программу, которая бы подсчитывала во время работы число выполненных сравнений, число выполненных операций присваивания.

[6] Напишите программу, которая бы запускала программу из упражнения 5 много раз (сотни тысяч) для случайно формируемых больших (сотни тысяч элементов) массивов и определяля минимальное, среднее и максимальное значения, вычисляемых программой из управжения 5, величин.

[7] Напишите программу, выполняющую сортировку строк в алфавитном порядке с помощью одного из рассмотренных алгоритмов.

[8] Напишите программу, выполняющую сортировку элементов связного списка с помощью всех рассмотренных алгоритмов. Перемещать элементы списка не нужно: достаточно изменять связи.

2