Performancevergleich einer Implementierung des Quicksort-Algorithmus in den Programmiersprachen C++ und Pascal.

#include <iostream>
#include <ctime>
using namespace std;
 
const int n = 45;
 
int reihung[n];
 
void swap(int& a, int& b)
{
 int temp;
 temp = a;
 a    = b;
 b    = temp;
}
 
void ausgeben()
{
 for(int i = 0; i < n; i++)
        cout << reihung[i] << " ";
 cout << endl;
}
 
int qsort(int i, int j)
{
 int L, R;
 int pivot;
 
 if (i < j)
 {
        L     = i;
        R     = j;
        pivot = i;
 
        while(i < j)
        {
                while(reihung[i] < reihung[pivot])
                        i++;
                while(reihung[j] > reihung[pivot])
                        j--;
 
                if (i <= j)
                {
                        swap(reihung[i], reihung[j]);
                        i++;
                        j--;
                }
 
        } /* while */
        ausgeben();
        qsort(L, j);
        qsort(i, R);
 } /* if */
}
 
int main()
{
 cout << "Quicksort" << endl << endl;
 
 srand ( time(NULL) ); /* Zufallsgenerator initialisieren */
 for(int i = 0; i < n; i++)
        reihung[i] = rand()%100;
 ausgeben();
 cout << endl;
 
 qsort(0, n-1);
 
 cout << endl;
 ausgeben();
 
 return 0;
}

Program qsort;
USES Crt;
 
CONST n = 45;
 
VAR Reihung : ARRAY [1..n] OF INTEGER;
    i       : INTEGER;
 
Procedure swap(VAR a, b : INTEGER);
VAR temp : INTEGER;
Begin
 temp := a;
 a := b;
 b := temp;
End;
 
Procedure ausgeben;
VAR i : INTEGER;
Begin
 FOR i := 1 TO n DO
  Write(Reihung[i], ' ');
 WriteLn;
End;
 
Procedure Qsort(i, j : INTEGER);
VAR pivo : INTEGER;
    R, L : INTEGER;
Begin
 
 if (i < j) THEN
 Begin
  L := i;
  R := j;
  pivo := i;
  WHILE (i < j) DO
  Begin
 
   WHILE (Reihung[i] < Reihung[pivo]) DO { von links aus Element > Pivotelement suchen }
    i := i + 1;
   WHILE (Reihung[j] > Reihung[pivo]) DO { von rechts aus Element < Pivotelement suchen }
    j := j - 1;
 
   IF (i <= j) THEN                      { falls Elemente bei der Suche das Pivotelement }
   Begin                                 { nicht übersprungen haben }
      swap(Reihung[i], Reihung[j]);      { werden sie vertauscht }
      i := i + 1;                        { und Zeiger um 1 verschoben }
      j := j - 1;
   End;
 
  End; {while}                           { alles links von Pivotelement ist jetzt }
  ausgeben;                              { kleiner als alles rechts von ihm }
  Qsort(L, j);                           { -> linke Seite sortieren }
  Qsort(i, R);                           { -> rechte Seite sortieren }
 End; {if}
End;
 
Begin
 ClrScr;
 TEXTCOLOR(white);
 
 WriteLn('Quicksort');
 WriteLn;
 
 randomize;     { Zufallsgenerator initialisieren }
 FOR i := 1 TO n DO
  Reihung[i] := random(100);
 
 ausgeben;
 WriteLn;
 
 Qsort(1, n);
 
 WriteLn;
 ausgeben;
End.

Anmerkung: Es wurde darauf geachtet, den Code bei beiden Programmiersprachen so ähnlich wie möglich zu gestalten. Darum wurde bei C++ bewusst auf OOP verzichtet.

Anmerkung: Die hier aufgeführten Geschwindigkeiten sind natürlich nur Näherungswerte.

Dies ist ein Beispiel einer möglichen Ausgabe. Anfangs wird ein 45-stelliges Feld durch einen Zufallsgenerator generiert und anschließend ausgegeben. Danach erfolgt das sortieren, wie man an den aufgeführten Zwischenschritten erkennen kann. Am Ende ist das fertig sortierte Feld sichtbar.

Quicksort

64 88 89 80 55 99 42 46 41 74 63 39 44 24 4 94 35 4 38 92 99 98 60 62 39 57 2 98 39 32 10 3 72 99 36 80 50 30 26 44 57 41 83 1 17 

17 1 3 10 2 4 4 46 41 74 63 39 44 24 42 94 35 99 38 92 99 98 60 62 39 57 55 98 39 32 80 89 72 99 36 80 50 30 26 44 57 41 83 88 64 
4 1 3 4 2 10 17 46 41 74 63 39 44 24 42 94 35 99 38 92 99 98 60 62 39 57 55 98 39 32 80 89 72 99 36 80 50 30 26 44 57 41 83 88 64 
2 1 3 4 4 10 17 46 41 74 63 39 44 24 42 94 35 99 38 92 99 98 60 62 39 57 55 98 39 32 80 89 72 99 36 80 50 30 26 44 57 41 83 88 64 
1 2 3 4 4 10 17 41 26 30 36 39 32 24 39 39 35 38 99 92 99 98 60 62 94 57 55 98 42 44 80 89 72 99 63 80 50 74 41 44 57 46 83 88 64 
1 2 3 4 4 10 17 38 26 30 36 35 32 24 39 39 39 41 99 92 99 98 60 62 94 57 55 98 42 44 80 89 72 99 63 80 50 74 41 44 57 46 83 88 64 
1 2 3 4 4 10 17 24 26 30 32 35 36 38 39 39 39 41 64 46 57 44 60 62 41 57 55 50 42 44 63 89 72 99 80 80 98 74 94 98 99 92 83 88 99 
1 2 3 4 4 10 17 24 26 30 32 35 36 38 39 39 39 41 63 46 57 44 60 62 41 57 55 50 42 44 64 89 72 99 80 80 98 74 94 98 99 92 83 88 99 
1 2 3 4 4 10 17 24 26 30 32 35 36 38 39 39 39 41 44 42 41 44 60 62 57 57 55 50 46 63 64 89 72 99 80 80 98 74 94 98 99 92 83 88 99 
1 2 3 4 4 10 17 24 26 30 32 35 36 38 39 39 39 41 41 42 44 44 60 62 57 57 55 50 46 63 64 89 72 99 80 80 98 74 94 98 99 92 83 88 99 
1 2 3 4 4 10 17 24 26 30 32 35 36 38 39 39 39 41 41 42 44 44 46 50 55 57 57 60 62 63 64 88 72 83 80 80 74 98 94 98 99 92 99 89 99 
1 2 3 4 4 10 17 24 26 30 32 35 36 38 39 39 39 41 41 42 44 44 46 50 55 57 57 60 62 63 64 74 72 83 80 80 88 98 94 98 99 92 99 89 99 
1 2 3 4 4 10 17 24 26 30 32 35 36 38 39 39 39 41 41 42 44 44 46 50 55 57 57 60 62 63 64 72 74 83 80 80 88 98 94 98 99 92 99 89 99 
1 2 3 4 4 10 17 24 26 30 32 35 36 38 39 39 39 41 41 42 44 44 46 50 55 57 57 60 62 63 64 72 74 80 80 83 88 89 92 94 98 98 99 99 99 

1 2 3 4 4 10 17 24 26 30 32 35 36 38 39 39 39 41 41 42 44 44 46 50 55 57 57 60 62 63 64 72 74 80 80 83 88 89 92 94 98 98 99 99 99 

Anmerkung: Die Ausgabe wurde gekürzt, da es durch Rekursion zu einer mehrfachen Ausgabe des Feldes mit dem gleichen Inhalt kommt. Aus diesem Grund kann auch nicht jeder Einzelschritt ausgegeben werden.

Performancevergleich von Implementierungen einer verketteten Liste in den Programmiersprachen C++ und Pascal.

Es wird eine dynamische Datenstruktur (Liste) mit 30 000 Elementen angelegt, denen per Zufallsgenerator ein Wert zugewiesen wird. Dabei wird die Zeit gemessen, die zum Anlegen der Elemente und Zuweisen der Werte benötigt wird.

#include <iostream>
#include <ctime>
using namespace std;
 
const int n = 30*1000;
 
int main()
{
 struct Zeiger
 {
        int Daten;
        Zeiger *next;
 };
 
 cout << "verkettete Liste" << endl << endl;
 
 srand ( time(NULL) ); /* Zufallsgenerator initialisieren */
 
 Zeiger *Element = new Zeiger;
 Zeiger *Anfang  = new Zeiger;
 
 Anfang->next = NULL;
 Element = Anfang;
 
 for(int i = 0; i < n; i++)
 {
        Zeiger *Neu = new Zeiger;
        Element->next = Neu;
        Neu->next = NULL;
        Element = Neu;
 
        Neu->Daten = rand()%100;
 }
 
 /*Element = Anfang;
 while(Element->next != NULL)
 {
        Element = Element->next;
        cout << Element->Daten << endl;
 }*/
 
 return 0;
}

Program List;
USES Crt;
 
CONST n = 30*1000;
 
TYPE Zeiger = ^Liste;
 
     Liste = RECORD
                Daten : INTEGER;
                Next : Zeiger;
             End;
 
VAR Anfang, Element, Neu : Zeiger;
    i            : INTEGER;
 
Begin
 ClrScr;
 TEXTCOLOR(white);
 
 randomize; { Zufallsgenerator initialisieren }
 
 WriteLn('verkettete Liste');
 WriteLn;
 
 NEW (Anfang);
 Anfang^.next := NIL;
 Element := Anfang;
 
 FOR i := 0 TO n DO
 Begin
        NEW (Neu);              { neues Element erzeugen }
        Element^.next := Neu;   { Nachfolger vom aktuellen Element wird das Neue }
        Neu^.next := NIL;       { Nachfolger vom neuen Element wird NIL }
        Element := Neu;         { neues Element ist nun aktuelles Element }
 
        Neu^.Daten := random(100);
 End;
 
 {Element := Anfang;
 WHILE (Element <> NIL) DO
 Begin
        WriteLn(Element^.Daten);
        Element := Element^.next;
 End;}
 
End.

Anmerkung: Der Code zum Ausgeben der Listeninhalte wurde bewusst auskommentiert, da die Programmausgabe einen wesentlichen Teil der Gesamtzeit in Anspruch nimmt und das Ergebnis dadurch u.U. verfälschen kann.
Zusätzlich mussten die Elemente der Liste auf 30 000 begrenzt werden, da man in Pascal anscheinend keine größeren Konstanten definieren kann (geplant waren ursprünglich mehrere Millionen Elemente, was sich in C++ auch problemlos umsetzen ließ). Eine größere Anzahl an Elementen hätte zu einer genaueren Zeitmessung geführt, da sich die Ablaufdauer der Programme im Bereich von wenigen Millisekunden bewegen.

Anmerkung: Die hier aufgeführten Geschwindigkeiten sind natürlich nur Näherungswerte.

Performancevergleich von Implementierungen einer binären Suche in den Programmiersprachen C++ und Pascal.

#include <iostream>
using namespace std;
 
const int n = 32767;
 
int Reihung[n];
 
void fill()
{
 for(int i = 1; i <= n; i++)
        Reihung[i] = i;
}
 
bool bsearch(int L, int R, int Key)
{
 if (L > R)
 {
        cout << "Der Suchschlüssel " << Key
             << " ist nicht enthalten." << endl;
        return false;
 }
 else
 {
        int center = (L + R) / 2;
 
        if      (Key > Reihung[center])  
                bsearch(center+1, R, Key);
        else if (Key < Reihung[center])
                bsearch(L, center-1, Key);
        else
        {
                cout << "Der Suchschlüssel " << Key
                     << " ist an Stelle " << center
                     << " zu finden." << endl;
                return true;
        }
 }
}
 
int main()
{
 cout << "binäre Suche" << endl;
 
 fill();
 bsearch(1, n, 1);
 
 return 0;
}

Program bin_search;
USES Crt;
 
CONST n = 32767;
 
VAR Reihung : ARRAY [1..n] OF INTEGER;
 
Procedure fill;
VAR i : INTEGER;
Begin
 FOR i := 1 TO n DO
        Reihung[i] := i;
End;
 
Function bsearch(L, R, Key : INTEGER) : BOOLEAN;
VAR center : INTEGER;
Begin
 IF (L > R) THEN
 Begin
        bsearch := false;
        WriteLn('Der Suchschlüssel ', Key,
                ' ist nicht enthalten.');
 End
 ELSE
 Begin
        center := (L+R) DIV 2;
 
        IF      (Key > Reihung[center]) THEN
                bsearch := bsearch(center+1, R, Key)
        ELSE IF (Key < Reihung[center]) THEN
                bsearch := bsearch(L, center-1, Key)
        ELSE
        Begin
                bsearch := true;
                WriteLn('Der Suchschlüssel ', Key,
                        ' ist an Stelle ', center,
                        ' zu finden.');
        End;
 End;
End;
 
Begin
 ClrScr;
 TEXTCOLOR(white);
 
 WriteLn('binäre Suche');
 WriteLn;
 
 fill;
 bsearch(1, n, 1);
End.

Anmerkung: Zur fairen Ermittlung der Ablaufdauer werden die Feldinhalte und Suchschlüssel nicht zufällig ermittelt, sondern sind bereits im Code definiert.
Zusätzlich mussten die Elemente der Felder auf 32 767 begrenzt werden, da man in Pascal anscheinend keine größeren Konstanten definieren kann (was in C++ problemlos möglich ist). Eine größere Anzahl an Elementen hätte zu einer genaueren Zeitmessung geführt, da sich die Ablaufdauer der Programme im Bereich von wenigen Millisekunden bewegen.

Anmerkung: Die hier aufgeführten Geschwindigkeiten sind natürlich nur Näherungswerte.