SAUCE SAUCE

Aufgabe 2: Rekursion/Iteration 2 (Bubblesort) Assignment

Bubblesort ist kein optimaler aber einfacher Algorithmus für das Sortieren einer Liste von Zahlen. Sie sollen sich mit diesem instruktiven Algorithmus in dieser Aufgabe einmal auseinander setzen. Der Algorithmus funktioniert folgendermaßen: 

Eingabe: Liste von n Zahlen
Ausgabe: Aufsteigend sortierte Liste dieser n Zahlen
                                                                                                                                                                                                                                   
Grobalgorithmus Bubblesort:
1. Gehe die Liste sukzessive durch: 
        Vergleiche jeweils das aktuelle Element mit dem Nächsten. Ist das aktuelle Element größer als das Nächste, dann vertausche die beiden. 
2. Wiederhole Schritt 1, bis die Liste aufsteigend sortiert ist. 

Aufgaben:
1. Implementieren Sie diesen Algorithmus in einem Unterprogramm bubblesort_it(a), dem eine unsortierte Liste a übergeben wird und das die Liste sortiert zurück gibt. 
2. Überlegen Sie sich analog zur Vorlesung und Aufgabe 3 von Übungsblatt 8 den Laufzeitaufwand O dieses Algorithmus für eine Liste mit n Zahlen. 
3. Implementieren Sie den Algorithmus in einem Unterprogramm bubblesort_rec(a) rein rekursiv (also ohne die Verwendung von Schleifen). (Hinweis: Fällt Ihnen die rekursive Formulierung schwer, so beobachten Sie das Verhalten des iterativen Algorithmus bei jeder abgeschlossenen Iteration über die Liste. Gibt es Stellen, die sich nach den Durchläufen nicht mehr ändern und könnte man so das Problem rekursiv verkleinern, bis es trivial wird (Divide-and-Conquer Prinzip) ?) 

Scaffold Head
Scaffold Foot
Start time:
Do 21 Dez 2017 14:00:56
End time:
Do 11 Jan 2018 14:00:56
General test timeout:
20.0 seconds

Tests

Comment prefix #
Given input 
[-16, -87, 1, -73, -63, -100, 25, -71, 77, -46]
[37, 39, -39, -67, 69, 23, -66, 80, 45, -43]
[46, -84, -10, 72, 40, 6, -82, -42, -93, -11]
[-68, 11, -98, 10, -91, -78, 26, -41, -51, -76]
[-41, 10, -32, 54, 45, 63, -14, 64, 68, -38]
[-38, -50, 15, -29, -5, -91, -9, -42, 66, 16]
[-25, 63, -18, 27, -72, -65, 23, -11, -99, 2]
[-72, -25, 76, 77, 0, -18, 91, -25, 62, -27]
[-10, 73, 82, -67, -8, 54, 97, 20, 46, 86]
[84, -29, -99, 64, -41, -36, -20, 45, -21, -50]
[49, 15, 77, 100, 1, 61, 59, 26]
[67, 59, 13, 46, 6, 13, 72, 49]
[58, 21, 55, 40, 94, 81, 72, 30]
[70, 10, 54, 75, 93, 88, 82, 24]
[80, 36, 74, 56, 35, 10, 64, 85]
[41, 26, 94, 77, 39, 13, 7, 67]
[79, 20, 94, 76, 84, 20, 70, 59]
[58, 46, 37, 68, 22, 51, 68, 54]
[79, 98, 4, 67, 11, 78, 31, 57]
[10, 83, 25, 46, 45, 11, 36, 54]
[-77, -68, -4, -60, -67, -72, -63, -44]
[-13, -4, -51, -14, -19, -68, -7, -41]
[-97, -2, -94, -47, -64, -75, -1, -25]
[-38, -29, -22, -49, -23, -8, -43, -59]
[-17, -29, -59, -31, -81, -23, -9, -86]
[-72, -4, -27, -48, -8, -70, -30, -42]
[-78, -33, -13, -23, -76, -10, -15, -77]
[-95, -12, -84, -87, -64, -36, -88, -58]
[-41, -80, -70, -45, -63, -98, -44, -85]
[-12, -82, -98, -67, -80, -70, -50, -71]
[]
Expected output 
[-100, -87, -73, -71, -63, -46, -16, 1, 25, 77]
[-67, -66, -43, -39, 23, 37, 39, 45, 69, 80]
[-93, -84, -82, -42, -11, -10, 6, 40, 46, 72]
[-98, -91, -78, -76, -68, -51, -41, 10, 11, 26]
[-41, -38, -32, -14, 10, 45, 54, 63, 64, 68]
[-91, -50, -42, -38, -29, -9, -5, 15, 16, 66]
[-99, -72, -65, -25, -18, -11, 2, 23, 27, 63]
[-72, -27, -25, -25, -18, 0, 62, 76, 77, 91]
[-67, -10, -8, 20, 46, 54, 73, 82, 86, 97]
[-99, -50, -41, -36, -29, -21, -20, 45, 64, 84]
[1, 15, 26, 49, 59, 61, 77, 100]
[6, 13, 13, 46, 49, 59, 67, 72]
[21, 30, 40, 55, 58, 72, 81, 94]
[10, 24, 54, 70, 75, 82, 88, 93]
[10, 35, 36, 56, 64, 74, 80, 85]
[7, 13, 26, 39, 41, 67, 77, 94]
[20, 20, 59, 70, 76, 79, 84, 94]
[22, 37, 46, 51, 54, 58, 68, 68]
[4, 11, 31, 57, 67, 78, 79, 98]
[10, 11, 25, 36, 45, 46, 54, 83]
[-77, -72, -68, -67, -63, -60, -44, -4]
[-68, -51, -41, -19, -14, -13, -7, -4]
[-97, -94, -75, -64, -47, -25, -2, -1]
[-59, -49, -43, -38, -29, -23, -22, -8]
[-86, -81, -59, -31, -29, -23, -17, -9]
[-72, -70, -48, -42, -30, -27, -8, -4]
[-78, -77, -76, -33, -23, -15, -13, -10]
[-95, -88, -87, -84, -64, -58, -36, -12]
[-98, -85, -80, -70, -63, -45, -44, -41]
[-98, -82, -80, -71, -70, -67, -50, -12]
[]
[-100, -87, -73, -71, -63, -46, -16, 1, 25, 77]
[-67, -66, -43, -39, 23, 37, 39, 45, 69, 80]
[-93, -84, -82, -42, -11, -10, 6, 40, 46, 72]
[-98, -91, -78, -76, -68, -51, -41, 10, 11, 26]
[-41, -38, -32, -14, 10, 45, 54, 63, 64, 68]
[-91, -50, -42, -38, -29, -9, -5, 15, 16, 66]
[-99, -72, -65, -25, -18, -11, 2, 23, 27, 63]
[-72, -27, -25, -25, -18, 0, 62, 76, 77, 91]
[-67, -10, -8, 20, 46, 54, 73, 82, 86, 97]
[-99, -50, -41, -36, -29, -21, -20, 45, 64, 84]
[1, 15, 26, 49, 59, 61, 77, 100]
[6, 13, 13, 46, 49, 59, 67, 72]
[21, 30, 40, 55, 58, 72, 81, 94]
[10, 24, 54, 70, 75, 82, 88, 93]
[10, 35, 36, 56, 64, 74, 80, 85]
[7, 13, 26, 39, 41, 67, 77, 94]
[20, 20, 59, 70, 76, 79, 84, 94]
[22, 37, 46, 51, 54, 58, 68, 68]
[4, 11, 31, 57, 67, 78, 79, 98]
[10, 11, 25, 36, 45, 46, 54, 83]
[-77, -72, -68, -67, -63, -60, -44, -4]
[-68, -51, -41, -19, -14, -13, -7, -4]
[-97, -94, -75, -64, -47, -25, -2, -1]
[-59, -49, -43, -38, -29, -23, -22, -8]
[-86, -81, -59, -31, -29, -23, -17, -9]
[-72, -70, -48, -42, -30, -27, -8, -4]
[-78, -77, -76, -33, -23, -15, -13, -10]
[-95, -88, -87, -84, -64, -58, -36, -12]
[-98, -85, -80, -70, -63, -45, -44, -41]
[-98, -82, -80, -71, -70, -67, -50, -12]
[]