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

[gigacomp]

Кто знает код быстрой сортировки?

void Sort(int v[],int n)
{
 int* vp;           
 int* vz=v+n-1;     
 int i,t;
 while (v<vz){      
  vp=vz;            
  while (vp>v){      
   if (*v > *vp){   
    t=*v;           
    *v=*vp;
    *vp=t;
    }
   vp--;             
  }
  v++;               
 }          
}

Этот код наверняка показывает не самые шикарные результаты...

[PapaKarlo]

Посмотрите "Дональд Кнут. Искусство программирования, том 3. Сортировка и поиск"

[Ed_Em]

Почитайте "Numerical recipes in C".
Наиболее быстрый алгоритм сортировки переменного количества аргументов:

Используется синтаксис C

#include <stdlib.h>
#include <stdio.h>
/*
  * This Quickselect routine is based on the algorithm described in
  * "Numerical recipes in C", Second Edition,
  * Cambridge University Press, 1992, Section 8.5, ISBN 0-521-43108-5
  * This code by Nicolas Devillard - 1998. Public domain.
  */
typedef int elem_type;
#define ELEM_SWAP(a,b) { register elem_type t=(a);(a)=(b);(b)=t; }
elem_type quick_select(elem_type arr[], int n)
{
     int low, high ;
     int median;
     int middle, ll, hh;
     low = 0 ; high = n-1 ; median = (low + high) / 2;
     for (;;) {
         if (high <= low) /* One element only */
             return arr[median] ;
         if (high == low + 1) { /* Two elements only */
             if (arr[low] > arr[high])
                 ELEM_SWAP(arr[low], arr[high]) ;
             return arr[median] ;
         }
     /* Find median of low, middle and high items; swap into position low */
     middle = (low + high) / 2;
     if (arr[middle] > arr[high])    ELEM_SWAP(arr[middle], arr[high]) ;
     if (arr[low] > arr[high])       ELEM_SWAP(arr[low], arr[high]) ;
     if (arr[middle] > arr[low])     ELEM_SWAP(arr[middle], arr[low]) ;
     /* Swap low item (now in position middle) into position (low+1) */
     ELEM_SWAP(arr[middle], arr[low+1]) ;
     /* Nibble from each end towards middle, swapping items when stuck */
     ll = low + 1;
     hh = high;
     for (;;) {
         do ll++; while (arr[low] > arr[ll]) ;
         do hh--; while (arr[hh] > arr[low]) ;
         if (hh < ll)
         break;
         ELEM_SWAP(arr[ll], arr[hh]) ;
     }
     /* Swap middle item (in position low) back into correct position */
     ELEM_SWAP(arr[low], arr[hh]) ;
     /* Re-set active partition */
     if (hh <= median)
         low = ll;
        if (hh >= median)
        high = hh - 1;
    }
}
#undef ELEM_SWAP
 

Самый быстрый алгоритм для фиксированного количества аргументов, в данном случае - для девяти (для другого количества см. те же Num.rec):

typedef int pixelvalue ;
#define PIX_SORT(a,b) { if ((a)>(b)) PIX_SWAP((a),(b)); }
#define PIX_SWAP(a,b) { pixelvalue temp=(a);(a)=(b);(b)=temp; }

pixelvalue opt_med9(pixelvalue * p)
{
    PIX_SORT(p[1], p[2]) ; PIX_SORT(p[4], p[5]) ; PIX_SORT(p[7], p[8]) ;
    PIX_SORT(p[0], p[1]) ; PIX_SORT(p[3], p[4]) ; PIX_SORT(p[6], p[7]) ;
    PIX_SORT(p[1], p[2]) ; PIX_SORT(p[4], p[5]) ; PIX_SORT(p[7], p[8]) ;
    PIX_SORT(p[0], p[3]) ; PIX_SORT(p[5], p[8]) ; PIX_SORT(p[4], p[7]) ;
    PIX_SORT(p[3], p[6]) ; PIX_SORT(p[1], p[4]) ; PIX_SORT(p[2], p[5]) ;
    PIX_SORT(p[4], p[7]) ; PIX_SORT(p[4], p[2]) ; PIX_SORT(p[6], p[4]) ;
    PIX_SORT(p[4], p[2]) ; return(p[4]) ;
}

Бенчмарк (медианная фильтрация с использованием указанных алгоритмов, время в секундах):

                                          quick_median   optim
усреднение изобр. 500х500 по 3х3 (full)____0.096
-//- без краев_____________________________0.084
-//- -//- с ускорением набора массива______0.056      0.028
-//- 300x300 -//-//-//_____________________0.020      0.010
-//-   1000x1000___________________________0.223      0.111