De doorsnede van twee verzamelingen vinden

De doorsnede van twee verzamelingen vinden Daniel von Asmuth

Inleiding Dit artikel probeert enkele algoritmen te vergelijken om de doorsnede van twee verzamelingen  of rijen van getallen te vinden. In een rij kunnen elementen meerdere keren voorkomen; we spre­ ken in plaats van sets over bags of multisets — de Nederlandse term is me niet bekend — die zon­ der extra moeite verwerkt kunnen worden.

I. Naïef: exhaustive search Zet beide verzamelingen in twee rijen (arrays of lists). Loop elk element van verzameling B af  om te zien of het eerste element van A daarin voorkomt, doe hetzelfde met het tweede element  van A, etc. De meeste besproken algoritmen werken ook voor rijen getallen waarin elementen  meer dan eens kunnen voorkomen. Het probleem wordt opgelost in O(n^2) stappen. Vanwege de eenvoud gebruiken we deze me­ thode soms voor kleine verzamelingen.

II. Vectoren van bits In de programmeertaal Pascal is het berekenen van de doorsnede of vereniging van twee verza­ melingen een ingebouwde bewerking. Deelverzamelingen van een domein worden gerepresen­ teerd door vectoren van bits: als het ie bit hoog is dan bevat de verzameling dat element.  Sorteren is hiermee niet nodig. Voor deelverzamelingen van grote domeinen kost deze methode  veel tijd en geheugen, namelijk O(#D), waarin #D de grootte van het domein is. Als we overstappen op vectoren van gehele van gehele getallen dan kunnen we daarmee een  eenvoudig sorteeralgoritme vormen. Initialiseer een array A ter grootte van #D met nullen en  lees de getallen in: als je een waarde i vindt, dan hoog je A[i] op. Daarna loop je het array af en  als A[i] == c dan druk je c keer het getal i af. De rekentijd is in de orde van O(#D + n) stappen,  het benodigde geheugen kan onpraktisch zijn als D bijvoorbeeld uit de 32­bits integers bestaat. 

III. Sorteren Het probleem is gemakkelijker op te lossen wanneer beide verzamelingen gesorteerd zijn; als  dat niet het geval is, kunnen we het quicksort sorteeralgoritme aanpassen zodat de doorsnede al  tijdens het sorteren wordt gevonden. De programmacode in C is te vinden als listing 1 in de bij­ lagen.  Het belangrijkste onderdeel is de functie partition(), die een deelinterval van rij A van index s tot  en met m verdeelt in drie delen: van s t/m j komen getallen die kleiner zijn dan de pivot, tussen j  en i staan waarden gelijk aan de pivot en van i t/m m waarden groter dan de pivot, waarvoor we  een willekeurig element van rij A kiezen. 

begin i=s

j=m = pivot

< pivot

eind s

j

> pivot i

m

Figuur 1 De functie werkt door eerst de delen van het array links van index i en rechts van j af te zoeken  naar getallen groter of gelijk aan de pivot en omgekeerd en telkens paren getallen te verwisse­ len. Daarna worden de linker en rechter delen nog eens afgezocht naar waarden die gelijk zijn  aan de pivot. De functie retourneert de grenzen i en j; de gevonden segmenten kunnen leeg zijn. De hoofdfunctie intersect() kiest het midden van rij A als pivot en roept de functie partition() aan  voor rij A en B, tenzij de te sorteren deelrij slechts één element lang is. Daarna roept de functie  zich recursief aan op de deelrijen kleiner dan respectievelijk groter dan de pivot. De functies re­ port() en report2() drukken de gevonden waarden af.  Dit lost het probleem op in O(n.log(n)) stappen; een goede keus als de invoergegevens ongesor­ teerd zijn. Een nadeel van de aanpassing is dat de rijen na afloop niet volledig gesorteerd zijn,  maar daarvoor besparen we iets tijd door af en toe getallen over te slaan. 

IV. Hashing en radix sort Hashing kan sneller zijn dan sorteren. Daarvoor kiezen het aantal hash buckets bijvoorbeeld op  de wortel van #B (als #A > #B) en verdelen de rij A daarover en verdelen de rij B over een even  grote hash tabel. Daarna moet je de doorsneden bepalen tussen de inhoud van corresponderende paren buckets,  bijvoorbeeld met algoritme III. Als tenminste één van de buckets leeg is, kun je die overslaan. Dit algoritme zal Ω(n) rekenstappen nodig hebben, maar de output is ongesorteerd.   Een   verwante   techniek   heet  radix­sort.   Hierin   begin   je   met   de   invoer   te   verdelen   over   een  (zes)tiental buckets aan hand van het meest significante (hexadecimale) cijfer. De buckets ver­ deel je dan één voor één over kleinere buckets aan hand van het tweede cijfer. Na het laatste cij­ fer houd je groepen over waarin alle getallen gelijk zijn. Hiermee kun je gehele getallen sorteren in O(#D + n) rekentijd. Om doorsneden van twee verza­ melingen te vinden, verdelen we ze simultaan over de buckets. Als een bucket A i  leeg is, dan  kunnen we de bucket Bi  overslaan. Aan het eind hoeven we alleen van de aantallen getallen in  corresponderende buckets telkens de kleinste te nemen. Hiermee is de output netjes gesorteerd.

V. Klassiek: twee rijen mergen Als de rijen A en B al gesorteerd zijn, dan kan de doorsnede eenvoudig worden gevonden door  telkens de kleinste elementen van beide rijen te vergelijken: als ze gelijk zijn rapporteer je het ge­ tal en verwijdert beide elementen, anders verwijder je het kleinste en vergelijkt weer de twee  kleinste, enzovoorts. Dit lost het probleem eenvoudig op in O(n) stappen. Voor multisets kan het algoritme iets wor­ den versneld met een array waarin per positie de waarde van het element plus het aantal malen  dat ze voorkomt worden opgeslagen. 

VI. Binaire zoekbomen De representatie met vectoren van bits verspilt geheugen wanneer het domein groot is en de  verzamelingen kleiner; in zo'n geval zijn gelinkte lijsten beter, maar binaire bomen zijn sneller 

te doorzoeken. Omdat het domein bekend is, is het niet nodig om de zoeksleutels expliciet op  te slaan; een waarde correspondeert met een vaste positie in de boom. Daardoor zijn wel extra  interne knopen benodigd voor getallen die niet in de verzameling voorkomen. In plaats van  een bit, gebruiken we een integer veld om te tellen hoe vaak een getal in de verzameling voor­ komt. De broncode is te vinden in listing 2. Stelling  I.  De  functie intersect()  drukt  alle elementen  van  de doorsnede  van   boom   A en  boom B éénmaal af in stijgende volgorde. We geven een synopsis van het bewijs. De functie intersect() bestaat uit niets meer dan een  aanroep van intersect_r( tree_a, tree_b, 0, M­1) voor het domein [0..M­1]. A. Als  één (deel)verzameling leeg is, dan is de doorsnede van A en B ook leeg. Het if­statement zorgt in dat geval dat de functie geen uitvoer produceert.   if( node1 == NULL || node2 == NULL)     return;

B. De bomen zijn zo opgezet dat knopen steeds corresponderen met dezelfde zoeksleutel. De  node1 en node2 parameters verwijzen bij de eerste aanroep naar de beide wortels, bij de eerste  recursieve aanroep naar diens linker zoon, de tweede recursieve aanroep naar diens rechter  zoon. Dus verwijzen de parameters altijd naar de zelfde positie in de bomen. C. Als de doorsnede van de deelbomen, waarvan node1 en node2 de wortels zijn, niet leeg is,  dan zorgt het for­statement dat de functie de juiste uitvoer produceert als het om twee bladen  gaat en geen uitvoer als een interne knoop bij is.   for( i = 0; i < min( node1­>count, node2­>count); i++)     printf( "Gevonden: \t%05d \n", node_key);

D. De intersect_r() functie vergelijkt eerst de linker zonen, dan de knopen node1 en node2 zelf  en vervolgens de rechter zonen.    intersect_r( node1­>left, node2­>left, lo, node_key – 1);   for( i = 0; i < min( node1­>count, node2­>count); i++)     printf( "Gevonden: \t%05d \n", node_key);   intersect_r( node1­>right, node2­>right, node_key + 1, hi

E.  De intersect_r() functie drukt eerst de doorsnede van de linker deelbomen af, dan van de  wortels van de deelbomen en vervolgens van de rechter deelbomen.  Dit volgt met structurele inductie op bewering D, samen met de beweringen A, B, en C, die er­ voor zorgen dat elk element van de doorsnede precies één keer wordt afgedrukt. F. De intersect_r() functie drukt elementen van de doorsnede op volgorde af. De parameters lo  en hi zijn de onder­ en bovengrenzen van de deelbomen en de wortel deelt dat interval in drie  delen, waarvan eerst het interval [0..node_key­1] wordt verwerkt, dan node_key zelf, gevolgd  door [node_key+1, hi]. Dit volgt uit de code onder bewering D.   int           node_key        = min(max(hi / 2 + lo / 2 + 1, lo), hi);

G. Het domein [0..M] wordt zodanig onderverdeeld dat elk element correspondeert met pre­ cies één knoop in de zoekboom. Voor interval [0..0] is de sleutel 0  en wordt intersect_r() aangeroepen op de delen [0..­1] en  [2..0]. Dat zijn ongeldige waarden en de NULL­test zal die afvangen.  Voor interval [0..1]  is  de   sleutel 1 en  wordt   intersect_r() aangeroepen  op  de  delen  [0..0]   en  [2..0]. Het laatste is ongeldig en wordt door de NULL­test afgevangen.  Voor interval [0..2]  is  de   sleutel 2  en  wordt   intersect_r()  aangeroepen  op  de  delen   [0..1]  en  [3..2]. Het laatste is ongeldig en wordt door de NULL­test afgevangen. 

Voor  interval [3..3]  is  de  sleutel  3  en wordt  intersect_r() aangeroepen op de   delen [3..2]  en  [4..3]. Die zijn ongeldig en worden door de NULL­test afgevangen.  Voor interval [0..3]  is  de   sleutel 2  en  wordt   intersect_r()  aangeroepen  op  de  delen   [0..1]  en  [3..3].  De bewering G klopt dus voor M = 0, 1, 2 en 3; inductie bewijst ze voor alle waarden van M. Stelling II. Een deelverzameling van domein D met  e  elementen kan worden gerepresen­ teerd door een binaire boom met ten hoogste 2∙e knopen.  Als er e bladen zijn en e is een macht van 2, dan heeft de zoekboom 1 + 2 + 4 + 8 + ... + e/2 = e   – 1 interne knopen nodig. In ons geval kunnen interne knopen eveneens elementen van de ver­ zameling   representeren.   Voor   multisets   worden   alle   elementen   met   dezelfde   waarde   in   1  knoop opgeslagen en in één rekenstap verwerkt. Stelling III. Algoritme VIII bepaalt de doorsnede van twee verzamelingen in O(A ∩ B) re­ kentijd.  Voor stelling I hebben we laten zien dat elk blad en elke interne knoop die nodig is voor een  binaire boom van het resultaat één keer verwerkt wordt en in stelling II dat er minder interne  knopen dan bladen nodig zijn. Voor elk blad in het resultaat zal intersect_r() tweemaal worden  aangeroepen met een NULL parameter. De kosten van de if­test vergroten de tijd voor de ver­ werking van het blad maar weinig, dus is de stelling geldig.  Het opbouwen van de zoekboom kost in O(n.log(n)) stappen, maar als de invoer gesorteerd is  reduceert dat tot O(n). Eventueel is het mogelijk om het sorteren en opbouwen te combineren. 

VII. Gesorteerde rijen Hierboven gebruikten we een boom waarin de getalswaarden impliciet uit de locatie volgen, als  we daarentegen de locatie van de elementen vastleggen, krijgen we een array; als beide impliciet  zijn, komen we uit op de bit vectoren van paragraaf I.  De broncode is te vinden in listing 3. Dit algoritme is generieker dan het vorige. De zoeksleutels  zijn niet van te voren vastgelegd, zodat geen geheugenruimte aan lege knopen verspild wordt.  Het voornaamste verschil met algoritme V is dat de rij niet sequentieel wordt doorlopen, maar  telkens wordt opgedeeld in twee delen van gelijke lengte.  Als de zoeksleutel voor rij A kleiner is dan die voor rij B, dan kunnen we kleinere waarden dan  akey vinden in de linker deelbomen van A en B, maar voor grotere waarden moeten we de rech­ ter deelboom van A vergelijken met de gehele boom B; alleen als beide sleutels aan elkaar gelijk  zijn kunnen beide bomen worden opgesplitst.  De parameters xmin en xmax worden gebruikt om de zoektocht op tijd te beëindigen. De manier  waarop dit interval recursief wordt gesplitst garandeert dat elke sleutelwaarde één keer wordt  verwerkt; aanroepen van intersect() met overlappende array indices worden afgevangen door  de if­statements aan het begin. Die zorgen er tevens voor dat een deelboom van A niet verder  wordt afgelopen als de deelboom van B al leeg is en omgekeerd, zodat de rekentijd van dit al­ goritme eveneens lineair toeneemt met de grootte van de uitvoer.  We kunnen beredeneren dat wanneer de sleutels homogeen verdeeld zijn over het domein, de  kans dat een deelboom geen deel uitmaakt van de doorsnede wordt gegeven door

p g=

m−n! 1 ⋅ g  m−n−g! m

Hierin is g het aantal sleutels in de deelboom, ongeveer gelijk aan 2h waarin in h de hoogte is;  een blad bevindt zich op hoogte 0, m = #D is de grootte van het sleutel domein en n de grootte  van de verzameling. Voor bladen is de kans om te worden overgeslagen groot, maar hoger in de  boom wordt ze al snel verwaarloosbaar.  Tests met algoritme VI geven aan dat het aantal recursieve aanroepen ongeveer 150 % van de  grootte van de verzameling bedraagt, tegen 500 % voor algoritme VII, terwijl ze ongeveer even­ veel rekentijd kosten. Een oorzaak ligt in de malloc() functie om geheugen voor de boom te re­ serveren. 

Conclusies Met de algoritmen VI en VII uit dit artikel is het mogelijk is het mogelijk om de doorsnede van  twee verzamelingen te bepalen zonder alle elementen te testen. Als we zowel het domein als de  cardinaliteit van de verzamelingen laten toenemen, neemt de rekentijd recht evenredig toe: de  overgeslagen elementen vormen een constante fractie van het totaal. Voor non­uniform verdeel­ de zoeksleutels zal het iets sneller gaan. Bovengenoemde methoden vereisen dat de invoer ge­ sorteerd is; als dat niet het geval is zorgen de algoritmen III en IV en passant voor die sortering. Veel hogere snelheden zijn mogelijk door de algoritmen VI en VII zodanig aan te passen dat de  twee recursieve functieaanroepen parallel worden uitgevoerd; door de resultaten tijdelijk op te  slaan kunnen ze zonder weer te sorteren op volgorde worden afgedrukt.

Bijlagen Listing 1. Rij sorteren en doorsnede bepalen  #include <stdio.h> #include <stdlib.h> #include  #define  N   40 #define  M   60 #define min(a,b) (((a) < (b)) ? (a) : (b)) #define max(a,b) (((a) > (b)) ? (a) : (b)) int             a[ N]; int             b[ N]; /* vul rij met willekeurige waarden */ static void  fill_arrays( void) { int           i;   srand( time( 0));   for( i = 0; i < N; i++)   { a[i] = rand() % M;   }   srand( time( 0) + 1);   for( i = 0; i < N; i++)   { b[i] = rand() % M;   } } /* druk de rijen af */ static void  print_arrays() { int           i;   for( i = 0; i <= N ­ 1; i++)   { printf( "\t%05d\t%05d\n", a[i], b[i]);   }   printf( "\n"); } /* druk gemeenschappelijke elementen af */ static void report( int pivot, int amin, int amax, int bmin, int bmax) {   int           i;   for( i = 0; i <= min( amax ­ amin, bmax ­ bmin); i++)     printf( "%05d\n", pivot); } /* tel gemeenschappelijke elementen */ static void report2( int pivot, int amin, int amax, int bmin, int bmax) {   int           ac              = 0;   int           bc              = 0;   int           i;   for( i = amin; i <= amax; i++)     if( a[i] == pivot)       ac++;   for( i = bmin; i <= bmax; i++)     if( b[i] == pivot)       bc++;   report( pivot, 1, ac, 1, bc); }

/* verwissel twee getallen */ static void swap( int *a, int *b) {   int           c;   c = *a; *a = *b; *b = c; } /* rangschik de waarden tussen s en m door de waarde te vergelijken met pivot*/ static void partition( int *a, int pivot, int s, int m, int *i, int *j) {   int           g;   /* eerst verwisselen we elementen groter en kleiner dan of gelijk aan de pivot */   *i = s; *j = m;   while( *i < *j)   { for( ; *i <= m; (*i)++)       if( a[*i] >= pivot)         break;     *i = min( *i, m);     for( ; *j >= s; (*j)­­)       if( a[*j] <= pivot)         break;     *j = max( *j, s);     if( *i < *j)      { swap( a + *i, a + *j);       (*i)++; (*j)­­;     }   }   swap( i, j);   while( *j >= *i && a[*j] >= pivot)     (*j)­­;   while( *i <= *j && a[*i] <= pivot)     (*i)++;   /* daarna zoeken we elementen gelijk aan de pivot */   for( g = *j; g >= s; g­­)     if( a[g] == pivot)     { swap( a + g, a + *j);       (*j)­­;     }   for( g = *i; g <= m; g++)     if( a[g] == pivot)     { swap( a + g, a + *i);       (*i)++;     }   /* corrigeer de grenzen nog eens, bijv. voor lege intervallen */   while( *j >= s && a[*j] >= pivot)     (*j)­­;   while( *i <= m && a[*i] <= pivot)     (*i)++; } /* Bepaal de doorsnede van deelrijen A en B tussen Amin en Amax, Bmin en Bmax */ static void  intersect( int *a, int amin, int amax, int *b, int bmin, int bmax) {   int           f, ai, aj, bi, bj;   int           pivot;   /* test of de deelrijen nul of een elementen bevatten */   if (amin > amax || bmin > bmax)     return;   if (amin == amax)   { report2( a[amin], amin, amax, bmin, bmax);     return;   }   else 

    if( bmin == bmax)     { report2( b[bmin], amin, amax, bmin, bmax);       return;     }   /* bepaal de pivot en partitioneer de arrays */   f = (amin + amax) / 2;    pivot = a[f];   if( amin < amax)     partition( a, pivot, amin, amax, &ai, &aj);   else     ai = aj = amin;   if( bmin < bmax)     partition( b, pivot, bmin, bmax, &bi, &bj);   else     bi = bj = bmin;   /* druk gevonden waarden af en doorzoek deelrijen kleiner en groter dan pivot */   intersect( a, amin, aj, b, bmin, bj);   report( pivot, aj+1, ai­1, bj+1, bi­1);   intersect( a, ai, amax, b, bi, bmax); } int main( int argc, char **argv) {   fill_arrays();   print_arrays();   intersect( a, 0, N ­ 1, b, 0, N ­ 1);   exit( 0); }

Listing 2. Doorsnede van twee binaire bomen #include <stdio.h> #include <stdlib.h> #include <stdint.h> #include  #define min(a,b) (((a) < (b)) ? (a) : (b)) #define max(a,b) (((a) > (b)) ? (a) : (b)) #define  N   30 #define  M  100

/* aantal elementen in verzameling */ /* maximum waarde van een element */

int             a[ N]; int             b[ N];

/* tijdelijke opslag voor getalswaarden */

typedef         struct node { int           count;   struct node   *left;   struct node   *right; } NODE, *NODE_P;

/* hoevaak de waarde voorkomt */ /* wijzer naar kleinere elementen */ /* wijzer naar grotere elementen */

/* maak een nieuw element voor in de boom */ static NODE_P create_node( void) {   NODE_P        result;   if((result = (NODE_P) malloc( sizeof( NODE))) == NULL)   { fprintf( stderr, "Malloc() failed \n");     exit( 1);   }   else   { result­> count = 0;     result­>left = result­>right = NULL;   }   return result; } /* recursief deel van opbouwfunctie */

static void build_tree_r( NODE_P *node_p, int *keys, int *i, int lo, int hi) {   int           node_key        = min(max(hi / 2 + lo / 2 + 1, lo), hi);   if( *i >= N || keys[*i] < lo || keys[*i] > hi)     return; /* test om recursie te termineren */   if( *node_p == NULL)     *node_p = create_node(); /* voeg nieuwe knoop toe aan boom */   if( keys[*i] == node_key)   { (*node_p)­>count++; /* tel het element mee */     ++*i;   }   if( keys[*i] < node_key) /* getal te klein; zoek verder */     build_tree_r( &(*node_p)­>left, keys, i, lo, node_key ­ 1);   else     if( keys[*i] > node_key) /* getal te groot; zoek verder */       build_tree_r( &(*node_p)­>right, keys, i, node_key + 1, hi);   build_tree_r( node_p, keys, i, lo, hi); }

/* ga verder met volgende getal */

/* Bouw een zoekboom van de elementen van een gesorteerde rij */ void build_tree( NODE_P *root, int *keys) {   int           i       = 0;   build_tree_r( root, keys, &i, 0, M ­ 1); } /* Recursief deel van de bepaling van de doorsnede */ static void intersect_r( NODE_P node1, NODE_P node2, int lo, int hi) {   int           node_key        = min(max(hi / 2 + lo / 2 + 1, lo), hi);   int           i;   if( node1 == NULL || node2 == NULL)     return;

/* controleer of we al klaar zijn */

  intersect_r( node1­>left, node2­>left, lo, node_key – 1);   /* het kleinste aantal malen dat element voorkomt bepaalt de doorsnede */   for( i = 0; i < min( node1­>count, node2­>count); i++)     printf( "Gevonden: \t%05d \n", node_key);   intersect_r( node1­>right, node2­>right, node_key + 1, hi); } /* Druk de gemeenschappelijke elementen in twee bomen af */ void intersect( NODE_P tree1, NODE_P tree2) {   printf( "\nDe doorsnede bestaat uit: \n");   intersect_r( tree1, tree2, 0, M ­ 1); } /* Vul rijen met willekeurige getallen */ static void fill_arrays( void) { int           i;   srand( time( 0));   for( i = 0; i < N; i++)   { a[i] = rand() % M;   }   srand( time( 0) + 1);   for( i = 0; i < N; i++)   { b[i] = rand() % M;   } } /* een hulpfunctie voor quicksort */ static int compare( const void *a, const void *b) { return *(int *)a ­ *(int *)b; }

/* het hoofdprogramma */ int main( int argc, char **argv) {   NODE_P        tree_a          = NULL;   NODE_P        tree_b          = NULL;   fill_arrays();   qsort( a, N, sizeof( int), compare);   qsort( b, N, sizeof( int), compare);   build_tree( &tree_a, a);   build_tree( &tree_b, b);

/* vul geheugen met de getallen */

  intersect( tree_a, tree_b);   return 0; }

/* bepaal de doorsnede */

/* sorteer de waarden eerst */ /* om de bomen snel op te bouwen */

Listing 3. Doorsnede van twee rijen #include <stdio.h> #include <stdlib.h> #include <stdint.h> #include  #define  N      30 #define  M      60 #define min(a,b) (((a) < (b)) ? (a) : (b)) #define max(a,b) (((a) > (b)) ? (a) : (b)) int             a[ N]; int             b[ N]; /* http://stackoverflow.com/questions/1903954/is­there­a­standard­sign­function­ signum­sgn­in­c­c */ int sgn(int val) {   return (val > 0) ­ (val < 0); } /* vul rijen met willekeurige getallen */ void fill_arrays( void) { int           i;   srand( time( 0));   for( i = 0; i < N; i++)     a[i] = rand() % M;   srand( time( 0) + 1);   for( i = 0; i < N; i++)     b[i] = rand() % M; } /* hulpfunctie voor sorteren */ static int compare( const void *a, const void *b) { return *(int *)a ­ *(int *)b; } void print_arrays( void) { int           i;   for( i = 0; i < N; i++)     printf( "%d:\t%05d\t%05d\n", i, a[i], b[i]);   printf( "\n"); } /* druk resultaat af */ void found( int x) {    if( x >= 0)     printf( "Found value\t%05d \n", x); }

/* bepaal de doorsnede van twee (deel)rijen A en B */ static void intersect( int a[], int amin, int amax, int b[], int bmin, int bmax,   int xmin, int xmax) {   int           ai              = min(max(amin / 2 + amax / 2 + 1, amin), amax);   int           bi              = min(max(bmin / 2 + bmax / 2 + 1, bmin), bmax);   int           aj              = ai;   int           bj              = bi;   int           akey            = a[ai]; /* de zoeksleutels */   int           bkey            = b[bi];   int           i;   /* controleer of de deelrijen leeg zijn */   if((amin > amax) || (bmin > bmax))     return;   /* controleer of de waarden binnen de grenzen vallen */   if((a[amin] > xmax) || (a[amax] < xmin) || (b[bmin] > xmax) || (b[bmax] < xmin))     return;      /* zoek getallen gelijk aan de sleutels */   while((ai > amin) && (a[ai­1] == akey))     ai­­;   while((aj < amax) && (a[aj+1] == akey))     aj++;   while((bi > bmin) && (b[bi­1] == bkey))     bi­­;   while((bj < bmax) && (b[bj+1] == bkey))     bj++;   /* pas het algoritme recursief toe op de rest van het array */   switch( sgn( akey ­ bkey))   { case ­1: intersect( a, amin, aj,    b, bmin, bi­1,  xmin,   akey);              intersect( a, aj+1, amax,  b, bmin, bmax,  akey+1, xmax);              break;     case 1:  intersect( a, amin, ai­1,  b, bmin, bj,    xmin,   bkey);             intersect( a, amin, amax,  b, bj+1, bmax,  bkey+1, xmax);             break;     case 0: intersect( a, amin, ai­1,  b, bmin, bi­1,  xmin,   akey­1);             for( i = 0; i <= min( aj­ai, bj­bi); i++)               found( akey);        intersect( a, aj+1, amax,  b, bj+1, bmax,  akey+1, xmax);            break;   } } int main( int argc, char **argv) {   fill_arrays();   qsort( a, N, sizeof( int), compare);   /* standaard quicksort functie */   qsort( b, N, sizeof( int), compare);   print_arrays();   intersect(a, 0, N­1, b, 0, N­1, max(a[0],b[0]), min(a[N­1],b[N­1]));   exit( 0); }