Hier werden verschiedene Sortierverfahren auf ihr Laufzeit untersucht, das bei unsortierten Feldern, mit der 3-Median-Killer-Sequenz und bei sortierten Feldern.
Hier eine Beispielausgabe die ich auf eine alten Laptop gemacht habe und Ubuntu 10.04 lief im VMware Player:
Jeweils 10 Durchgänge CPU-Zeiten in sec für unsortierte Daten | n = 10 000 | n = 20 000 | n = 30 000 | n = 40 000 ---------------------------------------------------------------------------------------- insertionSort | 0.368 | 1.46 | 3.512 | 5.629 ---------------------------------------------------------------------------------------- quickSort | 0.002 | 0.01 | 0.013 | 0.013 ---------------------------------------------------------------------------------------- quickSort3Median | 0.005 | 0.007 | 0.012 | 0.015 ---------------------------------------------------------------------------------------- introSpectiveQuickSort | 0.005 | 0.009 | 0.015 | 0.022 CPU-Zeiten in sec für sortierte Daten | n = 10 000 | n = 20 000 | n = 30 000 | n = 40 000 ---------------------------------------------------------------------------------------- quickSort | 0.428 | 1.579 | 4.091 | 6.272 ---------------------------------------------------------------------------------------- quickSort3Median | 0.001 | 0.005 | 0.007 | 0.011 ---------------------------------------------------------------------------------------- introSpectiveQuickSort | 0.005 | 0.009 | 0.017 | 0.02 CPU-Zeiten in sec für 3-Median-Killer-Sequenzen | n = 10 000 | n = 20 000 | n = 30 000 | n = 40 000 ---------------------------------------------------------------------------------------- quickSort | 0.039 | 0.149 | 0.337 | 1.072 ---------------------------------------------------------------------------------------- quickSort3Median | 0.211 | 0.873 | 1.871 | 3.118 ---------------------------------------------------------------------------------------- introSpectiveQuickSort | 0.003 | 0.009 | 0.015 | 0.018 Programmlaufzeit: 7 Minuten 13 Sekunden
Programmiertechnik 2 – Aufgabe 5 (Sortierverfahren)
Lösung:
main.cpp:
// Aufgabe 5
//
// Autor: Andreas Giemza
// Datum: 8.06.2010
#include <iostream>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
// sortiert das Feld a[] mit n Elementen, indem es a[1] bis a[n-1] a die richtige Stelle einfuegt
void insertionSort (int a[], int n)
{
for(int i = 1; i < n; ++i)
{
int t = a[i];
int j = i-1;
while ( j >= 0 && a[j] > t )
{
a[j+1] = a[j];
--j;
}
a[j+1] = t;
}
}
// waehlt ein Pivotelement a[re], sortiert alle Elemente < Pivo links > Pivo rechts und liefert Index des Pivotelements zurueck
int partition (int a[], int li, int re)
{
int pivo = a[re]; // Pivotelement
int i = li-1;
int j = re;
while (1)
{
do ++i; while( a[i] < pivo ); // 1. Element grö�er als Pivotelement suchen
do --j; while( a[j] > pivo ); // 1. Element kleiner als Pivotelement suchen
if ( i >= j ) break;
int t = a[i]; // diese Elemente vertauschen
a[i] = a[j];
a[j] = t;
}
a[re] = a[i]; // Pivotelement mit a[i] vertauschen
a[i] = pivo;
return i;
}
// sortiert Feldelemente von a[] ab dem Index li bis Index re mit dem Teile- und Herrscheverfahren
void quickSort (int a[], int li, int re)
{
if (re > li)
{
int i = partition (a, li, re); // Teileschritt
quickSort (a, li, i-1); // Herrscheschritt
quickSort (a, i+1, re);
}
}
// waehlt ein Pivotelement, sortiert alle Elemente < Pivo links > Pivo rechts und liefert Index des Pivotelements zurueck
// Pivotelement ist der Median (mittlere Wert) von a[li], a[(li+re)/2], a[re]
int partition_median (int a[], int li, int re)
{
// falls das linke Randelement der Median ist
if( a[li] > a[(li+re)/2] && a[li] < a[re] || a[li] < a[(li+re)/2] && a[li] > a[re] )
{
int median = a[li]; // rechtes Randelement mit Median vertauschen
a[li] = a[re];
a[re] = median;
}
// falls das mittlere Element der Median ist
else if( a[(li+re)/2] > a[li] && a[(li+re)/2] < a[re] || a[(li+re)/2] < a[li] && a[(li+re)/2] > a[re] )
{
int median = a[(li+re)/2]; // rechtes Randelement mit Median vertauschen
a[(li+re)/2] = a[re];
a[re] = median;
}
int pivo = a[re]; // Pivotelement
int i = li-1;
int j = re;
while (1)
{
do ++i; while( a[i] < pivo ); // 1. Element grö�er als Pivotelement suchen
do --j; while( a[j] > pivo ); // 1. Element kleiner als Pivotelement suchen
if ( i >= j ) break;
int t = a[i]; // diese Elemente vertauschen
a[i] = a[j];
a[j] = t;
}
a[re] = a[i]; // Pivotelement mit a[i] vertauschen
a[i] = pivo;
return i;
}
// sortiert Feldelemente von a[] ab dem Index li bis Index re mit dem Teile- und Herrscheverfahren
void quickSort3M( int a[], int li, int re )
{
if ( re > li ) // Feld enthält mehr als 1 Element
{
int i = partition_median( a, li, re ); // Teileschritt:
quickSort3M( a, li, i-1 ); // Herrscheschritt:
quickSort3M( a, i+1, re );
}
}
// verschiebt das Element mit Index k des Feldes a[] mit n Elementen im Heap ganz nach unten
// dabei wird das Element immer mit dem groesseren der beiden Kinder vertauscht
void downheap (int a[], int n, int k)
{
int t = a[k];
while (2*k+1 < n) // a[k] hat ein linkes Kind
{
int j = 2*k+1; // a[j] ist linkes Kind von a[k]
if (j+1 < n)
if (a[j+1] > a[j]) j++; // a[j] ist jetzt groesstes Kind
if (t >= a[j]) break;
a[k] = a[j]; // groesstes Kind eine Position nach oben schieben
k = j;
}
a[k] = t;
}
// sortiert ein Feld a[] mit n Elementen mittels eines Heaps
void heapSort (int a[], int n)
{
for (int i = n/2-1; i >= 0; i--) // Feld in Heap umbauen
downheap (a, n, i);
while (n > 1) // Heap hat mehr als 1 Element
{
int t = a[0]; // Heap abbauen und sortiertes Feld aufbauen
a[0] = a[n-1];
a[n-1] = t;
n--;
downheap (a,n,0);
}
}
// introSpektiveQuickSort mit 3Median-Strategie: steigt bei einer Rekursionstiefe von 2*logBasis2(n) auf HeapSort um
void ISquickSort3M (int a[], int li, int re)
{
static int rek = -1; // Rekursions Tiefe
static int g = re - li + 1; // Anzahl der insgesamt zu sortierenden Daten
++rek;
if ( rek >= (2*log(g)/log(2)) ) // wenn Rek Tiefe 2*logBasis2(n) erreicht ->
{
--rek;
heapSort (a, re-li+1); // auf heapSort umsteigen
}
else
{
if ( re > li ) // Feld enthält mehr als 1 Element
{
--rek;
int i = partition_median( a, li, re ); // Teileschritt:
ISquickSort3M( a, li, i-1 ); // Herrscheschritt:
ISquickSort3M( a, i+1, re );
}
}
}
int main(int argc, char *argv[])
{
// Anzahl der Durchgänge
int k = 5;
if (argc > 1)
{
char *endPtr;
k = std::strtol(argv[1], &endPtr, 10);
if (k < 1)
{
std::cout << "Falsche Eingabe (" << k << ")! Bitte einen Wert groesser als 1 eingeben.nAnzahl der Durchgaenge wird auf 5 gesetzt.n";
k = 5;
}
}
else
{
std::cout << "Keine Eingabe! Bitte einen Wert groesser als 1 eingebennAnzahl der Durchgaenge wird auf 5 gesetzt. Beispiel: ./aufg5 100n";
}
// Programmlaufzeit
clock_t progstart = clock();
// insertionSort
// Viele Variabeln
clock_t startInsertionSort10, endInsertionSort10, startInsertionSort20, endInsertionSort20;
clock_t startInsertionSort30, endInsertionSort30, startInsertionSort40, endInsertionSort40;
double summTimeInsertionSort10 = 0, summTimeInsertionSort20 = 0, summTimeInsertionSort30 = 0, summTimeInsertionSort40 = 0;
int feldInsertionSort10[10000], feldInsertionSort20[20000], feldInsertionSort30[30000], feldInsertionSort40[40000];
// Die Durchgänge
for (int j = 0; j < k; ++j)
{
// Felder mit Zufallszahlen füllen
for (int i = 0; i < 10000; ++i)
feldInsertionSort10[i] = rand();
for (int i = 0; i < 20000; ++i)
feldInsertionSort20[i] = rand();
for (int i = 0; i < 30000; ++i)
feldInsertionSort30[i] = rand();
for (int i = 0; i < 40000; ++i)
feldInsertionSort40[i] = rand();
// Zeiten aufzeichnen
startInsertionSort10 = clock();
insertionSort (feldInsertionSort10,10000-1);
endInsertionSort10 = clock();
startInsertionSort20 = clock();
insertionSort (feldInsertionSort20,20000-1);
endInsertionSort20 = clock();
startInsertionSort30 = clock();
insertionSort (feldInsertionSort30,30000-1);
endInsertionSort30 = clock();
startInsertionSort40 = clock();
insertionSort (feldInsertionSort40,40000-1);
endInsertionSort40 = clock();
// Zeiten aufaddieren
summTimeInsertionSort10 += double (endInsertionSort10 - startInsertionSort10)/CLOCKS_PER_SEC;
summTimeInsertionSort20 += double (endInsertionSort20 - startInsertionSort20)/CLOCKS_PER_SEC;
summTimeInsertionSort30 += double (endInsertionSort30 - startInsertionSort30)/CLOCKS_PER_SEC;
summTimeInsertionSort40 += double (endInsertionSort40 - startInsertionSort40)/CLOCKS_PER_SEC;
cout << "insertionSort Durchgang " << j+1 << " fertig!" << endl;
}
// quickSort
// Viele Variabeln
clock_t startQuickSort10, endQuickSort10, startQuickSort20, endQuickSort20;
clock_t startQuickSort30, endQuickSort30, startQuickSort40, endQuickSort40;
double summTimeQuickSort10 = 0, summTimeQuickSort20 = 0, summTimeQuickSort30 = 0, summTimeQuickSort40 = 0;
double ssummTimeQuickSort10 = 0, ssummTimeQuickSort20 = 0, ssummTimeQuickSort30 = 0, ssummTimeQuickSort40 = 0;
double ksummTimeQuickSort10 = 0, ksummTimeQuickSort20 = 0, ksummTimeQuickSort30 = 0, ksummTimeQuickSort40 = 0;
int feldQuickSort10[10000], feldQuickSort20[20000], feldQuickSort30[30000], feldQuickSort40[40000];
// Die Durchgänge
for (int j = 0; j < k; ++j)
{
// Felder mit Zufallszahlen füllen
for (int i = 0; i < 10000; ++i)
feldQuickSort10[i] = rand();
for (int i = 0; i < 20000; ++i)
feldQuickSort20[i] = rand();
for (int i = 0; i < 30000; ++i)
feldQuickSort30[i] = rand();
for (int i = 0; i < 40000; ++i)
feldQuickSort40[i] = rand();
// Unsortiert
// Zeiten aufzeichnen
startQuickSort10 = clock();
quickSort (feldQuickSort10, 0, 10000-1);
endQuickSort10 = clock();
startQuickSort20 = clock();
quickSort (feldQuickSort20, 0, 20000-1);
endQuickSort20 = clock();
startQuickSort30 = clock();
quickSort (feldQuickSort30, 0, 30000-1);
endQuickSort30 = clock();
startQuickSort40 = clock();
quickSort (feldQuickSort40, 0, 40000-1);
endQuickSort40 = clock();
// Zeiten aufaddieren
summTimeQuickSort10 += double (endQuickSort10 - startQuickSort10)/CLOCKS_PER_SEC;
summTimeQuickSort20 += double (endQuickSort20 - startQuickSort20)/CLOCKS_PER_SEC;
summTimeQuickSort30 += double (endQuickSort30 - startQuickSort30)/CLOCKS_PER_SEC;
summTimeQuickSort40 += double (endQuickSort40 - startQuickSort40)/CLOCKS_PER_SEC;
// Sortiert
// Zeiten aufzeichnen
startQuickSort10 = clock();
quickSort (feldQuickSort10, 0, 10000-1);
endQuickSort10 = clock();
startQuickSort20 = clock();
quickSort (feldQuickSort20, 0, 20000-1);
endQuickSort20 = clock();
startQuickSort30 = clock();
quickSort (feldQuickSort30, 0, 30000-1);
endQuickSort30 = clock();
startQuickSort40 = clock();
quickSort (feldQuickSort40, 0, 40000-1);
endQuickSort40 = clock();
// Zeiten "ausrechnen"
ssummTimeQuickSort10 += double (endQuickSort10 - startQuickSort10)/CLOCKS_PER_SEC;
ssummTimeQuickSort20 += double (endQuickSort20 - startQuickSort20)/CLOCKS_PER_SEC;
ssummTimeQuickSort30 += double (endQuickSort30 - startQuickSort30)/CLOCKS_PER_SEC;
ssummTimeQuickSort40 += double (endQuickSort40 - startQuickSort40)/CLOCKS_PER_SEC;
// 3-Median-Killer-Sequenzen
// Null an das Ende packen
feldQuickSort10[10000 - 1] = 0;
feldQuickSort20[20000 - 1] = 0;
feldQuickSort30[30000 - 1] = 0;
feldQuickSort40[40000 - 1] = 0;
// Zeiten aufzeichnen
startQuickSort10 = clock();
quickSort (feldQuickSort10, 0, 10000-1);
endQuickSort10 = clock();
startQuickSort20 = clock();
quickSort (feldQuickSort20, 0, 20000-1);
endQuickSort20 = clock();
startQuickSort30 = clock();
quickSort (feldQuickSort30, 0, 30000-1);
endQuickSort30 = clock();
startQuickSort40 = clock();
quickSort (feldQuickSort40, 0, 40000-1);
endQuickSort40 = clock();
// Zeiten "ausrechnen"
ksummTimeQuickSort10 = double (endQuickSort10 - startQuickSort10)/CLOCKS_PER_SEC;
ksummTimeQuickSort20 = double (endQuickSort20 - startQuickSort20)/CLOCKS_PER_SEC;
ksummTimeQuickSort30 = double (endQuickSort30 - startQuickSort30)/CLOCKS_PER_SEC;
ksummTimeQuickSort40 = double (endQuickSort40 - startQuickSort40)/CLOCKS_PER_SEC;
cout << "quickSort Durchgang " << j+1 << " fertig!" << endl;
}
// quickSort3M
// Viele Variabeln
clock_t startQuickSort3M10, endQuickSort3M10, startQuickSort3M20, endQuickSort3M20;
clock_t startQuickSort3M30, endQuickSort3M30, startQuickSort3M40, endQuickSort3M40;
double summTimeQuickSort3M10 = 0, summTimeQuickSort3M20 = 0, summTimeQuickSort3M30 = 0, summTimeQuickSort3M40 = 0;
double ssummTimeQuickSort3M10 = 0, ssummTimeQuickSort3M20 = 0, ssummTimeQuickSort3M30 = 0, ssummTimeQuickSort3M40 = 0;
double ksummTimeQuickSort3M10 = 0, ksummTimeQuickSort3M20 = 0, ksummTimeQuickSort3M30 = 0, ksummTimeQuickSort3M40 = 0;
int feldQuickSort3M10[10000], feldQuickSort3M20[20000], feldQuickSort3M30[30000], feldQuickSort3M40[40000];
// Die Durchgänge
for (int j = 0; j < k; ++j)
{
// Felder mit Zufallszahlen füllen
for (int i = 0; i < 10000; ++i)
feldQuickSort3M10[i] = rand();
for (int i = 0; i < 20000; ++i)
feldQuickSort3M20[i] = rand();
for (int i = 0; i < 30000; ++i)
feldQuickSort3M30[i] = rand();
for (int i = 0; i < 40000; ++i)
feldQuickSort3M40[i] = rand();
// Unsortiert
// Zeiten aufzeichnen
startQuickSort3M10 = clock();
quickSort3M (feldQuickSort3M10, 0, 10000-1);
endQuickSort3M10 = clock();
startQuickSort3M20 = clock();
quickSort3M (feldQuickSort3M20, 0, 20000-1);
endQuickSort3M20 = clock();
startQuickSort3M30 = clock();
quickSort3M (feldQuickSort3M30, 0, 30000-1);
endQuickSort3M30 = clock();
startQuickSort3M40 = clock();
quickSort3M (feldQuickSort3M40, 0, 40000-1);
endQuickSort3M40 = clock();
// Zeiten aufaddieren
summTimeQuickSort3M10 += double (endQuickSort3M10 - startQuickSort3M10)/CLOCKS_PER_SEC;
summTimeQuickSort3M20 += double (endQuickSort3M20 - startQuickSort3M20)/CLOCKS_PER_SEC;
summTimeQuickSort3M30 += double (endQuickSort3M30 - startQuickSort3M30)/CLOCKS_PER_SEC;
summTimeQuickSort3M40 += double (endQuickSort3M40 - startQuickSort3M40)/CLOCKS_PER_SEC;
// Sortiert
// Zeiten aufzeichnen
startQuickSort3M10 = clock();
quickSort3M (feldQuickSort3M10, 0, 10000-1);
endQuickSort3M10 = clock();
startQuickSort3M20 = clock();
quickSort3M (feldQuickSort3M20, 0, 20000-1);
endQuickSort3M20 = clock();
startQuickSort3M30 = clock();
quickSort3M (feldQuickSort3M30, 0, 30000-1);
endQuickSort3M30 = clock();
startQuickSort3M40 = clock();
quickSort3M (feldQuickSort3M40, 0, 40000-1);
endQuickSort3M40 = clock();
// Zeiten "ausrechnen"
ssummTimeQuickSort3M10 += double (endQuickSort3M10 - startQuickSort3M10)/CLOCKS_PER_SEC;
ssummTimeQuickSort3M20 += double (endQuickSort3M20 - startQuickSort3M20)/CLOCKS_PER_SEC;
ssummTimeQuickSort3M30 += double (endQuickSort3M30 - startQuickSort3M30)/CLOCKS_PER_SEC;
ssummTimeQuickSort3M40 += double (endQuickSort3M40 - startQuickSort3M40)/CLOCKS_PER_SEC;
// 3-Median-Killer-Sequenzen
// Null an das Ende packen
feldQuickSort3M10[10000 - 1] = 0;
feldQuickSort3M20[20000 - 1] = 0;
feldQuickSort3M30[30000 - 1] = 0;
feldQuickSort3M40[40000 - 1] = 0;
// Zeiten aufzeichnen
startQuickSort3M10 = clock();
quickSort3M (feldQuickSort3M10, 0, 10000-1);
endQuickSort3M10 = clock();
startQuickSort3M20 = clock();
quickSort3M (feldQuickSort3M20, 0, 20000-1);
endQuickSort3M20 = clock();
startQuickSort3M30 = clock();
quickSort3M (feldQuickSort3M30, 0, 30000-1);
endQuickSort3M30 = clock();
startQuickSort3M40 = clock();
quickSort3M (feldQuickSort3M40, 0, 40000-1);
endQuickSort3M40 = clock();
// Zeiten "ausrechnen"
ksummTimeQuickSort3M10 += double (endQuickSort3M10 - startQuickSort3M10)/CLOCKS_PER_SEC;
ksummTimeQuickSort3M20 += double (endQuickSort3M20 - startQuickSort3M20)/CLOCKS_PER_SEC;
ksummTimeQuickSort3M30 += double (endQuickSort3M30 - startQuickSort3M30)/CLOCKS_PER_SEC;
ksummTimeQuickSort3M40 += double (endQuickSort3M40 - startQuickSort3M40)/CLOCKS_PER_SEC;
cout << "quickSort3M Durchgang " << j+1 << " fertig!" << endl;
}
// ISquickSort3M
// Viele Variabeln
clock_t startISquickSort3M10, endISquickSort3M10, startISquickSort3M20, endISquickSort3M20;
clock_t startISquickSort3M30, endISquickSort3M30, startISquickSort3M40, endISquickSort3M40;
double summTimeISquickSort3M10 = 0, summTimeISquickSort3M20 = 0, summTimeISquickSort3M30 = 0, summTimeISquickSort3M40 = 0;
double ssummTimeISquickSort3M10 = 0, ssummTimeISquickSort3M20 = 0, ssummTimeISquickSort3M30 = 0, ssummTimeISquickSort3M40 = 0;
double ksummTimeISquickSort3M10 = 0, ksummTimeISquickSort3M20 = 0, ksummTimeISquickSort3M30 = 0, ksummTimeISquickSort3M40 = 0;
int feldISquickSort3M10[10000], feldISquickSort3M20[20000], feldISquickSort3M30[30000], feldISquickSort3M40[40000];
// Die Durchgänge
for (int j = 0; j < k; ++j)
{
// Felder mit Zufallszahlen füllen
for (int i = 0; i < 10000; ++i)
feldISquickSort3M10[i] = rand();
for (int i = 0; i < 20000; ++i)
feldISquickSort3M20[i] = rand();
for (int i = 0; i < 30000; ++i)
feldISquickSort3M30[i] = rand();
for (int i = 0; i < 40000; ++i)
feldISquickSort3M40[i] = rand();
// Unsortiert
// Zeiten aufzeichnen
startISquickSort3M10 = clock();
ISquickSort3M (feldISquickSort3M10, 0, 10000-1);
endISquickSort3M10 = clock();
startISquickSort3M20 = clock();
ISquickSort3M (feldISquickSort3M20, 0, 20000-1);
endISquickSort3M20 = clock();
startISquickSort3M30 = clock();
ISquickSort3M (feldISquickSort3M30, 0, 30000-1);
endISquickSort3M30 = clock();
startISquickSort3M40 = clock();
ISquickSort3M (feldISquickSort3M40, 0, 40000-1);
endISquickSort3M40 = clock();
// Zeiten aufaddieren
summTimeISquickSort3M10 += double (endISquickSort3M10 - startISquickSort3M10)/CLOCKS_PER_SEC;
summTimeISquickSort3M20 += double (endISquickSort3M20 - startISquickSort3M20)/CLOCKS_PER_SEC;
summTimeISquickSort3M30 += double (endISquickSort3M30 - startISquickSort3M30)/CLOCKS_PER_SEC;
summTimeISquickSort3M40 += double (endISquickSort3M40 - startISquickSort3M40)/CLOCKS_PER_SEC;
// Sortiert
// Zeiten aufzeichnen
startISquickSort3M10 = clock();
ISquickSort3M (feldISquickSort3M10, 0, 10000-1);
endISquickSort3M10 = clock();
startISquickSort3M20 = clock();
ISquickSort3M (feldISquickSort3M20, 0, 20000-1);
endISquickSort3M20 = clock();
startISquickSort3M30 = clock();
ISquickSort3M (feldISquickSort3M30, 0, 30000-1);
endISquickSort3M30 = clock();
startISquickSort3M40 = clock();
ISquickSort3M (feldISquickSort3M40, 0, 40000-1);
endISquickSort3M40 = clock();
// Zeiten aufaddieren
ssummTimeISquickSort3M10 += double (endISquickSort3M10 - startISquickSort3M10)/CLOCKS_PER_SEC;
ssummTimeISquickSort3M20 += double (endISquickSort3M20 - startISquickSort3M20)/CLOCKS_PER_SEC;
ssummTimeISquickSort3M30 += double (endISquickSort3M30 - startISquickSort3M30)/CLOCKS_PER_SEC;
ssummTimeISquickSort3M40 += double (endISquickSort3M40 - startISquickSort3M40)/CLOCKS_PER_SEC;
// 3-Median-Killer-Sequenzen
// Null an das Ende packen
feldISquickSort3M10[10000 - 1] = 0;
feldISquickSort3M20[20000 - 1] = 0;
feldISquickSort3M30[30000 - 1] = 0;
feldISquickSort3M40[40000 - 1] = 0;
// Zeiten aufzeichnen
startISquickSort3M10 = clock();
ISquickSort3M (feldISquickSort3M10, 0, 10000-1);
endISquickSort3M10 = clock();
startISquickSort3M20 = clock();
ISquickSort3M (feldISquickSort3M20, 0, 20000-1);
endISquickSort3M20 = clock();
startISquickSort3M30 = clock();
ISquickSort3M (feldISquickSort3M30, 0, 30000-1);
endISquickSort3M30 = clock();
startISquickSort3M40 = clock();
ISquickSort3M (feldISquickSort3M40, 0, 40000-1);
endISquickSort3M40 = clock();
// Zeiten aufaddieren
ksummTimeISquickSort3M10 += double (endISquickSort3M10 - startISquickSort3M10)/CLOCKS_PER_SEC;
ksummTimeISquickSort3M20 += double (endISquickSort3M20 - startISquickSort3M20)/CLOCKS_PER_SEC;
ksummTimeISquickSort3M30 += double (endISquickSort3M30 - startISquickSort3M30)/CLOCKS_PER_SEC;
ksummTimeISquickSort3M40 += double (endISquickSort3M40 - startISquickSort3M40)/CLOCKS_PER_SEC;
cout << "ISquickSort3M Durchgang " << j+1 << " fertig!" << endl;
}
cout << endl << "Jeweils " << k << " Durchgänge" << endl;
cout << endl << "CPU-Zeiten in sec für unsortierte Daten" << endl;
cout << "ttt| n = 10 000t| n = 20 000t| n = 30 000t| n = 40 000" << endl;
cout << "----------------------------------------------------------------------------------------" << endl;
cout << "insertionSorttt| " << summTimeInsertionSort10/k << "tt| " << summTimeInsertionSort20/k << "tt| ";
cout << summTimeInsertionSort30/k << "tt| " << summTimeInsertionSort40/k << endl;
cout << "----------------------------------------------------------------------------------------" << endl;
cout << "quickSorttt| " << summTimeQuickSort10/k << "tt| " << summTimeQuickSort20/k << "tt| ";
cout << summTimeQuickSort30/k << "tt| " << summTimeQuickSort40/k << endl;
cout << "----------------------------------------------------------------------------------------" << endl;
cout << "quickSort3Mediant| " << summTimeQuickSort3M10/k << "tt| " << summTimeQuickSort3M20/k << "tt| ";
cout << summTimeQuickSort3M30/k << "tt| " << summTimeQuickSort3M40/k << endl;
cout << "----------------------------------------------------------------------------------------" << endl;
cout << "introSpectiveQuickSortt| " << summTimeISquickSort3M10/k << "tt| " << summTimeISquickSort3M20/k << "tt| ";
cout << summTimeISquickSort3M30/k << "tt| " << summTimeISquickSort3M40/k << endl;
cout << endl << "CPU-Zeiten in sec für sortierte Daten" << endl;
cout << "ttt| n = 10 000t| n = 20 000t| n = 30 000t| n = 40 000" << endl;
cout << "----------------------------------------------------------------------------------------" << endl;
cout << "quickSorttt| " << ssummTimeQuickSort10/k << "tt| " << ssummTimeQuickSort20/k << "tt| ";
cout << ssummTimeQuickSort30/k << "tt| " << ssummTimeQuickSort40/k << endl;
cout << "----------------------------------------------------------------------------------------" << endl;
cout << "quickSort3Mediant| " << ssummTimeQuickSort3M10/k << "tt| " << ssummTimeQuickSort3M20/k << "tt| ";
cout << ssummTimeQuickSort3M30/k << "tt| " << ssummTimeQuickSort3M40/k << endl;
cout << "----------------------------------------------------------------------------------------" << endl;
cout << "introSpectiveQuickSortt| " << ssummTimeISquickSort3M10/k << "tt| " << ssummTimeISquickSort3M20/k << "tt| ";
cout << ssummTimeISquickSort3M30/k << "tt| " << ssummTimeISquickSort3M40/k << endl;
cout << endl << "CPU-Zeiten in sec für 3-Median-Killer-Sequenzen" << endl;
cout << "ttt| n = 10 000t| n = 20 000t| n = 30 000t| n = 40 000" << endl;
cout << "----------------------------------------------------------------------------------------" << endl;
cout << "quickSorttt| " << ksummTimeQuickSort10/k << "tt| " << ksummTimeQuickSort20/k << "tt| ";
cout << ksummTimeQuickSort30/k << "tt| " << ksummTimeQuickSort40/k << endl;
cout << "----------------------------------------------------------------------------------------" << endl;
cout << "quickSort3Mediant| " << ksummTimeQuickSort3M10/k << "tt| " << ksummTimeQuickSort3M20/k << "tt| ";
cout << ksummTimeQuickSort3M30/k << "tt| " << ksummTimeQuickSort3M40/k << endl;
cout << "----------------------------------------------------------------------------------------" << endl;
cout << "introSpectiveQuickSortt| " << ksummTimeISquickSort3M10/k << "tt| " << ksummTimeISquickSort3M20/k << "tt| ";
cout << ksummTimeISquickSort3M30/k << "tt| " << ksummTimeISquickSort3M40/k << endl << endl;
clock_t progende = clock();
int progtime = (progende - progstart)/CLOCKS_PER_SEC;
cout << "Programmlaufzeit: " << progtime/60 << " Minuten " << progtime%60 << " Sekunden" << endl << endl;
return 0;
}
makefile:
# Author: Andreas Giemza # Date: 12.09.2007 CC = g++ -g OBJ = main.o BIN = aufg5 $(BIN): $(OBJ) $(CC) -o $(BIN) $(OBJ) main.o: main.cpp set.h $(CC) -c main.cpp