Vaje 5

Simona Perčič

10.11.1997

Urejanje (sortiranje) števil

Oglejmo si, kako lahko uredimo zaporedje števil:

Imejmo neko zaporedje števil

a_{1}, a_{2}, ..., a_{n}

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

Med danim zaporedjem a_{j}, a_{i1}, a_{i2}, …, a_{ik}, a_{ik+1}, …, kjer i-teče, zamenjamo a_{j} in a_{ik} tako, da dobimo novo zaporedje števil in sicer a_{ik}, a_{i1}, a_{i2}, …, a_{j}, a_{ik+1}, . . .. Pri tem pa dobimo števila razporejena v dve podzaporedji in sicer:

• zaporedje števil pred a_{j} je manjše od a_{j},

• zaporedje števil za a_{j} pa je večje od a_{j}.

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 */

Risanje grafov

Poglejmo na primeru kako lahko rišemo grafe:

#include<stdio.h>
#include<conio.h>
#include<graphics.h> /*knjiznica za grafiko*/
#include<process.h>
void main() {
clrscr();
int ix, j, mx, my, gd, gm, c;
float az, ak, a, da, x;
printf("Napisi zacetno in koncno vrednost a:\n");
scanf("%f %f", &az, &ak);
detectgraph(&gd, &gm);            /* gd-graph driver,
                                    gm-graph mode*/
initgraph(&gd, &gm, "u:priimek"); /* u:priimek-ce imamo
                                    nalozeno EGAVGA.BGI */
c= graphresult();
if (c != 0) {                     /* ce ni uspesen, */
  printf("Napaka \n");            /* javi napako
  getch();

  exit(0);
};
a= az;
mx= getmaxx();                    /* ukazi za risanje crt */
my= getmaxy();
da= (ak-az)/mx;                   /* korak v smeri a-ja */
x= 0.5;
for(ix= 0; ix <= mx; ix++) {
  for(j=0; ix <= 500; j++)
    x=a*x*(1-x);
  for(j=0;ix<=400;j++) {
    x= a*x*(1-x);
    putpixel(ix, (int)((1-x)*my), 15); /* obrne os y navzgor */
  }
  a=a+ad;
}
getch();
closegraph();                     /* grafika zakljucena */
}