home *** CD-ROM | disk | FTP | other *** search
/ Turbo Toolbox / Turbo_Toolbox.iso / 1991 / 07_08 / review / ada / shellsor.ada < prev    next >
Encoding:
Text File  |  1991-04-18  |  3.2 KB  |  138 lines
  1. // -------------------------------------
  2. //          SHELLSORT.ADA
  3. //   Shellsort Testprogramm in Ada
  4. //   (C) 1991 R. Fischer & TOOLBOX
  5. // -------------------------------------
  6. WITH TEXT_IO; USE TEXT_IO;
  7. WITH CALENDAR; USE CALENDAR;
  8. // bit_ops nur in Meridian Ada
  9. WITH BIT_OPS; USE BIT_OPS; 
  10.  
  11. PROCEDURE shellsor IS // Testprogramm
  12.  
  13. // Ein/Ausgabe von Zeitsprannen
  14. PACKAGE duration_io IS 
  15.    NEW FIXED_IO(DURATION);    
  16. USE duration_io;
  17.  
  18. // iarray = unbegrenztes INTEGER Array
  19. TYPE iarray IS 
  20.   ARRAY(INTEGER RANGE <>) OF INTEGER;
  21.  
  22. startzeit : TIME; // Startzeit des Tests
  23.  
  24. // Der Test wird 'iterationen' Mal 
  25. // durchgeführt
  26. iterationen: LONG_INTEGER := 32;
  27.  
  28. // Es werden bei jedem Durchlauf 
  29. // 'size' Zahlen sortiert
  30. size : CONSTANT INTEGER := 4000;
  31.  
  32. // Definition des Sortierfeldes:
  33. feld : iarray(0..size-1);
  34.  
  35. // Inline-Prozedur zum Vertauschen 
  36. // zweier Variableninhalte
  37. PROCEDURE swap(a : IN OUT INTEGER; 
  38.                b : IN OUT INTEGER)
  39. IS
  40.    BEGIN
  41.       a := a XOR b;
  42.       b := b XOR a;
  43.       a := a XOR b;
  44.    END swap;
  45. PRAGMA INLINE(swap);
  46.  
  47. // Aufsteigend Sortieren des Arrays v
  48. PROCEDURE shellsort( v : IN OUT iarray)
  49. IS 
  50.       gap : INTEGER;
  51.       j   : INTEGER;
  52.    BEGIN
  53.       gap := (v'LAST+1) / 2;
  54.       WHILE gap > 0 LOOP
  55.          FOR i IN gap..v'LAST LOOP
  56.             j := i-gap;
  57.             WHILE (j>=0) AND THEN
  58.                (v(j)>v(j+gap)) LOOP
  59.                swap(v(j),v(j+gap));
  60.                j := j - gap;
  61.             END LOOP;
  62.          END LOOP;
  63.          gap := gap / 2;
  64.       END LOOP;
  65.    END shellsort;
  66.  
  67. // Beginn des "Hauptprogramms"
  68. BEGIN
  69.    startzeit := CLOCK;
  70.    WHILE iterationen > 0 LOOP
  71.       // Feld in inverser Reihenfolge
  72.       // füllen
  73.       FOR i IN feld'RANGE LOOP
  74.          feld(i) := size-i;
  75.       END LOOP;
  76.       // Feld sortieren
  77.       shellsort(feld);
  78.       iterationen := iterationen-1;
  79.    END LOOP;
  80.    // Benötigte Zeit anzeigen
  81.    PUT(CLOCK-startzeit); 
  82.    PUT(" Sekunden"); NEW_LINE;
  83. //--------------------------------------
  84. //     Ende von SHELLSORT.ADA
  85.  
  86.  
  87.  
  88. // -------------------------------------
  89. //          SHELLSORT.CPP
  90. //   Shellsort Testprogramm in C++
  91. //   (C) 1991 R. Fischer & TOOLBOX
  92. // -------------------------------------
  93.  
  94. #include <iostream.h>
  95. #include <time.h>
  96.  
  97. const int size=4000; // Größe des Feldes
  98. static long iterationen=32; //Durchläufe
  99. int feld[size];
  100.  
  101. // Vertauschen der Inhalte von a und b
  102. inline void swap(int& a, int& b)
  103. {  a ^= b; b ^= a; a ^= b; }
  104.  
  105. // Shellsort - v[0] .. v[n-1] werden
  106. // aufsteigend sortiert
  107. // Algorithmus nach:
  108. //   Kernighan/Ritchie,
  109. //   The C Programming Language, 2nd ed.
  110. void shellsort(int* v, int n)
  111. {  int gap, i,j;
  112.    for(gap=n/2; gap>0; gap /= 2)
  113.       for(i = gap; i < n; i++)
  114.          for(
  115.             j = i-gap;
  116.             j>=0 && v[j]>v[j+gap];
  117.             j -= gap
  118.          )
  119.             swap(v[j],v[j+gap]);
  120. }
  121.  
  122. void main(void)
  123. {
  124.    time_t startzeit = clock();
  125.    while(iterationen--)
  126.    {  // Feld initialisieren
  127.       for(int i=0; i<size; i++)
  128.          feld[i] = size-i;
  129.       // Sortieren
  130.       shellsort(feld,size);
  131.    }
  132.    cout << ((clock()-startzeit)/CLK_TCK)
  133.         << "Sekunden\n";
  134. }
  135. END;
  136. //--------------------------------------
  137. //     Ende von SHELLSORT.CPP
  138.