C!T ROM 2/ctrom_ii_b.zip/ctrom_ii_b/C!T/C!T05_93/CLAPET/CLAPET.C

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;
}