\documentclass[a4paper]{article}

\usepackage[utf8]{inputenc}
\usepackage[ngerman]{babel}

\usepackage{graphicx}

\title{VP WAP: Aufgabe 3\\Mathematica}
\author{Siegmar Alber\\0720046}
\date{28.01.2009}

\begin{document}
\maketitle
\tableofcontents

\section{Aufgabenstellung}
\begin{enumerate}
\item Programmieraufgabe Mathematica:
\begin{enumerate}
\item Eine Liste von Zufallszahlen erzeugen.
\item Sortierfunktionen implementieren:
\begin{enumerate}
\item Quicksort
\item Heapsort
\item Bubblesort
\end{enumerate}
\item Geschwindigkeiten der einzelnen Sortierverfahren mit verschiedenen Listenlängen messen.
\item Gemessene Geschwindigkeiten exportieren.
\end{enumerate}
\item Ergebnisse mit gnuplot darstellen.
\item Grafiken in \LaTeX einbinden.
\item \LaTeX-Dokument und Mathematica-Quelltext ausdrucken und abgeben.
\end{enumerate}

\section{Mathematica-Quelltext}
\subsection{Quicksort}
\begin{verbatim}
quicksort[liste_] := Module[{list = liste, swap, teile, qsort},
  
  swap[p1_, p2_] := Module[{temp},
    temp = list[[p1]];
    list[[p1]] = list[[p2]];
    list[[p2]] = temp;
    ];
  
  teile[links_, rechts_] := Module[{aaa, i, j, pivot},
    i = links;
    j = rechts - 1;
    pivot = list[[rechts]];
    
    aaa := (
      While[list[[i]] <= pivot && i < rechts,
       i++
       ];
      While[list[[j]] >= pivot && j > links,
       j--
       ];
      
      If[i < j,
       swap[i, j];
       ];
      );
    
    aaa[];
    While[i < j, aaa[];];
    
    If[list[[i]] > pivot,
     swap[i, rechts];
     ];
    
    i
    ];
  
  
  qsort[links_, rechts_] := Module[{teiler},
    If[links < rechts,
      teiler = teile[links, rechts];
      qsort[links, teiler - 1];
      qsort[teiler + 1, rechts]];
    ];
  
  qsort[1, Length[list]];
  list
  ]
\end{verbatim}

\subsection{Heapsort}
\begin{verbatim}
heapsort[liste_] := Module[{list = liste, swap, blub, macheHeap, sortiere},
  
  swap[p1_, p2_] := Module[{temp},
    temp = list[[p1]];
    list[[p1]] = list[[p2]];
    list[[p2]] = temp;
    ];
  
  blub[position_, länge_] := 
   Module[{kindLinks, kindRechts, kind, pos = position, laenge = länge},
    While[pos <= Floor[laenge/2], (
      kindLinks = pos*2;
      kindRechts = kindLinks + 1;
      
      kind = kindLinks;
      If[kindRechts <= laenge && list[[kindRechts]] > list[[kindLinks]], 
       kind = kindRechts];
      
      If[list[[pos]] < list[[kind]], (
        swap[pos, kind];
        pos = kind;
        ),
       Goto[fertig];
       ];
      )];
    Label[fertig];
    ];
  
  macheHeap[] := Module[{i},
    For[i = Floor[Length[list]/2], i >= 1, i--,
     blub[i, Length[list]];
     ]
    ];
  
  sortiere[] := Module[{i},
    For[i = Length[list], i > 1, i--,
      swap[i, 1];
      blub[1, i - 1];
      ];
    ];
  
  macheHeap[];
  sortiere[];
  list
  ]
\end{verbatim}

\subsection{Bubblesort}
\begin{verbatim}
bubblesort[liste_] := Module[{list = liste, body, vertauscht, n, swap},
   
   swap[p1_, p2_] := Module[{temp},
     temp = list[[p1]];
     list[[p1]] = list[[p2]];
     list[[p2]] = temp;
     ];
   
   body[] := Module[{i},
     vertauscht = False;
     For[i = 1, i <= n - 1, i++,
      If[list[[i]] > list[[i + 1]],
        swap[i, i + 1];
        vertauscht = True;
        ];
      ];
     n--;
     ];
   
   n = Length[list];
   body[];
   While[vertauscht && n >= 1, body[]];
   list
   ];
\end{verbatim}

\subsection{Main}
\subsubsection{Zufällige Liste}
\begin{verbatim}
Module[{laenge, quicksorttime, bubblesorttime, mathematicatime, heapsorttime, 
  x, file},
 file = OpenWrite["random.dat"];
 For[laenge = 100, laenge <= 1000, laenge += 100, (
   x = RandomInteger[1000000, laenge];
   heapsorttime = Timing[heapsort[x]][[1]];
   quicksorttime = Timing[quicksort[x]][[1]];
   bubblesorttime = Timing[bubblesort[x]][[1]];
   mathematicatime = Timing[Sort[x]][[1]];
   Print[laenge, "\t", quicksorttime, "\t", heapsorttime, "\t", 
    bubblesorttime, "\t", mathematicatime];
   Write[file, 
    OutputForm[{laenge/100, laenge, quicksorttime, heapsorttime, 
      bubblesorttime, mathematicatime}]];
   )];
 Close[file];
 ]

100	0.010368	0.025227	0.068933	0.000036
200	0.022529	0.054173	0.27489	0.000039
300	0.036467	0.117312	0.664839	0.000058
400	0.052316	0.125926	1.13873	0.000073
500	0.062243	0.150897	1.75322	0.000089
600	0.076757	0.19177	2.65083	0.000116
700	0.092454	0.22541	3.53807	0.000126
800	0.107352	0.26148	4.73844	0.000174
900	0.122115	0.296943	5.64427	0.000196
1000	0.133494	0.331511	7.07948	0.000213
\end{verbatim}

\subsubsection{Aufsteigend sortierte Liste}
\begin{verbatim}
$RecursionLimit = Infinity; $IterationLimit = Infinity;

Module[{laenge, quicksorttime, bubblesorttime, mathematicatime, heapsorttime, 
  x, file},
 file = OpenWrite["asc.dat"];
 For[laenge = 100, laenge <= 1000, laenge += 100, (
   x = Sort[RandomInteger[1000000, laenge]];
   heapsorttime = Timing[heapsort[x]][[1]];
   quicksorttime = Timing[quicksort[x]][[1]];
   bubblesorttime = Timing[bubblesort[x]][[1]];
   mathematicatime = Timing[Sort[x]][[1]];
   Print[laenge, "\t", quicksorttime, "\t", heapsorttime, "\t", 
    bubblesorttime, "\t", mathematicatime];
   Write[file, 
    OutputForm[{laenge/100, laenge, quicksorttime, heapsorttime, 
      bubblesorttime, mathematicatime}]];
   )];
 Close[file];
 ]

100	0.025928	0.028127	0.000644	0.000017
200	0.082041	0.057791	0.001141	0.000027
300	0.171199	0.09024	0.001644	0.000036
400	0.292233	0.125433	0.002263	0.000048
500	0.448394	0.161051	0.002778	0.000056
600	0.630507	0.200557	0.003259	0.000099
700	0.871571	0.241028	0.003861	0.000105
800	1.11449	0.284192	0.004394	0.000124
900	1.38033	0.314423	0.00486	0.000128
1000	1.70624	0.356286	0.005542	0.000127
\end{verbatim}

\subsubsection{Absteigend sortierte Liste}
\begin{verbatim}
Module[{laenge, quicksorttime, bubblesorttime, mathematicatime, heapsorttime, 
  x, file},
 file = OpenWrite["dsc.dat"];
 For[laenge = 100, laenge <= 1000, laenge += 100, (
   x = Sort[RandomInteger[1000000, laenge], (#1 > #2) &];
   heapsorttime = Timing[heapsort[x]][[1]];
   quicksorttime = Timing[quicksort[x]][[1]];
   bubblesorttime = Timing[bubblesort[x]][[1]];
   mathematicatime = Timing[Sort[x]][[1]];
   Print[laenge, "\t", quicksorttime, "\t", heapsorttime, "\t", 
    bubblesorttime, "\t", mathematicatime];
   Write[file, 
    OutputForm[{laenge/100, laenge, quicksorttime, heapsorttime, 
      bubblesorttime, mathematicatime}]];
   )];
 Close[file];
 ]

100	0.022669	0.020347	0.103164	0.000031
200	0.075599	0.04615	0.409731	0.000033
300	0.158146	0.074343	0.920926	0.000047
400	0.268661	0.101783	1.65807	0.000059
500	0.411633	0.13413	2.56831	0.000066
600	0.576772	0.161089	3.67872	0.000091
700	0.783641	0.193751	5.04629	0.000129
800	1.03289	0.23001	6.6132	0.000112
900	1.29986	0.260036	8.38182	0.000122
1000	1.55788	0.289618	10.3344	0.000144
\end{verbatim}

\section{Grafiken}
\subsection{Zufällige Liste}
\includegraphics[width=12cm]{../diagramme/random.eps}

\subsection{Aufsteigend sortierte Liste}
\includegraphics[width=12cm]{../diagramme/asc.eps}

\subsection{Absteigend sortierte Liste}
\includegraphics[width=12cm]{../diagramme/dsc.eps}

\end{document}

