Алгоритм быстрой сортировки QuickSort

Алгоритм QuickSort является ярким примером использования идеи divide-and-conquer (разделяй и властвуй) и первым нетривиальным примером использования рекурсии. Кроме того, алгоритм QuickSort — это самый простой алгоритм сортировки, который работает в среднем время N log N, где N — число элементов.

Функция QuickSort сводит сортировку данного ей массива к разделению (partitioning) этого массива на две группы элементов и сортировке этих двух групп по отдельности.

Пусть нам нужно отсортировать участок массива A с p-го по q-й элемент включительно, будем называть этот участок подмассивом и обозначать как A[p..q].

• ШАГ 1: Возьмем элемент A[p] и "раскидаем" остальные элементы A[(p+1)..q] по разные стороны от него стороны — меньшие влево, большие --- вправо, то есть переставим элементы подмассива A[p..q] так, чтобы вначале шли элементы меньше либо равные A[p] потом элементы, больше либо равные A[p]. Назовет этот шаг разделением (partition).

• ШАГ 2: Пусть r есть новый индекс элемента A[p]. Тогда, если q - p > 2, вызовем функцию сортировки для подмассивов A[p..(r-1)] и A[(r+1)..q].

Итак, процедура сортировки QuickSort выглядит следующим образом:

 QuickSort(A,p,q):
1:  if p < q
2:      then r = Partition(A, p, q)
3:          QuickSort(A,p,r-1)
4:          QuickSort(A,r+1,q)
 Partition(A,p,r):
5:  x = A[p]
6:  i = p - 1
7:  j = r + 1
8:  while TRUE
9:    do repeat j--
10:            untill A[j] <= x
11:        repeat i++
12:            untill A[i] >= x
13:        if i < j
14:            then поменять A[i] <-> A[j]
15:        else return j

Резализация на C:

int partition(int* a,int p, int r)
{
   int x, j, i, tmp;
   x = a[p]; j = r+1; i = p-1;
   while(1){
      while (a[--j] > x);
      while (a[++i] < x);
      if(i < j) 
      {
         tmp  = a[i];
         a[i] = a[j];
         a[j] = tmp;
      } else {
         return j;
      }
   }
}

void qsort(int *a,int p, int q)
{
    int r;
    if (p < q)
    {
        r = partition (a, p, q);
        qsort (a, p, r);
        qsort (a, r+1, q);
    }
}

А вот классическая реализация этого алгоритма из какой-то известной книжки:

#include <stdio.h>
#define N 1000
qsort( int* a, int lo, int hi ) 
{
  int h, l, p, t;
  if (lo < hi) {
     l = lo;
     h = hi;
     p = a[hi];
     do {
          while ((l < h) && (a[l] <= p)) l++;
          while ((h > l) && (a[h] >= p)) h--;
          if (l < h) {
             t = a[l]; a[l] = a[h]; a[h] = t;
          }
     } while (l < h);
  
     t = a[l]; a[l] = a[hi]; a[hi] = t;
  
     qsort( a, lo, l-1 );
     qsort( a, l+1, hi );
  }
}
int main()
{
   int n, i;
   int a[N];
   scanf ("%d", &n);
   for( i = 0 ; i < n ; i++ )
      scanf("%d", &a[i]);
   
   qsort(a, 0, n - 1);

   for( i = 0 ; i < n ; i++ )
      printf("%d ", a[i]);
}

-- ArtemVoroztsov - 16 Jul 2004