Сортировка слиянием. Поразрядная сортировка

 

Слияние является процессом объединения двух и более отсортированных файлов в некоторый третий отсортированный файл [3]. Мы можем использовать такой подход к сортировке файла следующим образом. Разделим файл на n подфайлов размером 1 и будем объединять соседние (необъединенные) пары файлов. Тогда будем иметь примерно n /2 файлов размером 2. Повторяем этот процесс до тех пор, пока не останется только один файл размером n. Рассмотрим сказанное на примере.

 

Первоначальный файл (25) (57) (48) (37) (12) (92) (86) (33)

 

Просмотр 1        (25, 57) (37, 48) (12, 92) (33, 86)

 

Просмотр 2             (25, 37, 48, 57)                 (12, 33, 86, 92)

 

Просмотр 3                          (12, 25, 33, 37, 48, 57, 86, 92)

 

Поразрядная сортировка

 

Этот метод основан на свойстве значений действительных чисел в позиционном представлении сортируемых чисел. Для простоты предполагаем, что все числа имеют одинаковое число цифр, что при необходимости выполняется добавлением незначащих нулей. Предположим, что мы выполняем следующие действия над файлом для каждой цифры, начиная с самой младшей цифры и кончая самой старшей цифрой. Берем каждое число в том порядке, в котором оно появляется в файле, и помещаем его в одну из 10 очередей в зависимости от значения цифры, которая в данный момент обрабатывается. Затем восстанавливаем каждую очередь к виду первоначального файла, начиная с очереди чисел с цифрой 0 и кончая очередью чисел с цифрой 9. Когда эти действия будут выполнены для каждой цифры, начиная с самой младшей и кончая самой старшей, данный файл будет отсортирован. Рассмотрим изложенную процедуру на примере.

 

Первоначальный файл 25 57 48 37 12 92 86 33

 

Очереди, организованные по МЗЦ (младшей значащей цифре)

 

Очереди	Начало	Конец
0	–
1	–
2	12	92
3	33
4	–
5	25
6	86
7	57	37
8	48
9	–

 

После первого просмотра: 12 92 33 25 86 57 37 48

 

Очереди, организованные по СЗЦ (старшей значащей цифре)

 

Очереди	Начало	Конец
0	–
1	12
2	25
3	33	37
4	48
5	57
6	–
7	–
8	86
9	92

    

Отсортированный файл 12 25 33 37 48 57 86 92

 

Временные затраты на метод поразрядной сортировки зависят от числа цифр (m) и числа элементов в файле (n). Для того, чтобы сэкономить значительный объем работы при обработке очередей, рекомендуется использовать связанное распределение данных на основе указателей.

 

Поиск данных

Введение в поиск данных

 

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

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

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

Алгоритмом поиска является такой алгоритм, который, воспринимая некоторый аргумент a, пытается локализовать некоторую запись, ключ которой равен а. Данный алгоритм может возвратить всю данную запись или чаще всего может возвратить некоторый указатель на эту запись. Успешный поиск называется извлечением. В противном случае алгоритм может возвратить некоторую специальную «пустую запис ь» или некоторый пустой указатель. Однако чаще такое условие приводит к появлению некоторой ошибки или установке во флаге некоторого конкретного значения, которое указывает, что данная запись отсутствует. Если поиск закончился неудачно, то часто бывает желательно добавить некоторую новую запись с этим аргументом в качестве ключа. Алгоритм, который выполняет эту функцию, называется алгоритмом поиска и вставки [3].

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

 

Последовательный поиск

 

Простейшей формой поиска является последовательный поиск. Этот поиск применяется к таблице, которая организована или как массив, или как связанный список [3].

Предположим, что k есть некоторый массив из n ключей, а r — некоторый массив записей, такой, что k (i) является ключом для r (i). Предположим также, что key является некоторым аргументом поиска. Мы хотим установить в переменную search наименьшее целое число i, такое что k (i) = key, если такое i существует, и 0 в противном случае. Алгоритм выполнения этих действий следующий:

 

search =0;

for (i =1; i <= n; i + +)

{

  if(key = = k[i]) search = i;

}

 

Этот алгоритм может быть просто модифицирован для того, чтобы добавлять некоторую запись rec с ключом key в таблицу, если ключ key не находится в таблице. Следующие операторы добавляются в приведенные выше:

 

if (search = = 0)

{

n ++;    // увеличиваем размер таблицы

k [ n ] = key // вставляем новый ключ и запись

r[n]= rec;

search = n;

}

 

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

 

// key — искомый ключ записи

…

flag=false;

qq=q;    // q — указатель на начало списка

i=0;      // n — число элементов в списке

while((flag==false) && (i<=n))

{

i++;

if (qq->key==key)

{

q1=q; // q1 — указатель на искомый элемент

cout<<”Запись найдена\n”;

flag=true;

}

else

{

    q2=qq; // q2 – указатель, ссылающийся.ся на qq

    qq=qq->next; 

}

 

// вставка элемента zapis с заданным ключом key в начало списка

 

if (flag==false)

{

  item *kon=new kon(next,key,nam); // kon - указатель на ячейку

  kon->next=q;

  kon->key=key;

  kon->nam=zapis;

  q=kon;

}

 

// удаление элемента с ключом key из списка

else

  {

         q2.next=q1.next;

        delete q1;

}

}

…

 

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