home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
C!T ROM 2
/
ctrom_ii_b.zip
/
ctrom_ii_b
/
C!T
/
C!T05_93
/
CLAPET
/
CLAPET.C
Wrap
C/C++ Source or Header
|
1993-01-12
|
10KB
|
362 lines
// Demonstratieprogramma: Clapet-sort versus Quick-sort
// Auteur: Koos Eenink te Apeldoorn
// Januari 1993
// de sorteermethode: Clapet-sort, verwijder het comment voor
// #define Q voor Quick-sorting
//#define Q
// Instelbare parameters: ****************************************************
// de record-lengte,
#define Key_Lengte 25
// optional print (naar scherm), verwijder comment voor scherm-print
//#define PR
// en formaat scherm-print
#define Print_Formaat "%-16s"
// Afgeleide instellingen: ***************************************************
// als niet Quicksort, dan Clapetsort
#ifndef Q
#define C
#endif
// Record-lengte gekozen: 1 + key-lengte, record wordt zodoende automatisch
// ASCIIZ formaat
#define Record_Lengte (Key_Lengte + 1)
// de lengte tabel met integers (indexen in buffer) en daarom ook het aantal
// records, is gelimiteerd (64kBytes -> 32k records): afgerond op 1000-tal
#define MAX_AANTAL_RECORDS 32000
// eind ketting indicator:
#define LEEG 0xffff
// div. standaard-includes ***************************************************
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include <conio.h>
#include <time.h>
#include <dos.h>
unsigned char
*recbuf, // begin record-buffer
*record, // ptr naar actuele record
*rnd = (char *)0xf0000000; // ptr naar ROM-programma voor 'randomizing'
// integers over pointers voor adres-calculatie, zie: zet_record_ptr()
//
// < pointer >
// <integer> <integer>
// | offset | segment |
//
unsigned int
*bufseg = (int *)(((char *) &recbuf) + 2),
*recseg = (int *)(((char *) &record) + 2),
*recofs = (int *)(((char *) &record));
//
unsigned int
aantal_records = MAX_AANTAL_RECORDS,
*ketting;
#define verwijzing ketting
// voor Clapetsort: volgnr volgende in ketting
// voor Qsort: volgnr in buffer, zelfde array wordt gebruikt
unsigned long
tim, // elapsed time
sizalloc; // aantal bytes in buffer (probeer_start-waarde)
#ifdef C
// de ankers:
unsigned int
*anker_in, // array: (256) ankers input sorteergang
*anker_uit, // idem output sorteergang
anker1[256], // 256 aflegvakken, afwisselend gebruikt voor in-
anker2[256]; // en output (anker_in resp. anker_uit)
#endif
// Prototypes
void Quick_sort ( int left, int right);
void Clapet_sort();
long prtim(char * txt);
void * zet_record_ptr(int x);
// ************************ Het hoofd-programma ******************************
void main(int argc,char **argv)
{
unsigned int
u1, // div. tellers
u2,
u3,
next; // index in ketting
long hulp_long_var;
unsigned char
hulp_char;
// met runtime parameter kan aantal_records (default 32000) overschreven
// worden
if (argc == 2)
sscanf(argv[1],"%d",&aantal_records);
// geheugen-allocaties
ketting = (unsigned int *) halloc(aantal_records,sizeof (int));
sizalloc=630000; // 1e probeer-waarde
while ((recbuf = (char *)halloc(sizalloc,1)) == NULL)
sizalloc -= 1000;
if ((sizalloc / Record_Lengte) <= aantal_records)
aantal_records = sizalloc / Record_Lengte;
// naar beneden afronden op duizendtal t.b.v. tijdregistratie:
if ((aantal_records = 1000 * (aantal_records / 1000)) == 0)
return;
printf(
"\nlengte buffer in bytes :%ld"
"\naantal bytes gebruikt :%ld"
"\naantal records :%u"
"\nRecord_Lengte :%d"
"\nKey_Lengte :%d",
sizalloc,
((long)aantal_records) * Record_Lengte,
aantal_records,
Record_Lengte,
Key_Lengte);
#ifdef Q
printf("\nsorteermethode :Quick-sort");
#else
printf("\nsorteermethode :Clapet-sort");
#endif
// initiele verwijzing (Qsort)
#ifdef Q
// n-de entry wijst naar n-de record
for (u1 = 0; u1 < aantal_records ; ++u1)
verwijzing[u1] = u1;
#else
// initiele ketting (Csort)
// n-de entry wijst naar (n+1)-de record
for (u1 = 0; u1 < aantal_records - 1; ++u1)
ketting[u1] = u1 + 1;
// laatste entry wijst naar niets
ketting[u1] = LEEG;
#endif
// vul records met "random" waarde
hulp_long_var = prtim("bezig met vullen van random-records");
for (u1=0; u1 < aantal_records; ++u1)
{
zet_record_ptr(u1);
for (u2 = 0; u2 < Key_Lengte; ++u2)
{
do
hulp_long_var = 41 * hulp_long_var + 41 + rnd[u3++];
while ((hulp_char = (hulp_long_var >> 6) & 127) < 32);
record[u2] = hulp_char;
}
}
tim = prtim("start sorting");
#ifdef Q
// Quick sort + optionele print
Quick_sort(0,aantal_records - 1);
tim = prtim("end sorting") - tim;
printf(" %3.2lf\n",tim/100.);
// het "ophalen" van de gesorteerde informatie voor verdere bewerking:
#ifdef PR
printf(" druk een toets\n");
getch(); // pauze om resultaten te bekijiken
#endif
for (u1 = 0;u1 < aantal_records; ++u1)
{
zet_record_ptr(verwijzing[u1]);
// doe hier wat gedaan moet worden met de gesorteerde informatie
#ifdef PR
printf(Print_Formaat,record);
#endif
}
#else
// Clapet sort + optionele print
Clapet_sort();
tim = prtim("end sorting") - tim;
printf(" %3.2f\n",tim/100.);
// het "ophalen" van de gesorteerde informatie voor verdere bewerking:
#ifdef PR
printf(" druk een toets\n");
getch(); // pauze om resultaten te bekijiken
#endif
for (u1 = 0; u1 < 256; ++u1)
{
next = anker_uit[u1];
while (next != LEEG)
{
zet_record_ptr(next);
// doe hier wat gedaan moet worden met de gesorteerde informatie
#ifdef PR
printf(Print_Formaat,record);
#endif
next = ketting[next];
}
}
#endif
}
#ifdef Q
// swapping
unsigned int
swap_help;
__inline void swap(unsigned int x,unsigned int y)
{
// swappen gebeurt eenvoudig door de inhoud van x-de en y-de entry in
// de array: ketting (verwijzing) te verwisselen
swap_help=verwijzing[x];
verwijzing[x]=verwijzing[y];
verwijzing[y]=swap_help;
}
unsigned char
* auxrec;
void Quick_sort ( int left, int right)
{
int i,
last;
if (left >= right)
return;
i = (left + right) / 2;
swap(left,i);
last = left;
for(i = left + 1;i <= right; ++i)
{
auxrec = zet_record_ptr(verwijzing[i]);
zet_record_ptr(verwijzing[left]);
if (strncmp(auxrec,record,Key_Lengte) < 0)
swap(++last,i);
}
swap(left,last);
Quick_sort(left,last-1);
Quick_sort(last+1,right);
}
#else // Clapet
void Clapet_sort()
{
static int anker_eind_ketting[256],
// administratie laatste in aflegvakvak
*anker_swap_hulp,
// voor swappen in- en output vakken
kolom, // kolom in key
next, // index volgende key
act_rec, // actuele record, save-veld volgende key
i; // teller
static unsigned char
ch; // karakter uit key
// initial
// alloceer anker_in en anker_uit
anker_in = anker1;
anker_uit = anker2;
// hang alles aan anker_uit[0],
// en anker_uit[1]..anker_uit[n] 'leegmaken'
anker_uit[0] = 0;
i = 1;
while( i < 256)
anker_uit[i++] = LEEG;
kolom = Key_Lengte;
// begin by laatste kolom (Key_lengte - 1 !) t/m kolom: 0 (eerste kolom)
while (kolom--)
{
// verwissel aflegvakken: gevulde vakken vorige slag worden nu input
anker_swap_hulp = anker_uit;
anker_uit = anker_in;
anker_in = anker_swap_hulp;
// maak te vullen vakken leeg
for (i = 0; i < 256; ++i)
anker_uit[i] = LEEG;
// ga door alle in vorige ronde gevulde vakken
for (i = 0; i < 256; ++i)
{
next = anker_in[i]; // start van de ketting
while (next != LEEG) // doorloop ketting door char: i
{
zet_record_ptr(next);
if (anker_uit[ch = record[kolom]] == LEEG)
// zet ketting start
anker_uit[ch] = next;
else
// zet verwijzing in laatste record in ketting
// NB. aflegvakken volgens FIFO-principe
ketting[anker_eind_ketting[ch]] = next;
// administreer positie laatste in ketting
anker_eind_ketting[ch] = next;
// maak ketting in actuele record: LEEG
act_rec = next; // save verwijzing
next = ketting[act_rec]; // haal volgende in ketting
ketting[act_rec] = LEEG; // actuele record: laatste in ketting
}
}
}
} // Clapet_sort-end
#endif
// Print tijd en tekst en geef tijd in eenheden van 1/100 sec na middernacht
long prtim(char * tekst)
{
unsigned char
hour,
min,
sec,
hndrd;
// haal tijd op via DOS-call
_asm
{
mov ah,0x2c;
int 0x21;
mov hour,ch;
mov min,cl;
mov sec,dh;
mov hndrd,dl;
}
printf("\n %02d:%02d:%02d.%02d : %s",hour,min,sec,hndrd,tekst);
return 360000 * hour + 6000L * min + 100*sec+hndrd;
} // eind prtim()
unsigned long zrp1; // hulp-veld procedure: zet_record_ptr
// transformeer volgnummer in buffer, in een adres: segment + offset
// NB. bufferadres staat op paragraafadres: offset:0
__inline void * zet_record_ptr(int n)
{
zrp1 = (long) n * Record_Lengte;
*recofs = (unsigned int)(zrp1 & 0x00000fff);
*recseg = (unsigned int)(*bufseg + (unsigned int) ((zrp1 & 0xfffff000) >> 4));
return record;
}