Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Сортировка / FAQ /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Описание и исходник QuickSort (быстрая сортировка) - Программирование от RIN.RU
Описание и исходник QuickSort (быстрая сортировка)

Основной алгоритм


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


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


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


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


Устойчивости нет. Поведение неестественно.


Пример рекурсивной 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 < j && compGT(pivot, a[i])) i++;
while (j >= 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 < ub) {


/* сортировка вставками для малых массивов */
if (ub - lb <= 12) {
insertSort(a, lb, ub);
return;
}


/* разделение пополам */
m = partition (a, lb, ub);


/* Уменьшаем требования к памяти: */
/* меньший сегмент сортируем первым */
if (m - lb <= ub - m) {
quickSort(a, lb, m - 1);
lb = m + 1;
} else {
quickSort(a, m + 1, ub);
ub = m - 1;
}
}
}


Улучшения


Hа практике для увеличения быстроты, можно произвести несколько улучшений:


  1. Произвести случайную перестановку всех чисел массива перед сортировкой. Алгоритм с этим улушением называется Randomized Quicksort и работает в среднем за O(nlogn) времени при любых неприятных закономерностях в потоке входных данных.


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

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

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

  4. После разбиения сначала сортируется меньший раздел. Это также приводит к лучшему использованию стека, поскольку короткие разделы сортируются быстрее и им нужен более короткий стек. Требования к памяти уменьшаются с n до log n.
    Пример, входящий в стандартную реализацию Си использует многие из этих улучшений.




Стандартная реализация итерационной QuickSort


#include
#define MAXSTACK (sizeof(size_t) * CHAR_BIT)


static void exchange(void *a, void *b, size_t size) {
size_t i;


/******************
* обменять a,b *
******************/


for (i = sizeof(int); i <= size; i += sizeof(int)) {
int t = *((int *)a);
*(((int *)a)++) = *((int *)b);
*(((int *)b)++) = t;
}
for (i = i - sizeof(int) + 1; i <= size; i++) {
char t = *((char *)a);
*(((char *)a)++) = *((char *)b);
*(((char *)b)++) = t;
}
}


void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *)) {
void *lbStack[MAXSTACK], *ubStack[MAXSTACK];
int sp;
unsigned int offset;


lbStack[0] = (char *)base;
ubStack[0] = (char *)base + (nmemb-1)*size;
for (sp = 0; sp >= 0; sp--) {
char *lb, *ub, *m;
char *P, *i, *j;


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


while (lb < ub) {


/* выбираем центр и меняемся с 1м элементом */
offset = (ub - lb) >> 1;
P = lb + offset - offset % size;
exchange (lb, P, size);


/* разделение в два сегмента */
i = lb + size;
j = ub;
while (1) {
while (i < j && compar(lb, 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 <= ub - m) {
if (m + size < ub) {
lbStack[sp] = m + size;
ubStack[sp++] = ub;
}
ub = m - size;
} else {
if (m - size > lb) {
lbStack[sp] = lb;
ubStack[sp++] = m - size;
}
lb = m + size;
}
}
}
}




 8  Комментарии к статье  8 8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь