qsort

From

Max Alekseyev (2:5015/60)

To

Anatoly Svishev

Date

2002-10-08T20:12:28Z

Area

RU.ALGORITHMS

████ OS/2        Hi, Anatoly !

Replying to a message of Anatoly Svishev to Max Alekseyev:

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

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

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

 AS> небольшое замечание : &a[j] = a+j 

a smysl? &a[j] naglyadnee.

 AS> а теперь контрпример :

 AS> int a[]={16,17,18,19,16,17,18,19};// - он просто пройдет весь массив
 AS> справа налево и в цикл (вечный)

Net. Vse Ok. Zapusti i posmotri.

Regards,      °°
        Max    ~

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