Urejanje (sortiranje) števil

Oglejmo si, kako lahko uredimo zaporedje števil:

Imejmo neko zaporedje števil

Med njimi naj bo neko število slučajno in ga označimo z .

Med danim zaporedjem , kjer i-teče, zamenjamo in tako, da dobimo novo zaporedje števil in sicer . Pri tem pa dobimo števila razporejena v dve podzaporedji in sicer:

• zaporedje števil pred je manjše od ,
• zaporedje števil za pa je večje od .

V nadaljevanju vsako skupino števil še enkrat delimo in manjša števila spravimo levo, večja pa desno.

Ponavljamo dokler je smiselno.

Oglejmo si kako bi lahko tak program skonstruirali:

void Qsort(int a[], int zac, int kon) {
  int i, k;

  if (zac >= kon)  /* primerjamo zacetek in konec */
    return;        /* ce je zacetek vecji od konca ni nicesar
                      za urediti */

                        /* nakljucni vmesni element med podzaporedji
                           je kar prvi element */
  Zamenjaj(a, zac, (kon - zac)/2);
                        /* in se naredimo obe podzaporedji */
  for (i= zac+1, k= zac; i <= kon; i++)
    if (a[i]< a[zac])   /* ali prestavimo i-ti element ? */
      zamenjaj(a, ++k, i));  /* da, na k+1 mesto */

  zamenjaj(a, zac, k);  /* na koncu se pravilno postavimo vmesni
                           element */

                         /* Sedaj uredimo obe podzaporedji: */
  Qsort(a, zac, k-1);    /* uredimo stevila od zacetka do k ... */
  Qsort(a, k+1, kon);    /* in se stevila od k naprej */
} /* Qsort */

void Zamenjaj(int a[], int i, int k) {
  int c;
  c= a[i]; a[i]= a[k]; a[k]= c;
} /* Zamenjaj */