# General ## Ausgeführt von: * Florian Riegler - if19b118 * Sebastian Soldan - if19b167 * Arnold Stelzer - if19b110 ## Getestete Algorithmen: * Bubblesort * Radixsort * Bucketsort # Bubblesort Steckbrief ## Theoretische Komplexität (Time/Space) Bubblesort hat die Laufzeit O(n^2) für Listen der Länge n. Die Platzkomplexität ist O(1), da nur ein einziger zusätzlicher Speicherplatz benötigt wird, nämlich der für die Temp-Variable. ## Beispiel eines Best Case Szenarios Bei einer bereits sortierten Liste muss die Liste nur einmal druchgegangen werden, um festzustellen, dass die Liste bereits sortiert ist. Daher benötigt Bubblesort O(n) Schritte, um eine bereits sortierte Liste zu bearbeiten. Falls die Elemente der Liste bereits nah den Stellen sind, die sie nach der Sortierung bekommen sollen, ist die Laufzeit erheblich besser als O(n^2) ## Beispiel eines Worst Case Szenarios Die umgekehrt sortierte Liste. Hier müssen 1/2 * (n * (n-1)) Vertauschungen durchgeführt werden. ## Mögliche Einschränkungen bei der Anwendbarkeit Bei großen n dauert das sortieren wegen O(n^2) sehr lange. # Radixsort Steckbrief Der Radixsort-Algorithmus sortiert die Daten zuerst nach dem geringwertigste Bit, dann den zweitgeringwertigste Bit und so weiter. Es werden immer alle Werte, bei dem dieses Bit gesetzt ist, an das Ende des Arrays gesetzt. Durch das wiederholte Vorgehen, bis entweder alle Bits des Datentyps oder der größten Zahl durchgegangen wurden, wird sichergestellt, dass am Ende alle Werte korrekt sortiert sind. ## Theoretische Komplexität Die Speicherkomplexität des Radixsort beträgt O(n+k) und doe Zeitkomplexität des Bucketsort beträgt O(l∗(n+k)), wobei l die Anzahl der Ziffern aller Zahlen und k die Anzahl der Werte, die jede Ziffer einnehmen kann. Da l und k Konstanten sind, hat der Radixsort eine Speicher- und Zeitkomplexität von O(n). ## Beispiel Best/Worst Case Szenario Beim Radixsort gibt es keinen Best oder Worst Case, da es sich um einen nicht-vergleichenden Integer-Sortieralsgorithmus handelt und es daher keinen Einfluss auf O macht, in welchem Zustand die Werte vor der Sortierung sind. Desto großer die großt(möglich)e Zahl jedoch ist, desto länger wird der Algorithmus brauchen. ## Mögliche Einschränkungen bei der Anwendbarkeit Grundsätzlich gibt es keine Einschränkungen bei der Anwendung des Radixsorts. Falls negative Nummern vorkommen, muss man jedoch den Algorithmus mitteilen, dass diese kleiner sind als postive Nummern, da diese ansonsten in der invertierten Reihenfolge über der höchsten Nummer stehen würden. # Bucketsort Steckbrief Der Bucketsort-Algorithmus teilt die zu sortierenden Daten grob in verschiedene „Buckets“ ein (Beispiel: Integer 1 bis 99 werden in zehn Buckets von 0-9, 10-19, 20-29, etc.eingeteilt). Anschließend werden die einzelnen Buckets von der anderen Sortieralgorithmen sortiert und zum Schluss wieder zusammengefügt. Der Bucketsort-Algorithmus stellt also so eine Art Vorstufe dar, die einem anderen Algorithmus schneller und effizienter machen soll. Bucketsort ist dabei sehr flexibel, da die Effizienz stark vom verwendeten Sortieralgorithmus für die Buckets, sowie deren Anzahl abhängt. ## Theoretische Komplexität Die Speicherkomplexität des Bucketsorts beträgt O(n+k). Die Zeitkomplexität des Bucketsorts beträgt $$O(n)+\sum_{i=0}^{n-1} l_i \times log(l_i)$$ wobei l<sub>i</sub> die Länge des i-ten Buckets bezeichnet. Average Case Szenario wären gleichverteilte Werte, wobei die Zeitkomplexität dann O(n) beträgt. ## Beispiel Best Case Szenario Im Best Case sind die Elemente gleichverteilt und, bereits sortiert, in gleich große Buckets aufgeteilt. Wenn dann zB der Insertionsort zum Sortieren der Buckets verwendet wird, beträgt die Zeitkomplexität des Bucketsort nur O(n+k) mit n = Anzahl der Elemente und k = Anzahl der Buckets. ## Beispiel Worst Case Szenario Im Worst Case Szenario werden alle Elemente des Ausgangsarrays in einen einzigen Bucket sortiert. Dann nimmt der Bucketsort die Zeitkomplexität des Bucket-Sortieralgorithmus an. Wird Bubblesort für das Sortieren des Buckets benutzt wäre dann hier der Worst Case eine rückwarts sortierte Liste. ## Mögliche Einschränkungen bei der Anwendbarkeit Es sind keine Einschränkungen bei der Anwendbarkeit spezifisch für Bucketsort bekannt. Da der Algorithmus stark vom gewählten Sortieralgorithmus für die Buckets abhängt, hängen dementsprechend auch Einschränkungen bei der Anwendbarkeit vom gewählten Algorithmus ab. # Gewählte Variationen Bei den Variationen haben wir uns für vier verschiedene Arten von Arrays als Input entschieden, die jeweils einmal mit zufälligen 130968 Werten und einmal mit rückwarts sortierten 130968 Werten befüllt werden. Somit kommen wir insgesamt auf acht verschiedene Ausführungsvariationen. Im Folgenden werden die einzelnen Arten von Arrays beschrieben: ## NormalList Die Klasse NormalList besteht aus einem herkömmlichen Integer-Array. ## ObjectList Bei der ObjectList handelt es sich um ein Array von Objekten der selbst erstellten IntObject-Klasse. Die Klasse ist ein Wrapper für einen einzelnen Integer. ## BigObjectList Bei BigObjectList handelt es sich um ein Array von Objekten der selbst erstellten BigObject-Klasse. Diese Klasse enthält einen Integer und zwölf Long, wobei nur der Integerwert für die Sortierung benutzt wird. Die Longs sind dazu gedacht die einzelnen Objekte der Klasse auf 800 Bit aufzublasen, was dazu führt, dass das Array dieser Objekte nicht vollständig in den Cache der Testmaschine passt. ## GeneratorGroupList Die GeneratorGroupList ist ein spezielles Array insofern, als dass es sich wieder um ein normales Integer-Array handelt, das die zu sortierenden Werte enthält, allerdings funktioniert das Ansprechen der einzelnen Stellen des Arrays über ein Übersetzungsarray, das die Indizes für das Werte-Array enthält. Dieses Übersetzungsarray enthält die Elemente der zyklischen Gruppe die von 101 in der Restgruppe von 130696 erzeugt werden. Damit erreichen wir einen Random Access auf das Wertearray und dementsprechend oft sollte bei Verwendung der GeneratorGroupList ein Cache Miss auftreten. # Erwartungen ## Bubblesort Der Bubblesort wird selbstverständlich aufgrund seiner Average Case Zeitkomplexität von O(n^2) der langsamste Sortieralgorithmus sein. Bei den reverse befüllten Listen wird der Algorithmus noch einmal deutlich langsamer sein, da alle Elemente sehr weit getauscht werden müssen. Der Unterschied bei der Benutzung der (Big)ObjectList sollte nicht besonders groß sein, da nur Elemente vertauscht werden, die nebeneinander liegen und es so nicht besonders häufig zu Cache Misses kommen sollte. Bei der GeneratorGroupList wird das hingegen schon so sein, weshalb wir hier eine signifikant längere Laufzeit erwarten. ## Radixsort Hier erwarten wir uns eine deutlich bessere Performance als bei Bubblesort. Die reverse befüllten Listen sollten keine gröbere Auswirkung haben, da beim Anlegen der Subarrays für den Radixsort das Inputarray sowieso einmal komplett durchgegangen wird. Auch bei Radixsort sollte das Benutzen der (Big)ObjectList keine signifikante Auswirkung haben, da die Objekte hintereinander angesprochen werden und somit im Cache liegen sollten. Für die GeneratorGroupList erwarten wir uns aber analog zu Bubblesort ebenfalls eine spürbar schlechtere Performance. ## Bucketsort Für Bucketsort erwarten wir uns eine ähnliche Laufzeit wie bei Radixsort. Der für die einzelnen Buckets verwendete Algorithmus ist der Bubblesort und deswegen erwarten wir uns auch hier eine deutlich schlechtere Performance bei reverse befüllten Listen. # Ergebnisse Die hier abgebildeten Zeiten sind der jeweilige Durchschnitt aus 10 runs und sind somit nur ein Auszug aus unseren Ergebnissen. Eine genauere Auflistung der Ergebnisse entnehmen Sie bitte der angehängten results.txt - file. ## Bubblesort * Random Array - NormalList: 115.228ms * Reverse Array - NormalList: 137.060ms * Random Array - GeneratorGroupList: 144.843ms * Reverse Array - GeneratorGroupList: 159.354ms * Random Array - ObjectList: 128.011ms * Reverse Array - ObjectList: 129.244ms * Random Array - BigObjectList: 155.207ms * Reverse Array - BigObjectList: 166.556ms ## Radixsort * Random Array - NormalList: 49ms * Reverse Array - NormalList: 53ms * Random Array - GeneratorGroupList: 63ms * Reverse Array - GeneratorGroupList: 57ms * Random Array - ObjectList: 59ms * Reverse Array - ObjectList: 48ms * Random Array - BigObjectList: 108ms * Reverse Array - BigObjectList: 109ms ## Bucketsort * Random Array - NormalList: 183ms * Reverse Array - NormalList: 211ms * Random Array - GeneratorGroupList: 234ms * Reverse Array - GeneratorGroupList: 242ms * Random Array - ObjectList: 225ms * Reverse Array - ObjectList: 219ms * Random Array - BigObjectList: 256ms * Reverse Array - BigObjectList: 305ms # Erkenntnisse ## Bubblesort Der Bubblesort Algorithmus verhält sich nach unseren Erwartungen, er läuft bei steigender Anzahl der zu sortierenden Elementen n wirklich sehr lange. Einzige Unklarheit ist, dass die Variante Reverse - ObjectArray druchschnittlich schneller war als die nicht umgekehrte Variante des ObjectArray. (reverse 219ms avg. / nicht reverse ObjectList: 225ms avg.) ## Radixsort Unsere Annahmen, inklusive der, dass beim Radixsort kein erkennbarer Unterschied zwischen einem Random Array und einen Reverse Array besteht, haben sich alle bestätigt. Eine Sache, die uns jedoch verwundert hat, ist, dass die Runs, abgesehen von der BigObjectList, immer schneller geworden sind. Unserer Vermutung nach hat dies mit dem nicht geclearten und nicht voll ausgereizten Cache zu tun, jedoch können wir uns dies nicht genau erklären. Ein weiteres Phänomen, welches für uns nicht verständlich ist, ist, dass bei der BigObjectList die Ergebnisse zwischen den Runs auffällig sprunghaft sind. Wir vermuten jedoch, dass es an den oftigen Kopieren von weit entfernten Indizes im Array zu tun hat, und dies abhängig von den genauen Inputdaten mehr oder weniger oft stattfindet. ## Bucketsort Überrascht hat uns, dass der Bucketsort entgegen unseren Erwartungen trotz ähnlicher Funktionsweise mit den Subarrays deutlich langsamer durchgelaufen ist als der Radixsort. Wir gehen aber davon aus, dass das daran liegt, dass zum Sortieren der Buckets mit Bubblesort ein recht ineffizienter Sortieralgorithmus gewählt wurde. Ansonsten kann man aufgrund dieser Tatsache auch gut beobachten, dass sich die Verhältnisse der Laufzeiten bei den unterschiedlichen Variationen analog zu Bubblesort verhält. Der Performanceunterschied zu Bubblesort liegt hier einfach daran, dass die Buckets sehr viel kleiner sind als die Inputarrays und aufgrund der Zeitkomplexität des Bubblesort O(n^2) das Sortieren der Buckets somit wesentlich schneller abläuft als im reinen Bubblesort.