qsort

From

Max Alekseyev (2:5015/60)

To

Anatoly Svishev

Date

2002-10-07T11:47:32Z

Area

RU.ALGORITHMS

████ OS/2        Hi, Anatoly !

Replying to a message of Anatoly Svishev to Max Alekseyev:

 AS> int a[]={16,1,2,3,16,17,18,19};
 AS> Здесь будет вечное зависание ...

Та версия была для массива из _различных_ чисел. Если есть одинаковые - то вот модификация:

===cut===
void qsort(int *a,int d)          // quicksort array a[0],...,a[d-1]
{
    if(d<=1) return;
    int med = a[0], i = 0, j = d-1;
    while(1) {
        while((i<j) && (a[j]>=med)) j--;
        while((i<j) && (a[i]<med)) i++;
        if(i>=j) break;
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    j++;
    printf("%d: ",j);
    for(int i=0;i<d;i++) printf("%d ",a[i]);
    printf("\n");
    qsort(a,j); qsort(&a[j],d-j);
}
===cut===

ЗЫ. med = a[0] можно заменить, например, на med = a[rand()%d];

Regards,      °°
        Max    ~

--- FleetStreet 1.27.3.8
 * Origin:  (2:5015/60)