Во многих приложениях сортировки ключи, используемые для упорядочения записей в файлах, могут быть весьма сложными. Например, насколько сложны ключи, используемые в телефонной книге или в библиотечном каталоге. Сейчас мы рассмотрим другую абстракцию для ключей сортировки. Например, часто нет необходимости в полной обработке ключей на каждом этапе: при поиске в телефонном справочнике, чтобы найти страницу с номером какого-либо абонента, достаточно проверить лишь несколько первых букв его фамилии. Чтобы добиться такой же эффективности алгоритмов сортировки, мы перейдем от абстрактной операции сравнения ключей к абстракции, в которой ключи разбиваются на последовательность частей фиксированного размера — байтов. Методы сортировки, основанные на обработке ключей по частям, называются поразрядными методами сортировки (radix sort). Эти методы не просто сравнивают ключи, а обрабатывают и сравнивают части ключей.
Алгоритмы поразрядной сортировки интерпретируют ключи как числа, представленные в системе счисления с основанием R, при различных значениях R (основание системы счисления — radix), и работают с отдельными цифрами этих чисел. Алгоритмы поразрядной сортировки основаны на абстрактной операции " извлечь i-ю цифру ключа ".
Существуют два принципиально различных базовых подхода к поразрядной сортировке. Первый класс методов составляют алгоритмы, анализирующие цифры в ключах в направлении слева направо, при этом первыми обрабатываются наиболее значащие цифры. Все эти методы вместе называются MSD-сортировками (most significant digit radix sort — поразрядная сортировка сначала по старшей цифре). MSD-сортировки привлекательны тем, что они анализируют минимальный объем информации, необходимый для выполнения сортировки.
Во втором классе методов поразрядной сортировки используется другой принцип: они анализируют цифры ключей в направлении справа налево, работая сначала с наименее значащими цифрами. Все эти методы вместе называются LSD-сортировками (least significant digit radix sort — поразрядная сортировка сначала по младшей цифре). LSD-сортировка в какой-то степени противоречит интуиции, поскольку часть процессорного времени затрачивается на обработку цифр, которые не могут повлиять на результат, однако данная проблема легко решается, и этот почтенный метод годится для работы во многих приложениях сортировки.
#include <algorithm>
#include <iostream>
#include <iterator>
// Radix sort comparator for 32-bit two's complement integers
class radix_test
{
const int bit; // bit position [0..31] to examine
public:
radix_test(int offset): bit(offset) {} // constructor
bool operator()(int value) const // function call operator
{
if (bit == 31) // sign bit
return value < 0; // negative int to left partition
else
return!(value & (1 << bit)); // 0 bit to left partition
}
};
// Least significant digit radix sort
void lsd_radix_sort(int *first, int *last)
{
for (int lsb = 0; lsb < 32; ++lsb) // least-significant-bit
{
std::stable_partition(first, last, radix_test(lsb));
}
}
// Most significant digit radix sort (recursive)
void msd_radix_sort(int *first, int *last, int msb = 31)
{
if (first!= last && msb >= 0)
{
int *mid = std::partition(first, last, radix_test(msb));
msb--; // decrement most-significant-bit
msd_radix_sort(first, mid, msb); // sort left partition
msd_radix_sort(mid, last, msb); // sort right partition
}
}
// test radix_sort
int main()
{
int data[] = { 170, 45, 75, -90, -802, 24, 2, 66 };
lsd_radix_sort(data, data + 8);
// msd_radix_sort(data, data + 8);
std::copy(data, data + 8, std::ostream_iterator<int>(std::cout, " "));
return 0;
}
B. Внешние сортировки
Основным понятием при использовании внешней сортировки является понятие серии. Серия (упорядоченный отрезок) – это последовательность элементов, которая упорядочена по ключу. Количество элементов в серии называется длиной серии. Серия, состоящая из одного элемента, упорядочена всегда. Последняя серия может иметь длину меньшую, чем остальные серии файлов. Максимальное количество серий в файле N (все элементы не упорядочены). Минимальное количество серий одна (все элементы упорядочены). В основе большинства методов внешних сортировок лежит процедура слияния и процедура распределения. Слияние – это процесс объединения двух (или более) упорядоченных серий в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. Распределение – это процесс разделения упорядоченных серий на два и несколько вспомогательных файла. Фаза – это действия по однократной обработке всей последовательности элементов. Двухфазная сортировка – это сортировка, в которой отдельно реализуется две фазы: распределение и слияние. Однофазная сортировка – это сортировка, в которой объединены фазы распределения и слияния в одну. Двухпутевым слиянием называется сортировка, в которой данные распределяются на два вспомогательных файла. Многопутевым слиянием называется сортировка, в которой данные распределяются на N (N > 2) вспомогательных файлов.
I. Прямым слиянием
Одна из сортировок на основе слияния называется простым слиянием.
Алгоритм сортировки простым слияния является простейшим алгоритмом внешней сортировки, основанный на процедуре слияния серией.
В данном алгоритме длина серий фиксируется на каждом шаге. В исходном файле все серии имеют длину 1, после первого шага она равна 2, после второго – 4, после третьего – 8, после k -го шага – 2k.
Алгоритм сортировки простым слиянием
Шаг 1. Исходный файл f разбивается на два вспомогательных файла f1 и f2.
Шаг 2. Вспомогательные файлы f1 и f2 сливаются в файл f, при этом одиночные элементы образуют упорядоченные пары.
Шаг 3. Полученный файл f вновь обрабатывается, как указано в шагах 1 и 2. При этом упорядоченные пары переходят в упорядоченные четверки.
Шаг 4. Повторяя шаги, сливаем четверки в восьмерки и т.д., каждый раз удваивая длину слитых последовательностей до тех пор, пока не будет упорядочен целиком весь файл (рис. 43.1).
После выполнения i проходов получаем два файла, состоящих из серий длины 2i. Окончание процесса происходит при выполнении условия 2i>=n. Следовательно, процесс сортировки простым слиянием требует порядка O(log n) проходов по данным.
Признаками конца сортировки простым слиянием являются следующие условия:
· длина серии не меньше количества элементов в файле (определяется после фазы слияния);
· количество серий равно 1 (определяется на фазе слияния).
· при однофазной сортировке второй по счету вспомогательный файл после распределения серий остался пустым.
Реализация сортировки двухпутевым двухфазным простым слиянием
//Описание функции сортировки простым слиянием
void Simple_Merging_Sort (char *name){
int a1, a2, k, i, j, kol, tmp;
FILE *f, *f1, *f2;
kol = 0;
if ((f = fopen(name,"r")) == NULL)
printf("\nИсходный файл не может быть прочитан...");
else {
while (!feof(f)) {
fscanf(f,"%d",&a1);
kol++;
}
fclose(f);
}
k = 1;
while (k < kol){
f = fopen(name,"r");
f1 = fopen("smsort_1","w");
f2 = fopen("smsort_2","w");
if (!feof(f)) fscanf(f,"%d",&a1);
while (!feof(f)){
for (i = 0; i < k &&!feof(f); i++){
fprintf(f1,"%d ",a1);
fscanf(f,"%d",&a1);
}
for (j = 0; j < k &&!feof(f); j++){
fprintf(f2,"%d ",a1);
fscanf(f,"%d",&a1);
}
}
fclose(f2);
fclose(f1);
fclose(f);
f = fopen(name,"w");
f1 = fopen("smsort_1","r");
f2 = fopen("smsort_2","r");
if (!feof(f1)) fscanf(f1,"%d",&a1);
if (!feof(f2)) fscanf(f2,"%d",&a2);
while (!feof(f1) &&!feof(f2)){
i = 0;
j = 0;
while (i < k && j < k &&!feof(f1) &&!feof(f2)) {
if (a1 < a2) {
fprintf(f,"%d ",a1);
fscanf(f1,"%d",&a1);
i++;
}
else {
fprintf(f,"%d ",a2);
fscanf(f2,"%d",&a2);
j++;
}
}
while (i < k &&!feof(f1)) {
fprintf(f,"%d ",a1);
fscanf(f1,"%d",&a1);
i++;
}
while (j < k &&!feof(f2)) {
fprintf(f,"%d ",a2);
fscanf(f2,"%d",&a2);
j++;
}
}
while (!feof(f1)) {
fprintf(f,"%d ",a1);
fscanf(f1,"%d",&a1);
}
while (!feof(f2)) {
fprintf(f,"%d ",a2);
fscanf(f2,"%d",&a2);
}
fclose(f2);
fclose(f1);
fclose(f);
k *= 2;
}
remove("smsort_1");
remove("smsort_2");
}