GetInfo.Ru – Компьютерная библиотека
Последние поступления
Как выбрать систему управления базы данных
Базы данных03/09/14
Этапы загрузки UNIX (в схеме)
Unix27/03/12
Gatewall Antispam: тотальный контроль электронной почты
Спам21/04/11
Мастер-класс: создаем Интернет-магазин (Часть 1)
Обзоры ПО20/04/11
CorelDRAW Graphics Suite X5: Что нового?
Обзоры ПО20/07/10
Добавить статью
Самые читаемые материалы
Мягкие вычисления(44883)
Эволюционные вычисления(30968)
Сортировка и поиск: Рецептурный справочник(30175)
Алгоритмы архивации данных(24122)
Методика создания индексных файлов для осуществления полнотекстового поиска в сети Интернет(19180)
Всего статей: 793Всего авторов: 364Подразделов: 47Добавлено за сутки: 0
Статьи  СТАТЬИ Форум  ФОРУМ Рейтинг  РЕЙТИНГ Поиск  ПОИСК Контакты  КОНТАКТЫ
» Главная » Алгоритмы » Сортировка и поиск: Рецептурный справочник

Сортировка и поиск: Рецептурный справочник


Дубнер П.Н.
infoscope@writeme.com
http://attend.to/infoscope

Страницы: [ 1 ] [ 2 ]

Томас Ниман (Thomas Niemann)
Перевод с английского: П.Н.Дубнер (infoscope@writeme.com)
http://attend.to/infoscope

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

В первом разделе вводятся основные структуры данных и используемые обозначения. В следующем разделе вы найдете несколько алгоритмов сортировки. Затем следует описание методов реализации словарей - структур, которые позволяют эффективно искать, вставлять и удалять. В последнем разделе иллюстрируются алгоритмы сортировки данных и организации словарей в случае, когда файлы очень велики. Включены также тексты программ на языке Си (ANSI C).

Исходные тексты и многое другое вы можете найти на сайте автора

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

Оглавление

Введение

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

Массивы

На рис.1.1 показан массив из семи элементов с числовыми значениями. Чтобы найти в нем нужное нам число, мы можем использовать линейный поиск - его алгоритм приведен на рис. 1.2. Максимальное число сравнений при таком поиске - 7; оно достигается в случае, когда нужное нам значение находится в элементе A[6].

Рис. 1.1: Массив
Рис. 1.1: Массив
int function SequentialSearch (Array A, int Lb, int Ub, int Key);
  begin
  for i = Lb to Ub do
    if A(i) = Key then
      return i;
    return -1;
  end;

Рис. 1.2: Линейный поиск

Если известно, что данные отсортированы, можно применить двоичный поиск (рис. 1.3). Переменные Lb и Ub содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением Ub становится (M - 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы вдвое сужаем область поиска. Так, в нашем примере, после первой итерации область поиска - всего лишь три элемента, после второй остается всего лишь один элемент. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число.

Двоичный поиск - очень мощный метод. Если, например, длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй - до 255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10 сравнений.

Кроме поиска нам бывает нужно вставлять и удалять элементы. К сожалению, массив плохо приспособлен для выполнения этих операций. Например, чтобы вставить число 18 в массив на рис. 1.1, нам понадобится сдвинуть элементы A[3]:A[6] вниз - лишь после этого мы сможем записать число 18 в элемент A[3]. Аналогичная проблема возникает при удалении элементов. Для повышения эффективности операций вставки/удаления предложены связанные списки.

int function BinarySearch (Array A, int Lb, int Ub, int Key);
  begin
  do forever
    M = (Lb + Ub)/2;
    if (Key < A[M]) then
      Ub = M - 1;
    else if (Key > A[M]) then
      Lb = M + 1;
    else
      return M;
    if (Lb > Ub) then
    return -1;
  end;

Рис. 1.3: Двоичный поиск

Односвязные списки

На рис. 1.4 те же числа, что и раньше, хранятся в виде связанного списка; слово "связанный" часто опускают. Предполагая, что X и P являются указателями, число 18 можно вставить в такой список следующим образом:

X->Next = P->Next;
P->Next = X;

Списки позволяют очень эффективно вставлять и удалять. Поинтересуемся, однако, как найти место, куда мы будем вставлять новый элемент, т.е. каким образом присвоить нужное значение указателю P. Увы, для поиска нужной точки придется прогуляться по элементам списка. Таким образом, переход к спискам позволяет уменьшить время вставки/удаления элемента за счет увеличения времени поиска.

Рис. 1.4: Односвязный список
Рис. 1.4: Односвязный список

Оценки времени исполнения

Для оценки производительности алгоритмов можно использовать разные подходы. Самый бесхитростный - просто запустить каждый алгоритм на нескольких задачах и сравнить время исполнения. Другой способ - оценить время исполнения. Например, мы можем утверждать, что время поиска есть O(n) (читается так: о большое от n). Это означает, что при больших n время поиска не сильно больше, чем количество элементов. Когда используют обозначение O(), имеют в виду не точное время исполнения, а только его предел сверху, причем с точностью до постоянного множителя. Когда говорят, например, что алгоритму требуется время порядка O(n2), имеют в виду, что время исполнения задачи растет не быстрее, чем некоторая константа, помноженная на квадрат количества элементов. Чтобы почувствовать, что это такое, посмотрите таблицу 1.1, где приведены числа, иллюстрирующие скорость роста для нескольких разных функций. Скорость роста O(lg n) характеризует алгоритмы типа двоичного поиска. Логарифм по основанию 2, lg, увеличивается на 1, когда n удваивается. Вспомните - каждое новое сравнение позволяет нам искать в вдвое большем списке. Именно поэтому говорят, что время работы при двоичном поиске растет как lg n.

nlg nn lg nn1.25n2
10011
1646432256
25682,0481,02465,536
4,0961249,15232,76816,777,216
65,536161,048,5651,048,4764,294,967,296
1,048,4762020,969,52033,554,4321,099,301,922,576
16,775,61624402,614,7841,073,613,825281,421,292,179,456
Таблица 1.1: Скорость роста нескольких функций

Если считать, что числа в таблице 1.1 соответствуют микросекундам, то для задачи с 1048476 элементами алгоритму с временем работы O(lg n) потребуется 20 микросекунд, алгоритму с временем работы O(n1.25) - порядка 33 секунд, алгоритму с временем работы O(n2) - более 12 дней. В нижеследующем тексте для каждого алгоритма приведены соответствующие O-оценки. Более точные формулировки и доказательства можно найти в приводимых литературных ссылках.

Итак...

Как мы видели, если массив отсортирован, то искать его элементы нужно с помощью двоичного поиска. Однако, не забудем, кто-то должен отсортировать наш массив! В следующем разделе мы исследует разные способы сортировки массива. Оказывается, эта задача встречается достаточно часто и требует заметных вычислительных ресурсов, поэтому сортирующие алгоритмы исследованы вдоль и поперек, известны алгоритмы, эффективность которых достигла теоретического предела.

Связанные списки позволяют эффективно вставлять и удалять элементы, но поиск в них последователен и потому отнимает много времени. Имеются алгоритмы, позволяющие эффективно выполнять все три операции, мы обсудим из в разделе о словарях.

Сортировка

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

Сортировка вставками

Один из простейших способов отсортировать массив - сортировка вставками. В обычной жизни мы сталкиваемся с этим методом при игре в карты. Чтобы отсортировать имеющиеся у вас карты, вы вынимаете карту, сдвигаете оставшиеся карты, а затем вставляете карту на нужное место. Процесс повторяется до тех пор, пока хоть одна карта не на месте. Как среднее, так и худшее время для этого алгоритма - O(n2). Дальнейшую информацию можно получить в книжке Кнута[ 3 ].

Теория

На рис.2.1(a) мы вынимаем элемент 3. Затем элементы, расположенные выше, сдвигаем вниз - до тех пор, пока не найдем место, куда нужно вставить 3. Это процесс продолжается на рис.2.1(b) для числа 1. Наконец, на рис.2.1(c) мы завершаем сортировку, поместив 2 на нужное место.

Рис. 2-1: Сортировка вставками
Рис. 2-1: Сортировка вставками

Если длина нашего массива равна n, нам нужно пройтись по n - 1 элементам. Каждый раз нам может понадобиться сдвинуть n - 1 других элементов, получая алгоритм с временем работы O(n2).

Сортировка вставками относится к числу методов сортировки по месту. Другими словами, ей не требуется вспомогательная память, мы сортируем элементы массива, используя только память, занимаемую самим массивом. Кроме того, она является устойчивой - если среди сортируемых ключей имеются одинаковые, после сортировки они остаются в исходном порядке.

Реализация

Реализацию сортировки вставками на Си вы найдете в разделе 4.1. Оператор typedef T и оператор сравнения compGT следует изменить так, чтобы они соответствовали данным, хранимым в таблице.

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

Метод, предложенный Дональдом Л. Шеллом, является неустойчивой сортировкой по месту. Эффективность метода Шелла объясняется тем, что сдвигаемые элементы быстро попадают на нужные места. Среднее время для сортировки Шелла равняется O(n1.25), для худшего случая оценкой является O(n1.5). Дальнейшие свойства см. в книжке Кнута[ 3 ].

Теория

На рис. 2.2(a) был приведен пример сортировки вставками. Мы сначала вынимали 1, затем сдвигали 3 и 5 на одну позицию вниз, после чего вставляли 1. Таким образом, нам требовались два сдвига. В следующий раз нам требовалось еще два сдвига, чтобы вставить на нужное место 2. На весь процесс нам требовалось 2 + 2 + 1 = 5 сдвигов.

На рис. 2.2(b) иллюстрируется сортировка Шелла. Мы начинаем, производя сортировку вставками с шагом 2. Сначала мы рассматриваем числа 3 и 1: извлекаем 2, сдвигаем 3 на 1 позицию с шагом 2, вставляем 2. Затем повторяем то же для чисел 5 и 2: извлекаем 2, сдвигаем вниз 5, вставляем 2. И т.д. Закончив сортировку с шагом 2, производим ее с шагом 1, т.е. выполняем обычную сортировку вставками. Всего при этом нам понадобится 1 + 1 + 1 = 3 сдвига. Таким образом, использовав вначале шаг, больший 1, мы добились меньшего числа сдвигов.

Рис. 2-2: Сортировка Шелла
Рис. 2-2: Сортировка Шелла

Можно использовать самые разные схемы выбора шагов. Как правило, сначала мы сортируем массив с большим шагом, затем уменьшаем шаг и повторяем сортировку. В самом конце сортируем с шагом 1. Хотя этот метод легко объяснить, его формальный анализ довольно труден. В частности, теоретикам не удалось найти оптимальную схему выбора шагов. Кнут[1] провел множество экспериментов и нашел следующую формулу выбора шагов h для массива длины N:

в последовательности h1 = 1, hs+1 = 3hs + 1, ... взять ht, если ht+2 >= N

Вот несколько первых значений h:

h1 = 1
h2 = (3 x 1) + 1 = 4
h3 = (3 x 4) + 1 = 13
h4 = (3 x 13) + 1 = 40
h5 = (3 x 40) + 1 = 121

Чтобы отсортировать массив длиной 100, прежде всего найдем номер s, для которого hs >= 100. Согласно приведенным цифрам, s = 5. Нужное нам значение находится двумя строчками выше. Таким образом, последовательность шагов при сортировке будет такой: 13-4-1. Ну, конечно, нам не нужно хранить эту последовательность: очередное значение h находится из предыдущего по формуле:

hs-1 = [hs / 3]

Реализация

В реализации сортировки Шелла на Си следует изменить операторы typedef T и сравнения compGT так, чтобы они соответствовали данным, хранимым в массиве. Основная часть алгоритма - сортировка вставками с шагом h.

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

Хотя идея Шелла значительно улучшает сортировку вставками, резервы еще остаются. Один из наиболее известных алгоритмов сортировки - быстрая сортировка, предложенная Ч.Хоором. Метод и в самом деле очень быстр, недаром по-английски его так и величают QuickSort к неудовольствию всех спелл-чекеров ("...Шишков прости: не знаю, как перевести").

Этому методу требуется O(n lg n) в среднем и O(n2) в худшем случае. К счастью, если принять адекватные предосторожности, наихудший случай крайне маловероятен. Быстрый поиск не является устойчивым. Кроме того, ему требуется стек, т.е. он не является и методом сортировки на месте. Дальнейшую информацию можно получить в работе Кормена[ 2 ].

Теория

Алгоритм разбивает сортируемый массив на разделы, затем рекурсивно сортирует каждый раздел. В функции Partition (рис. 2.3) один из элементов массива выбирается в качестве центрального. Ключи, меньшие центрального следует расположить слева от него, те, которые больше, - справа.

int function Partition (Array A, int Lb, int Ub);
  begin
  select a pivot from A[Lb]...A[Ub];
  reorder A[Lb]...A[Ub] such that:
    all values to the left of the pivot are <= pivot
    all values to the right of the pivot are >= pivot
  return pivot position;
  end;

procedure QuickSort (Array A, int Lb, int Ub);
  begin
  if Lb < Ub then
    M = Partition (A, Lb, Ub);
    QuickSort (A, Lb, M - 1);
    QuickSort (A, M + 1, Ub);
  end;

Рис. 2-3: Быстрый поиск

На рис. 2.4(a) в качестве центрального выбран элемент 3. Индексы начинают изменяться с концов массива. Индекс i начинается слева и используется для выбора элементов, которые больше центрального, индекс j начинается справа и используется для выбора элементов, которые меньше центрального. Эти элементы меняются местами - см. рис. 2.4(b). Процедура QuickSort рекурсивно сортирует два подмассива, в результате получается массив, представленный на рис. 2.4(c).

Рис 2-4: Пример работы алгоритма Quicksort
Рис 2-4: Пример работы алгоритма Quicksort

В процессе сортировки может потребоваться передвинуть центральный элемент. Если нам повезет, выбранный элемент окажется медианой значений массива, т.е. разделит его пополам. Предположим на минутку, что это и в самом деле так. Поскольку на каждом шагу мы делим массив пополам, а функция Partition в конце концов просмотрит все n элементов, время работы алгоритма есть O(n lg n).

В качестве центрального функция Partition может попросту брать первый элемент (A[Lb]). Все остальные элементы массива мы сравниваем с центральным и передвигаем либо влево от него, либо вправо. Есть, однако, один случай, который безжалостно разрушает эту прекрасную простоту. Предположим, что наш массив с самого начала отсортирован. Функция Partition всегда будет получать в качестве центрального минимальный элемент и потому разделит массив наихудшим способом: в левом разделе окажется один элемент, соответственно, в правом останется Ub - Lb элементов. Таким образом, каждый рекурсивный вызов процедуры quicksort всего лишь уменьшит длину сортируемого массива на 1. В результате для выполнения сортировки понадобится n рекурсивных вызовов, что приводит к времени работы алгоритма порядка O(n2). Один из способов побороть эту проблему - случайно выбирать центральный элемент. Это сделает наихудший случай чрезвычайно маловероятным.

Реализация

В приведенной реализации алгоритма на Си операторы typedef T и compGT следует изменить так, чтобы они соответствовали данным, хранимым в массиве. По сравнению с основным алгоритмом имеются некоторые улучшения:

  • В качестве центрального в функции partition выбирается элемент, расположенный в середине. Такой выбор улучшает оценку среднего времени работы, если массив упорядочен лишь частично. Наихудшая для этой реализации ситуация возникает в случае, когда каждый раз при работе partition в качестве центрального выбирается максимальный или минимальный элемент.

  • Для коротких массивов вызывается insertSort. Из-за рекурсии и других "накладных расходов" быстрый поиск оказывается не столь уж быстрым для коротких массивов. Поэтому, если в массиве меньше 12 элементов, вызывается сортировка вставками. Пороговое значение не критично - оно сильно зависит от качества генерируемого кода.

  • Если последний оператор функции является вызовом этой функции, говорят о хвостовой рекурсии. Ее имеет смысл заменять на итерации - в этом случае лучше используется стек. Это сделано при втором вызове QuickSort на рис. 2.3.

  • После разбиения сначала сортируется меньший раздел. Это также приводит к лучшему использованию стека, поскольку короткие разделы сортируются быстрее и им нужен более короткий стек.

Функция qsort из стандартной библиотеки Си основана на алгоритме quicksort. Для этой реализации рекурсия была заменена на итерации. В таблице 2.1 приводится время и размер стека, затрачиваемые до и после описанных улучшений.

кол-во элементоввремя (чs)размер стека
допоследопосле
161035154028
2561,630911912112
4,09634,18320,0161,908168
65,536658,003460,7372,436252

Таблица 2.1: Влияние улучшений на скорость работы и размер стека

Сравнение методов

В данном разделе мы сравним описанные алгоритмы сортировки: вставками, Шелла и быструю сортировку. Есть несколько факторов, влияющих на выбор алгоритма в каждой конкретной ситуации:

  • Устойчивость. Напомним, что устойчивая сортировка не меняет взаимного расположения элементов с равными ключами. Сортировка вставками - единственный из рассмотренных алгоритмов, обладающих этим свойством.

  • Память. Сортировке на месте не требуется дополнительная память. Сортировка вставками и Шелла удовлетворяют этому условию. Быстрой сортировке требуется стек для организации рекурсии. Однако, требуемое этому алгоритму место можно сильно уменьшить, повозившись с алгоритмом.

  • Время. Время, нужное для сортировки наших данных, легко становится астрономическим (см. таблицу 1.1). Таблица 2.2 позволяет сравнить временные затраты каждого из алгоритмов по количеству исполняемых операторов. Время, затраченное каждым из алгоритмов на сортировку случайного набора данных, представлено в таблице 2.3.

  • Простота. Количество операторов, выполняемых каждым алгоритмом, приведено в таблице 2.2. Более простые алгоритмы вызывают меньше ошибок при программировании.

методкол-во операторовср. времявремя для наихудшего случая
сортировка вставками9O(n2)O(n2)
сортировка Шелла17O(n1.25)O(n1.5)
быстрая сортировка21O(n lg n)O(n2)
Таблица 2.2:Сравнение методов сортировки

кол-во элементоввставкиШеллquicksort
1639 чs45 чs51 чs
2564,969 чs1,230 чs911 чs
4,0961.315 sec.033 sec.020 sec
65,536416.437 sec1.254 sec.461 sec
Таблица 2.3: Время сортировки

 
12.04.2004
Версия для печати Версия для печати Запомнить ссылку Запомнить ссылку
Ваша оценка:  1   2   3   4   5     

 О проектеПерепечаткаАвторамПартнерыО нас пишут
Наверх
©2003—2007. GETINFO.RU. ВСЕ ПРАВА ЗАЩИЩЕНЫ.