FAQ по сортировкам — HackZona.Ru

FAQ по сортировкам

FAQ по сортировкам

Тип статьи:
Со старой ХакЗоны.
Источник:
1. Ликбез для понимания важной информации: Что означает символ O(n)? Почему не пишется основание логарифма: O (log n)?

A: Kantor Ilia — Tomas Niemann
Оценки времени исполнения. Cимвол O().
Для оценки производительности алгоритмов можно использовать разные подходы. Самый бесхитростный — просто запустить каждый алгоритм на нескольких задачах и сравнить время исполнения. Другой способ — оценить время исполнения. Hапример, мы можем утверждать, что время поиска есть O(n) (читается так: о большое от n).

Когда используют обозначение O(), имеют в виду не точное время исполнения, а только его предел сверху, причем с точностью до постоянного множителя. Когда говорят, например, что алгоритму требуется время порядка O(n^2), имеют в виду, что время исполнения задачи растет не быстрее, чем квадрат количества элементов. Чтобы почувствовать, что это такое, посмотрите на таблицу, где приведены числа, иллюстрирующие скорость роста для нескольких разных функций.

n log n n*log n n^2
1 0 0 1
16 4 64 256
256 8 2,048 65,536
4,096 12 49,152 16,777,216
65,536 16 1,048,565 4,294,967,296
1,048,476 20 20,969,520 1,099,301,922,576
16,775,616 24 402,614,784 281,421,292,179,456

Если считать, что числа в таблице соответствуют микросекундам, то для задачи с 1048476 элементами алгоритму с временем работы O(log n) потребуется 20 микросекунд, а алгоритму с временем работы O(n^2) — более 12 дней.

Если оба алгоритма, например, O ( n*log n ), то это отнюдь не значит, что они одинакого эффективны.

Символ О не учитывает константу, то есть первый может быть, скажем в 1000 раз эффективнее. Это значит лишь то, что их время возрастает приблизительно как функция n*log n.

За функцию берется количество операций, возрастающее быстрее всего.

То есть если в программе одна функция выполняется O(n) раз — например, умножение, а сложение — O(n^2) раз, то общая сложность — O(n^2), так как в конце концов при увеличении n более быстрые ( в определенное, константное число раз ) сложения станут выполнятся настолько часто, что будут тормозить куда больше, нежели медленные, но редкие умножения.

Основание логарифма не пишется.

Причина этого весьма проста. Пусть у нас есть O(log2_n). Hо log2_n = log3_n / log3_2, а log3_2, как и любую константу, асимптотика — символ О() не учитывает. Таким образом, O(log2_n) = O( log3_n). К любому основанию мы можем перейти аналогично, а, значит, и писать его не имеет смысла.

2. Какие на сегодняшний день самые эффективные методы сортировки?
A: Kantor Ilia
быстрая сортировка, распределяющая сортировка и быстрая сортировка с составными ключами, которая слишком сложна для ФАКа.

Для прикладных задач, использующих элементы сортировки также очень полезна пирамидальная сортировка.

3. Сортировка простыми вставками.
A: Kantor Ilia — Nicolas Virt — Tomas Niemann ;-)) Алгоритм
Все элементы условно разделяются на готовую последовательность a1… ai-1 и входную ai… an. Hа каждом шаге, начиная с i=2 и увеличивая i на 1, берем i-й элемент входной последовательности и вставляем его на нужное место в готовую.

Пример:

Hачальные ключи 44 55 12 42 94 18 06 67
i = 2 44 55 12 42 94 18 06 67
i = 3 12 44 55 42 94 18 06 67
i = 4 12 42 44 55 94 18 06 67
i = 5 12 42 44 55 94 18 06 67
i = 6 12 18 42 44 55 94 06 67
i = 7 06 12 18 42 44 55 94 67
i = 8 06 12 18 42 44 55 67 94

При поиске подходящего места удобно 'просеивать' x, сравнивая его с очередным элементом ai и либо вставляя его, либо пересылая ai направо и продвигаясь налево.

Просеивание может кончиться при двух условиях:

1. Hайден ai с ключом, меньшим x.

2. Достигнут конец готовой последовательности.

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

Анализ
Число сравнений
минимальное: n — 1
среднее: ( n^2 + n — 2 ) / 4
максимальное: ( n^2 + n ) * / 2 — 1
Количество пересылок
минимальное: 2 * ( n — 1 )

среднее: ( n^2 + 9 * n — 10 ) / 4

максимальное: ( n^2 + 3 * n — 4 ) / 2

Пример на Си — Tomas Niemann.
--------------------------------------------------------------------
typedef int item; /* Тип сортируемых элементов */
typedef int tblIndex; /* Тип ключей, по которым сортируем */

#define compGT(a,b) (a > b) /* Функция сравнения */

void insertSort(T *a, tblIndex lb, tblIndex ub) {
item t;
tblIndex i, j;

/***********************
* сортируем a[lb..ub] *
***********************/
for (i = lb + 1; i = lb && compGT(a[j], t); j--)
a[j+1] = a[j];

/* вставка */
a[j+1] = t;
}
}

4. Описание и исходник QuickSort (быстрая сортировка).
Основной алгоритм
Выберем случайным образом какой-то элемент х и просмотрим массив, двигаясь слева направо, пока не найдем аi больший x, а затем справа налево, пока не найдем аi меньший х. Поменяем их местами и продолжим процесс просмотра с обменом, пока просмотры не встретятся где-то в середине массива.

В результате массив разделится на две части: левую — с ключами, меньшими х и правую — с ключами, большими х.

Этот шаг называется разделением. Х — центром.

К получившимся частям рекурсивно применяем ту же процедуру.

В результате получается очень эффективная сортировка

Пример рекурсивной QuickSort
------------------------------------
typedef int item; /* Тип сортируемых элементов */
typedef int tblIndex; /* Тип ключей, по которым сортируем */

#define CompGT(a,b) (a > b)

tblIndex partition(T *a, tblIndex lb, tblIndex ub) {
item t, pivot;
tblIndex i, j, p;

/**********************************
* разделение массива a[lb..ub] *
**********************************/

/* Выбираем центр — pivot */
p = lb + ((ub — lb)>>1);
pivot = a[p];
a[p] = a[lb];

/* сортируем lb+1..ub относительно центра */
i = lb+1;
j = ub;
while (1) {
while (i = i && compGT(a[j], pivot)) j--;
if (i >= j) break;
t = a[i];
a[i] = a[j];
a[j] = t;
j--; i++;
}

/* центр в a[j] */
a[lb] = a[j];
a[j] = pivot;

return j;
}

void quickSort(T *a, tblIndex lb, tblIndex ub) {
tblIndex m;

/**************************
* сортируем a[lb..ub] *
**************************/

while (lb = 0; sp--) {
char *lb, *ub, *m;
char *P, *i, *j;

lb = lbStack[sp];
ub = ubStack[sp];

while (lb > 1;
P = lb + offset — offset % size;
exchange (lb, P, size);

/* разделение в два сегмента */
i = lb + size;
j = ub;
while (1) {
while (i 0) i += size;
while (j >= i && compar(j, lb) > 0) j -= size;
if (i >= j) break;
exchange (i, j, size);
j -= size;
i += size;
}

/* центр в A[j] */
exchange (lb, j, size);
m = j;

/* Меньший сегмент продолжаем обрабатывать, больший — в стек */
if (m — lb lb) {
lbStack[sp] = lb;
ubStack[sp++] = m — size;
}
lb = m + size;
}
}
}
}

5. Описание и исходник HeapSort (пирамидальная сортировка).
A: Kantor Ilia — Nicolas Virt
Hазовем пирамидой последовательность элементов

hl, hl+1,…, hr
такую, что
hi = a[j].key then goto 13;
a[i] := a[j]; i := j; j := 2*i
end;
13: a[i] := x
end;

begin l := (n div 2) + 1; r := n;
while l > 1 do
begin l := l — 1; sift
end;

while r > 1 do
begin x := a[l]; a[l] := a[r]; a[r] := x;
r := r — 1; sift
end
end { heapsort }

6. Требования QuickSort и HeapSort. InsertSort… Что лучше?
A: Kantor Ilia
Простые вставки.

Общее быстродействие — O( n^2 ), но ввиду простоты метода, является наибыстрейшим для малых ( 12-20 элементов ) массивов.

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

Сортировка не требует дополнительной памяти.

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

Общее быстродействие — O( nlogn ). Случай n^2 теоретически возможен, но крайне [ 1 / (n^logn) ] маловероятен.

В общем и целом — наиболее быстрая сортировка сравнениями для разупорядоченных массивов с >50 элементами.

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

Итерационный вариант требует logn памяти, рекурсивный — O(n).

Пирамидальная сортировка.

В 1.5 раза медленнее быстрой. Hаихудшего случая нет — всегда O(nlogn). Практически, ее элементы часто применяются в смежных задачах.

Поведение неестественно.

Основное достоинство — сортировка не требует дополнительной памяти.

7. Какая самая быстрая сортировка?
A: Kantor Ilia

Давайте разберемся раз и навсегда. Есть два типа сортировок:

Распределяющая и ее вариации | Сортировка сравнениями
|
Основана на том, что число возможных | Пользуется лишь возможностью
значений ключа конечно. | прямого сравнения ключей и
| их упорядоченностью.
| Quicksort, Heapsort...

Для сортировок сравнениями давно доказана теорема о максимальном быстродействии: O(nlog n).

Для сортировок распределением это — O(n). Быстрее сортировать нельзя.

Итак, наибыстрейшие сортировки -
Quicksort — быстрая,
Radix sort — распределяющая
и их молодой гибрид:
Multiway Quicksort /MQS / — быстрая с составными ключами.
апример, для строк.

Вообще, нужно смотреть по данным и имеющимся в наличии ресурсам, но в типичных случаях наибыстрейшими решениями станут .

8. Что такое Байтовая, Цифровая, Радиксная или Распределяющая сортировка?
A: Kantor Ilia
К сожалению, или к счастью, единица информации в современной технике способна применять лишь 2 значения: 1 и 0.

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

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

Разрядность данных ( количество возможных значений элементов k) — m.

Если мы сортируем слова, то элемент сортировки — буква. m = 33. Если в самом длинном слове 10 букв, k = 10.

Обычно мы будем сортировать данные по ключам из k байт, m=255.


--------------------------------------------------------------------------------

Пусть у нас есть массив source из n элементов по одному байту в каждом.

Для примера можете выписать на листочек массив source = { 7,9,8,5,4,7,7 }, и проделать с ним все операции, имея в виду m=9.

I. Составим таблицу распределения. В ней будет m ( = 256 ) значений и заполняться она будет так:

for ( i = 0; i
#include

void radix (int byte, long N, long *source, long *dest)
{
long count[256];
long index[256];
memset (count, 0, sizeof (count));
for ( int i=0; i>(byte*8))&0xff]++;
index[0]=0;
for ( i=1; i(byte*8))&0xff]++]=source[i];
}

void radixsort (long *source, long *temp, long N)
{
radix (0, N, source, temp);
radix (1, N, temp, source);
radix (2, N, source, temp);
radix (3, N, temp, source);
}

void make_random (long *data, long N)
{
for ( int i=0; i =p,
fp(p) = 1,
fi(p) = 0 для 0 = значения ключа последней прочитанной записи.
Если все «старые» ключи меньше последнего ключа, то мы достигли конца отрезка. Выбираем запись с наименьшим ключом в качестве первого элемента следующего отрезка.
Записываем выбранную запись.
Заменяем выбранную и записанную запись на новую из входного файла.
Hа следующей таблице выбор с замещением иллюстрируются для совсем маленького файла.

Hачало файла — справа. Чтобы упростить пример, считается, что в буфер помещается всего лишь 2 записи. Конечно, в реальных задачах в буфер помещаются тысячи записей. Мы загружаем буфер на шаге В и записываем в выходной файл запись с наименьшим номером >= 6 на шаге D. Ею оказалась запись с ключом 7. Теперь мы заменяем ее на новую запись из входного файла — с ключом 4. Процесс продолжается до шага F, где мы оказывается, что последний записанный ключ равен 8 и все ключи меньше 8. В этот момент мы заканчиваем формирование текущего отрезка и начинаем формирование следующего.

Шаг Вход Буфер Выход
A 5-3-4-8-6-7
B 5-3-4-8 6-7
C 5-3-4 8-7 6
D 5-3 8-4 7-6
E 5 3-4 8-7-6
F 5-4 3 | 8-7-6
G 5 4-3 | 8-7-6
H 5-4-3 | 8-7-6

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

Прочитав из входного файла очередную запись, мы ищем наименьший ключ, который >= последнего считанного. При этом мы, конечно, можем просто сканировать записи в буфере. Однако, если таких записей тысячи, время поиска может оказаться недопустимо большим. Если на этом этапе использовать двоичные деревья, нам понадобится всего лишь log n сравнений.

Реализация
В реализации внешней сортировки на ANSI-C функция makeRuns вызывает readRec для чтения очередной записи. В функции readRec используется выбор с замещением (с двоичными деревьями) для получения нужной записи, а makeRuns распределяет записи согласно ряду Фибоначчи. Если количество отрезков оказывается вне последовательности Фибоначчи, в начало каждого файла добавляются пустые отрезки. Затем вызывается функция mergeSort, которая производит многофазное слияние отрезков.

/* внешняя сортировка */

#include
#include
#include

/* темплейт для временных файлов (формат 8.3) */
#define FNAME "_sort%03d.dat"
#define LNAME 13

/* операторы сравнения */
#define compLT(x,y) (x y)

/* определяем сортируемые записи */
#define LRECL 100
typedef int keyType;
typedef struct recTypeTag {
keyType key; /* ключ, по которому сортируем */
#if LRECL
char data[LRECL-sizeof(keyType)]; /* остальные поля */
#endif
} recType;

typedef enum {false, true} bool;

typedef struct tmpFileTag {
FILE *fp; /* указатель на файл */
char name[LNAME]; /* имя файла */
recType rec; /* последняя прочитанная запись */
int dummy; /* номер холостых проходов */
bool eof; /* флаг конца пробега end-of-file */
bool eor; /* флаг конца прохода end-of-run */
bool valid; /* верно, если запись — годная */
int fib; /* идеальное число Фибоначчи */
} tmpFileType;

static tmpFileType **file; /* массив информации о временных файлах */
static int nTmpFiles; /* количество временных файлов */
static char *ifName; /* имя входного файла */
static char *ofName; /* имя выходного файла */

static int level; /* уровень проходов */
static int nNodes; /* количество узлов для дерева выбора */

void deleteTmpFiles(void) {
int i;

/* удалить сливаемые файлы и освободить ресурсы */
if (file) {
for (i = 0; i fp) fclose(file[i]->fp);
if (*file[i]->name) remove(file[i]->name);
free (file[i]);
}
}
free (file);
}
}

void termTmpFiles(int rc) {

/* очистить файлы */
remove(ofName);
if (rc == 0) {
int fileT;

/* file[T] содержит результаты */
fileT = nTmpFiles — 1;
fclose(file[fileT]->fp); file[fileT]->fp = NULL;
if (rename(file[fileT]->name, ofName)) {
perror(«io1»);
deleteTmpFiles();
exit(1);
}
*file[fileT]->name = 0;
}
deleteTmpFiles();
}

void cleanExit(int rc) {

/* очистить временные файлы и выйти */
termTmpFiles(rc);
exit(rc);
}

void *safeMalloc(size_t size) {
void *p;

/* Безопасно выделить память и инициализоваться */
if ((p = calloc(1, size)) == NULL) {
printf(«error: malloc failed, size = %d», size);
cleanExit(1);
}
return p;
}

void initTmpFiles(void) {
int i;
tmpFileType *fileInfo;

/* инициализовать файлы для слияния */
if (nTmpFiles name, FNAME, i);
if ((file[i]->fp = fopen(file[i]->name, «w+b»)) == NULL) {
perror(«io2»);
cleanExit(1);
}
}
}

recType *readRec(void) {

typedef struct iNodeTag { /* внутренний узел */
struct iNodeTag *parent;/* предок внутреннего узла */
struct eNodeTag *loser; /* внешний проигравший */
} iNodeType;

typedef struct eNodeTag { /* внешний узел */
struct iNodeTag *parent;/* предок внешнего узла */
recType rec; /* вводимая запись */
int run; /* номер прохода */
bool valid; /* вводимая запись годна */
} eNodeType;

typedef struct nodeTag {
iNodeType i; /* внутренний узел */
eNodeType e; /* внешний узел */
} nodeType;

static nodeType *node; /* массив узлов дерева выбора */
static eNodeType *win; /* новый победитель */
static FILE *ifp; /* входной файл */
static bool eof; /* верно, если конец входного файла */
static int maxRun; /* максимальное число проходов */
static int curRun; /* номер текущего прохода */
iNodeType *p; /* указатель на внутренние узлы */
static bool lastKeyValid; /* верно, если lastKey годен */
static keyType lastKey; /* последний ключ lastKey записан */

/* Прочитать следующую запись путем выбора с замещением */

/* Проверка на первый выхов */
if (node == NULL) {
int i;

if (nNodes rec, sizeof(recType), 1, ifp) == 1) {
if ((!lastKeyValid || compLT(win->rec.key, lastKey))
&& (++win->run > maxRun))
maxRun = win->run;
win->valid = true;
} else if (feof(ifp)) {
fclose(ifp);
eof = true;
win->valid = false;
win->run = maxRun + 1;
} else {
perror(«io4»);
cleanExit(1);
}
} else {
win->valid = false;
win->run = maxRun + 1;
}

/* привести в порядок предков победителя и проигравшего */
p = win->parent;
do {
bool swap;
swap = false;
if (p->loser->run run) {
swap = true;
} else if (p->loser->run == win->run) {
if (p->loser->valid && win->valid) {
if (compLT(p->loser->rec.key, win->rec.key))
swap = true;
} else {
swap = true;
}
}
if (swap) {
/* p должно быть победителем */
eNodeType *t;

t = p->loser;
p->loser = win;
win = t;
}
p = p->parent;
} while (p != &node[0].i);

/* конец прохода? */
if (win->run != curRun) {
/* win->run = curRun + 1 */
if (win->run > maxRun) {
/* конец вывода */
free(node);
return NULL;
}
curRun = win->run;
}

/* вывести верх дерева */
if (win->run) {
lastKey = win->rec.key;
lastKeyValid = true;
return &win->rec;
}
}
}

void makeRuns(void) {
recType *win; /* победитель */
int fileT; /* прошлый файл */
int fileP; /* следующий за прошлым файлом */
int j; /* выбираем file[j] */


/* Сделать инициализационные проходы через выбор с замещением.
* Проходы напианы с использованием распределения Фибоначчи.
*/

/* инициализовать файловые структуры */
fileT = nTmpFiles — 1;
fileP = fileT — 1;
for (j = 0; j fib = 1;
file[j]->dummy = 1;
}
file[fileT]->fib = 0;
file[fileT]->dummy = 0;

level = 1;
j = 0;


win = readRec();
while (win) {
bool anyrun;

anyrun = false;
for (j = 0; win && j valid) {
if (!compLT(win->key, file[j]->rec.key)) {
/* добавить к существующему проходу */
run = true;
} else if (file[j]->dummy) {
/* начать новый проход */
file[j]->dummy--;
run = true;
}
} else {
/* первый проход в файле */
file[j]->dummy--;
run = true;
}

if (run) {
anyrun = true;

/* полный проход */
while(1) {
if (fwrite(win, sizeof(recType), 1, file[j]->fp) != 1) {
perror(«io3»);
cleanExit(1);
}
file[j]->rec.key = win->key;
file[j]->valid = true;
if ((win = readRec()) == NULL) break;
if (compLT(win->key, file[j]->rec.key)) break;
}
}
}

/* Если нет места для проходов — вверх на уровень */
if (!anyrun) {
int t;
level++;
t = file[0]->fib;
for (j = 0; j dummy = t + file[j+1]->fib — file[j]->fib;
file[j]->fib = t + file[j+1]->fib;
}
}
}
}

void rewindFile(int j) {
/* Идти в начало file[j] и читать первую запись */
file[j]->eor = false;
file[j]->eof = false;
rewind(file[j]->fp);
if (fread(&file[j]->rec, sizeof(recType), 1, file[j]->fp) != 1) {
if (feof(file[j]->fp)) {
file[j]->eor = true;
file[j]->eof = true;
} else {
perror(«io5»);
cleanExit(1);
}
}
}

void mergeSort(void) {
int fileT;
int fileP;
int j;
tmpFileType *tfile;

/* Многофазная сортировка слиянием */

fileT = nTmpFiles — 1;
fileP = fileT — 1;

/* снабдить файлы информацией */
for (j = 0; j dummy) {
allDummies = false;
if (!file[j]->eof) anyRuns = true;
}
}

if (anyRuns) {
int k;
keyType lastKey;

/* слить 1 проход file[0]..file[P] --> в file[T] */

while(1) {
/* Каждый проход по циклу записывает 1 запись в file[fileT]
*/

/* Hайти наименьший ключ */
k = -1;
for (j = 0; j eor) continue;
if (file[j]->dummy) continue;
if (k rec.key, file[j]->rec.key)))
k = j;
}
if (k rec, sizeof(recType), 1,
file[fileT]->fp) != 1) {
perror(«io6»);
cleanExit(1);
}

/* заменить record[k] */
lastKey = file[k]->rec.key;
if (fread(&file[k]->rec, sizeof(recType), 1,
file[k]->fp) == 1) {
/* проверить на предмет конца пробега file[s] */
if (compLT(file[k]->rec.key, lastKey))
file[k]->eor = true;
} else if (feof(file[k]->fp)) {
file[k]->eof = true;
file[k]->eor = true;
} else {
perror(«io7»);
cleanExit(1);
}
}

/* Подкорректировкать холостые */
for (j = 0; j dummy) file[j]->dummy--;
if (!file[j]->eof) file[j]->eor = false;
}

} else if (allDummies) {
for (j = 0; j dummy--;
file[fileT]->dummy++;
}

/* конец прохода */
if (file[fileP]->eof && !file[fileP]->dummy) {
/* completed a fibonocci-level */
level--;
if (!level) {
/* готово, file[fileT] содержит данные */
return;
}

/* fileP истощился, открываем новый такой же */
fclose(file[fileP]->fp);
if ((file[fileP]->fp = fopen(file[fileP]->name, «w+b»))
== NULL) {
perror(«io8»);
cleanExit(1);
}
file[fileP]->eof = false;
file[fileP]->eor = false;

rewindFile(fileT);

/* f[0],f[1]...,f[fileT] eof) file[j]->eor = false;
}
}

}
}


void extSort(void) {
initTmpFiles();
makeRuns();
mergeSort();
termTmpFiles(0);
}

int main(int argc, char *argv[]) {

/* командная строка:
*
* ext ifName ofName nTmpFiles nNodes
*
* ext in.dat out.dat 5 2000
* читает in.dat, сортирует, используя 5 файлов и 2000 узлов,
* выводит в out.dat
*/
if (argc != 5) {
printf("%s ifName ofName nTmpFiles nNodes", argv[0]);
cleanExit(1);
}

ifName = argv[1];
ofName = argv[2];
nTmpFiles = atoi(argv[3]);
nNodes = atoi(argv[4]);

printf(«extSort: nFiles=%d, nNodes=%d, lrecl=%d»,
nTmpFiles, nNodes, sizeof(recType));

extSort();

return 0;
}


Нравится
Не нравится

Комментарии

Нет комментариев. Ваш будет первым!