Zum Inhalt

Sortieren

BubbleSort

Nun wollen wir den BubbleSort-Algorithmus auch implementieren. Als Erinnerung, hier eine Beschreibung des Algorithmus:

Schritt Was tun
1 Wähle die ersten beiden Elemente von links.
2 Ist beim gewählten Paar das linke Element grösser als das rechte? Wenn ja, vertausche die beiden.
3 Hat es rechts des soeben untersuchten Paares noch weitere Kugeln? Wenn ja, wähle das nächste Paar benachbarter Elemente und gehe zu Schritt 2.
4 Wir haben einen Durchgang beendet. Wurde in diesem Durchgang mindestens ein "falsches" Paar gefunden und vertauscht? Wenn ja, gehe zu Schritt 1, d.h. starte einen weiteren Durchgang. Wenn nein, sind wir fertig.

Vorgehen

Einen Algorithmus wie BubbleSort in einer Programmiersprache zu implementieren ist gar nicht so einfach! Darum zerteilen wir den Algorithmus in kleinere Schritte, lösen zuerst die Teilprobleme und kombinieren am Schluss die Teillösungen.

Die Schritte vom Algorithmus können wir z.B. in folgende Teilprobleme zerlegen:

  • (die ersten) zwei aufeinanderfolgende Elemente (ein Paar) eines Felds auswählen
  • zwei Elemente vergleichen
  • zwei Elemente vertauschen
  • ein Durchgang durchführen: d.h. einmal alle Elemente vergleichen & falls nötig vertauschen
  • soviel Durchgänge durchführen wie nötig, bis alle Elemente sortiert sind

Implementierung

Teilprobleme

Elemente vergleichen
Zwei Elemente vergleichen

Vergleiche einmal die ersten zwei Elemente von dem vorgegebenen Feld. Mit dem Ziel das Feld schlussendlich aufsteigend zu sortieren, was ist das Vergleichskriterium?

Gibt 'alles ok' aus, wenn die Anordnung der ersten zwei Elementen stimmt, andernfalls 'falsche Ordnung'.

Überprüfe deine Lösung, indem du das Feld von Hand richtig sortierst und dein Programm nochmals laufen läst: es sollte 'alles ok' erscheinen.

###(De-)Aktiviert den Code nach der Zeile # Tests (Groß-/Kleinschreibung wird nicht beachtet)
(Ctrl+I)
Ein- oder Ausstieg aus dem "Split-Screen"-Modus
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
Ein- oder Ausstieg aus dem "Vollbildmodus"
(Esc)
Kürzen/nicht kürzen der Rückmeldungen im Terminal (Standardausgabe & Stacktrace / Starte das Programm erneut zum Anwenden)
Wenn aktiviert, wird der aus dem Terminal kopierte Text in eine Zeile umgewandelt, bevor er in die Zwischenablage kopiert wird.

.128013I c2L(o4xkgfö3e=)i5hy/;apuOtEnd0m:sl[r1]qbv050F0p0C0y0s0K0J0c0d0K0y0J0J0q010C0s0z010406050J0A0H0H0y0M0v040f0n0?0E0l050w0?0^0`0|0;0z04051a131d0w1a0;0F0s0R0!0$0(0*0u0s0l0u0K1r0u0C0/050V0Q0K0p1m0%0)011q1s1u1s0C1A1C1y0C0M1b0C0u0!0h0Y0z0y0E0*0e011E1o010m0X0p0E0y0H0p1y0J1Y0E1(1G1+1C1.1:0/0a0c0~100l0J0R0h0M0J0d1t0y12141@1b0w1T2g1Q1S1R1z0F1_0*1u0E1-0h0J1y1j1l0#1F2q0s2s0E0h2x1y0z0M0p1b1?1Z2g2M0E2L1@2p012E0M0_0K0/0N132P0:0=2S2z1)2V2X0/0e2#2f0;2P2T2,0y2Y040o2:2N2=2)1n1G2^2`0i2}2Q2 1Z2@272-040t362g2I2K132x2j0F1S2o2*1G0d2F1;1b3k1c2J2R2N3f053r0T3y1^3p0*0d0N0/030c0p280C0p0Z0D1C1:0E0C0c0u0y3W0b0E0T0j0I0c0G3f383F310*0k0/0s0m3f0c2(393G2U0/0F2u1-3A2?3|0.040L42302A010H0s0/3+2e3z433/01450O3^3`3.4a0h0/020K0C0x4n4i4a0E3~400E483{4j45474g2Q4o2T4c2Z4E4p1)4l0I3,0c4V3_4y2+0Q0/2I2C0C4P2T450g4)3|0J1$04020P0A0h4v2_1C0Z0h0k4=4@4v4-4G0/0r3,4L3|3;040p0Y0p524a454T4J0:4W4X494Z4#0M4%5e4R0/4,5i574j4/4s4?4^0x0m2_290u1D0B0M0F0E0A114 5B5r1G45555i0;0w3C3i1g3x3j1k3l2j2m2h0y1B5Y3k5V0T0V0X0J04.
Lösung 
1
2
3
4
5
# erstes Element hat Index: 0
if dosen[0] < dosen[1]:
    print("alles ok")
else:
    print("falsche Ordnung")
Elemente vertauschen
Zwei Elemente vertauschen

Unser zweites Teilproblem besteht darin, zwei Elementen in einem Feld zu vertauschen. Ziel ist es, dass das erste Element nachher an zweiter Stelle steht. Versuche, diese Teilaufgabe zu lösen.

###(De-)Aktiviert den Code nach der Zeile # Tests (Groß-/Kleinschreibung wird nicht beachtet)
(Ctrl+I)
Ein- oder Ausstieg aus dem "Split-Screen"-Modus
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
Ein- oder Ausstieg aus dem "Vollbildmodus"
(Esc)
Kürzen/nicht kürzen der Rückmeldungen im Terminal (Standardausgabe & Stacktrace / Starte das Programm erneut zum Anwenden)
Wenn aktiviert, wird der aus dem Terminal kopierte Text in eine Zeile umgewandelt, bevor er in die Zwischenablage kopiert wird.

.128013S c2zLogfö3e=iäVhy/aputEndwms[r1]vlb0050A0m0x0u0o0J0D0c0d0J0u0D0D0n010x0o0v010406050D0w0C0C0u0F0s040g0k0-0z0i050t0-0/0;0?0+0v0405140}170t140+0A0o0I0U0W0Y0!0r0o0i0r0J1l0r0x0)050P0K0J0m1g0X0Z011k1m1o1m0x1u1w1s0x0F150x0r0U0h0S0v0u0z0!0e011y1i010j0R0m0z0u0C0m1s0D1S0z1Y1A1#1w1(1*0)0a0c0^0`0i0D0I0h0F0D0d1n0u0|0~1.150t1N2a1K1M1L1t0A1:0!1o0z1%0h0D1s1d1f0V1z2k0o2m0z0h2r1s0v0F0m151-1T2a2G0z2F1.2j012y0F0:0J0)0G0}2J0*0,2M2t1Z2P2R0)0e2V290+2J2N2$0u2S040l2*2H182D2a2r2d0A1M2i2!1A0d2z1+152|162`2Y2^282^330N2L1T2.0)0x0m0C0v2@2K0c3a1/310!0h0)0n3o043q2-3t2O0)0A2o1%3y3r2N0(040E3I3B1h1A0C0o0)0L3O2Z3Q0!3L0H3y3A3X2u010d0G0)030c3k3m210p2D0c0q0;0o0u1v1x0.0c0A0X0c0y1w1*0z0x0c0f0B0o230r1%0f0w1-0m0o240m0F0z3y2,3(2#3E3G4o3c2K3J3C3L3N4w3g3s3Y013S3U3W3h4z0)3#4C3%4K4F3v043x4O4y4F0z4t0D3H4C4W3)4A4J4E3)4H042U4$3P4(4M3$4%1Z3+3-490B4j3k0T3h1d1x0b3k0J1w0c200C0c4m0D3k4v2W4q4Q3)4Y043F4!5f294^1A4)4:4r3R3T4.4*3K4?4V4;1Z4S4U2W4P4+4s043:3n4C0+0t3e2E2_5R0t372b2~0}2e5Y3|1w2{1e2X5U0O0Q0S04.
Lösung 
1
2
3
temp = dosen[0] # temporäre Variable um das Element zwischenzuspeichern
dosen[0] = dosen[1] # zweites an die Stelle vom ersten
dosen[1] = temp
Durchgang
Ein ganzer BubbleSort 'Durchgang'

Kombiniere nun die ersten zwei Teillösungen und führe deren Schritte für alle Elemente einmal aus: also ein BubbleSort Durchgang durchführen.

Hinweise:

  • eine for-Schleife ist ganz nützlich

  • falls du auf folgende Fehlermeldung stösst: IndexError: list index out of range: dies bedeutet, dass du auf ein Element versuchts zuzugreifen, welches nicht existiert. D.h. es gibt kein Element mit diesem Index, meistens ist der Index zu gross!

###(De-)Aktiviert den Code nach der Zeile # Tests (Groß-/Kleinschreibung wird nicht beachtet)
(Ctrl+I)
Ein- oder Ausstieg aus dem "Split-Screen"-Modus
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
Ein- oder Ausstieg aus dem "Vollbildmodus"
(Esc)
Kürzen/nicht kürzen der Rückmeldungen im Terminal (Standardausgabe & Stacktrace / Starte das Programm erneut zum Anwenden)
Wenn aktiviert, wird der aus dem Terminal kopierte Text in eine Zeile umgewandelt, bevor er in die Zwischenablage kopiert wird.

.128013S c2zL(o4kgfö3e=)i6äV5hy/;aputEndwm-:+sl[r1]bv050H0p0E0B0s0O0N0c0d0O0B0N0N0q010E0s0C010406050N0D0J0J0B0Q0y040g0n0_0G0l050z0_0{0}0 0@0C04051d161g0z1d0@0H0s0U0%0)0+0-0x0s0l0x0O1u0x0E0=050Y0T0O0p1p0*0,011t1v1x1v0E1D1F1B0E0Q1e0E0x0%0i0#0C0B0G0-0e011H1r010m0!0p0G0B0J0p1B0N1#0G1+1J1.1F1;1?0=0a0c11130l0N0U0i0Q0N0d1w0B15171`1e0z1W2j1T1V1U1C0H1|0-1x0G1:0i0N1B1m1o0(1I2t0s2v0G0i2A1B0C0Q0p1e1_1$2j2P0G2O1`2s012H0Q0|0O0=0R162S0?0^2V2C1,2Y2!0=0e2(2i0@2S2W2/0B2#040o2?2Q2^2,1q1J2{2}0j302T321$2`2a2:040w392*2_2-353e2|0=0t3i1h2M2j2A2m0H1V2r3l0-0d2I1@1e3v1f3t2+2Q3r3C0W2U3c3A010k0=0m2a3i0c3J1{3Q0G0=0s3W3Y2W0i0I3$0G3(3k340-0G0T0=0Q1$0l0p3r3:2D010;040h3}333 3?0=1 443P3;400=432h3K3~2.0=0H2x1:4a3Z4c410r4o3*0=0K4t3Q0J0s2$4x4q0=0r0L3i06060c4K3X4i1J3S040s0m3/454j044l0N4n4g2T3)3Q410P4C463$4*1,410S4T4b3 0i0=020l0E0A4;4p4+4W4m3.4!3O4~4.0=4)534$4c3#4Q4-1J4@040M5e0-4z4B594N0-4/4G534J4L5u5a4 0E0p0J0C4}4u040q5C3!4k515j4d04582)5w4V3%5n4U1J4/5G4c0d0R0=030c5y5A2a0u2M0c0v0}0s0B1E1G0`0c0H0*0c0F1F1?0G0E0c0f0I0s2c0x1:0f0D1_0p0s2d0p0Q522)5t5u4K5P355I4Y6f2i6k5p575K5c5R5O5o5L4:534M5T0-5g5F6A6q2X6m4Z6w6C5L5N6p6x6u5K5g5i5S4=1,5l042%6V555U0=6z2)6B6W1J5Y5!600I6a5y0$3c1m1G0b5y0O1F0c290J0c6d0N5y6o316i4L6H5c4X6K6P6M4(6t4,6#2W5V6G6x6E5W5x5z5B5s163M2N3s7w0z3G2k3x162n7D5:1F3u1n2*7z0X0Z0#04.
Lösung 
1
2
3
4
5
6
for i in range(len(dosen)-1):

    if dosen[i] > dosen[i+1]:
        temp = dosen[i] # temporäre Variable um das Element zwischenzuspeichern
        dosen[i] = dosen[i+1] # zweites an die Stelle vom ersten
        dosen[i] = temp

Vollständige Implementation

Entwickle nun eine Funktion, welche ein Feld mit dem BubbleSort Algorithmus aufsteigend sortiert.

Question

Nun gilt es alle vorherigen Teillösungen zu kombinieren.

Das Programstück ab # Tests beinhaltet ein paar Beispiele, welche deine Bubblesort Implementierung direkt überprüft.

###(De-)Aktiviert den Code nach der Zeile # Tests (Groß-/Kleinschreibung wird nicht beachtet)
(Ctrl+I)
Ein- oder Ausstieg aus dem "Split-Screen"-Modus
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
Ein- oder Ausstieg aus dem "Vollbildmodus"
(Esc)
Kürzen/nicht kürzen der Rückmeldungen im Terminal (Standardausgabe & Stacktrace / Starte das Programm erneut zum Anwenden)
Wenn aktiviert, wird der aus dem Terminal kopierte Text in eine Zeile umgewandelt, bevor er in die Zwischenablage kopiert wird.
Verbleibende Versuche : 5/5

.128013 c2L(o4kDgfö3e=)i6785hy/9;aputEnd0m:w-+sl[r1]bv050H0o0E0B0r0P0O0b0c0P0B0O0O0p010E0r0C010406050O0D0J0J0B0R0x040e0m0`0G0k050y0`0|0~100^0C04051e171h0y1e0^0H0r0V0(0*0,0.0w0r0k0w0P1v0w0E0?050Z0U0P0o1q0+0-011u1w1y1w0E1E1G1C0E0R1f0E0w0(0g0$0C0B0G0.0d011I1s010l0#0o0G0B0J0o1C0O1$0G1,1K1/1G1=1@0?0a0b12140k0O0V0g0R0O0c1x0B16181{1f0y1X2k1U1W1V1D0H1}0.1y0G1;0g0O1C1n1p0)1J2u0r2w0G0g2B1C0C0R0o1f1`1%2k2Q0G2P1{2t012I0R0}0P0?0b0S172T0@0_2W2D1-2Z2#2%0d2*2j0^2T2X2;0B2$040b0n2^2R2`2.1r1K2}2 0b0h332U351%2|2b2=300v3d2,2{2/383i2~2%0s3m3f1|3p0.392%0t3v2-3g3y2Y3r3a0u3D3o373z3I2%0z3L362E3H2!3s040S0I3S3F3N3V3j0S2)2i343E3x3%3A3Y2@3,3e3.3h3W2 0S323@2k2M2O172B2n0H1W2s3G0c2J1^1f441g2N2V2R3m054a0X4h3/3U0i0?0X0l3m0b3_3G0G0l0?0U0D0U1F0o0O2b0E4j3M3U0=040f4J3T2:4r0B0E1;4P3$4L0?0q0K3v0b4%4v4K1-4q040l2b4u4w3:0?0D4:4*1K0g0L0?2G4^4Q380U0?0R1%0k0o4W4o1-4M4O3 4;3U0G520420582X5b5k4x4S4U0G5n3%4M0q4!3v064(5z4)500.0c0S0?030b0F2G0b0j0D0R2e0k554$5A4%5e4+0?4.0R4 4X4R040r5!594`4|5%5r3 5B5#515355575d4_0.5m5_5C2Y5h5j5}5;5{0?5c2+5V385p4V625*64040q5)2X0g0?0M6h3G0J0r0?3+675`015u4#3 065y5T5A680.4,0r4t5/6C2Y6a5.6s5~4M0Q5s5f4}6Q5a0?0T6m3%6j04020k0E0A6X6R040H4T6b6M636u0?6P6c2|6S6H6t6Z0N6)1-6o6q6T1K4M0T6w2+6z6A6A6I5E5G0b0V0o0R0Z0D2d0w1;0b0G0m0:2h7779796I0G0?4U0J0C6~4`0?0p7B3z6K726e6?6/6d6J5%7I6;046W6x7t7a6t7w6+6-6L2j6I6O7P7X5(6@3G747F016Z7E6`5~7X6,5q7P7%7+4=7O7=6:6|7.703Y7`6V5S7U5z7v7H7|4Y047K7#7W6_2+5:7M817 7M836r8g6N868n6i7D7.7X7y7A6x788k2X4,2N0E5N7!2R8D5o7Y7_6x174l421k4g431o452n2q2l0B4E2k440^0y0X0Z0#0O04.
Lösung 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def bubblesort(daten):
    for u in range(len(daten)):

        # Ein Durchgang
        for i in range(len(daten) - 1):

            if daten[i] > daten[i + 1]:
                # vertauschen nötig
                temp = daten[i]
                daten[i] = daten[i + 1]
                daten[i + 1] = temp

    return daten

Effiziente Implementierung

Gemäss BubbleSort Algorithmus müssten wir nur so oft einen Vergleich/Vertausch-Durchgang durchführen, bis kein Vertauschen mehr notwendig ist. Andernfalls muss das Programm unnötige Arbeit verrichten, ist langsamer und verbraucht mehr Energie.

Schleifen vorzeitig abbrechen: break

Abstract

Es gibt ein Programmierkonstrukt mit dem wir eine Schleife vorzeitig beenden können. Dazu verwenden wir das Schlüsselwort break. Es bewirkt, dass die dazugehörige Schleife sofort beendet wird. Alle Programmzeilen innerhalb der Schleife die nach break auftreten, werden nicht mehr ausgeführt.

Beispiel: Schleife mit break abbrechen

###(De-)Aktiviert den Code nach der Zeile # Tests (Groß-/Kleinschreibung wird nicht beachtet)
(Ctrl+I)
Ein- oder Ausstieg aus dem "Split-Screen"-Modus
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
Ein- oder Ausstieg aus dem "Vollbildmodus"
(Esc)
Kürzen/nicht kürzen der Rückmeldungen im Terminal (Standardausgabe & Stacktrace / Starte das Programm erneut zum Anwenden)
Wenn aktiviert, wird der aus dem Terminal kopierte Text in eine Zeile umgewandelt, bevor er in die Zwischenablage kopiert wird.

effizientere BubbleSort Implementation

Ändere nun deine BubbleSort Implementierung so ab, dass nur soviel Durchgänge ausgeführt werden wie notwendig.

Effizientere BubbleSort Implementation

Führe nur soviele Durchgänge durch, wie gemäss Algorithmus notwendig sind.

Kopiere dazu deine Lösung aus 'Vollständige Implementation' und verändere sie nachfolgend.

Sobald das Feld sortiert ist, kann mit break die entsprechende Schleife vorzeitig beendet werden.

###(De-)Aktiviert den Code nach der Zeile # Tests (Groß-/Kleinschreibung wird nicht beachtet)
(Ctrl+I)
Ein- oder Ausstieg aus dem "Split-Screen"-Modus
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
Ein- oder Ausstieg aus dem "Vollbildmodus"
(Esc)
Kürzen/nicht kürzen der Rückmeldungen im Terminal (Standardausgabe & Stacktrace / Starte das Programm erneut zum Anwenden)
Wenn aktiviert, wird der aus dem Terminal kopierte Text in eine Zeile umgewandelt, bevor er in die Zwischenablage kopiert wird.
Verbleibende Versuche : 5/5

.128013j FTc2L(o4kDgfö3e=)i6785hy/9;aputEnd0m:w-+sl[r1]bv050K0r0H0E0u0S0R0c0f0S0E0R0R0s010H0u0F010406050R0G0M0M0E0U0A040h0p0}0J0n050B0}0 11130{0F04051h1a1k0B1h0{0K0u0Y0+0-0/0;0z0u0n0z0S1y0z0H0_050$0X0S0r1t0.0:011x1z1B1z0H1H1J1F0H0U1i0H0z0+0j0)0F0E0J0;0g011L1v010o0(0r0J0E0M0r1F0R1)0J1/1N1=1J1^1`0_0a0c15170n0R0Y0j0U0R0f1A0E191b1~1i0B1!2n1X1Z1Y1G0K200;1B0J1@0j0R1F1q1s0,1M2x0u2z0J0j2E1F0F0U0r1i1}1*2n2T0J2S1~2w012L0U100S0_0c0V1a2W0`0|2Z2G1:2$2(2*0g2-2m0{2W2!2@0E2)040c0q2{2U2}2;1u1N30320c0k362X381*2 2e2^330y3g2/2~2=3b3l312*0v3p3i1 3s0;3c2*0w3y2:3j3B2#3u3d0x3G3r3a3C3L2*0C3O392H3K2%3v040V0L3V3I3Q3Y3m0V2,2l373H3A3*3D3#2`3/3h3;3k3Z320V353`3q3W2?3S3#3f423z3}3,3o493|3J3@0V3x4e3P3X4h3F4k443t3~0_0V3N421l2Q2n2E2q0K1Z2v3J0f2M1{1i4A1j4y3;2V2m054G0!2Y3)3X0l0_0!0o3p0c4f3?0o0_0X0G0X1I0r0R2e0H3p4$3X0^040i4=4l2?4X0E0H1@4{4q0;4^0t0N3y060c5a4#4|1N4W040o2e4!4?4}040b5j5d0;0j0O0_2J5o532#0X0_0U1*0n0r524U1:4^4`4w5p5x0_235E3=4@0_5I2.5k3b4~500J5O2!5556585b5(5c5w0J0_0R0O0E0F0F0r0K5v5F1N0j0_0s5^5P1:0l0f0_0d310R5D495)5b5U0;0f0V0_030c0I2J0c0m0G0U2h0n5B3y695a6b015f5h0U5~2 5t6z3J5r5t5Y425*5_3C5y045A18675T5K5H5Z4g6L5N5J5w6S6X6J2#5W516!5 1N556C3*5{040P6-3X0M0u4t6T3*5557686s5(6u5f0u4Z6H6u5,040K4 6(6Q6Y0_0T6`4m6B6)5!0_0W6=1:6/020n0H0D7n5V787a6G7c6#4^7f7j4g7i2.6I6*5q0_0Q7u0;6@6_7D6{7l6}2.596 6s6u6d6f0c0Y0r0U0$0G2g0z1@0c0J0p0?2k7U7W7X5K77500M0F7M016/5}757_6%7y4P6R7e7g5l0u896+7l6r7@5)76848c54887Q7h048b8n5G8e825w807~77795X8k017B8B778q7G6u6/7L8u6#7O3#8B4^7m6~8g6a837w8A8r8d047C7z7I6$8p7~8J7~8N3.8$7k048R8H5K8w8L8%7`0r7|8f8T6t8V5.5:5=5@8_2!8^8?5w610_0e0U0G6P2|7V69715t74996#77925;5?8*5|819n8%9b04640)9g2U6u4^7T2|8T9k040X2Q0E0l5%8U9a5z0#6m852U7H6A8W7b2|1a4R2R4x9(0B4K2o4C1a2r9/0E4-4z1r2/9+0#0%0)04.
Lösung 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def bubblesort(daten):

    for j in range(len(daten)):

        swapped = False
        # Ein Durchgang
        for i in range(len(daten) - 1):
            if daten[i] > daten[i + 1]:
                # vertauschen nötig
                temp = daten[i]
                daten[i] = daten[i + 1]
                daten[i + 1] = temp
                swapped = True

        if swapped == False:
            break

    return daten

BubbleSort Laufzeit

Wir wollen nun bestimmen, wie "gut" dieser Algorithmus zum sortieren ist. Dazu könnten wir die Zeit messen, die benötigt wird um ein Feld zu sortieren.

Laufzeit von BubbleSort messen

Miss die benötigte Zeit um jeweils n Zahlen zu sortieren. Beginne mit den zufälligen Daten und erweitere dein Programm für den worst case bezüglich der Datenverteilung.

Stelle die Laufzeiten mit einem Diagramm dar.

Deine Abbildung

Deine Abbildung wird hier erscheinen

###(De-)Aktiviert den Code nach der Zeile # Tests (Groß-/Kleinschreibung wird nicht beachtet)
(Ctrl+I)
Ein- oder Ausstieg aus dem "Split-Screen"-Modus
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
Ein- oder Ausstieg aus dem "Vollbildmodus"
(Esc)
Kürzen/nicht kürzen der Rückmeldungen im Terminal (Standardausgabe & Stacktrace / Starte das Programm erneut zum Anwenden)
Wenn aktiviert, wird der aus dem Terminal kopierte Text in eine Zeile umgewandelt, bevor er in die Zwischenablage kopiert wird.

.128013j FS2zLo4gfö3e=Gi75yW/9apnwm_r]vTcZ(xkD)P6ä8h;utEBd-:+s[1,.qlb0050Z0o0W0y0r0-0%0c0I0-0y0%0%0p010W0r0z010406050%0V0C0C0y0E0u040h0m1a0A0k050w1a1c1e1g180z04051u1n1x0w1u180Z0r0G0{0}0 110T0r0k0T0-1L0T0W16050?0.0-0o1G0~10011K1M1O1M0W1U1W1S0W0E1v0W0T0{0i0_0z0y0A110f011Y1I010l0^0o0A0y0C0o1S0%1_0A1 1!221W2527160a0c1i1k0k0%0G0i0E0%0I1N0y1m1o2b1v0w1;2A1.1:1/1T0Z2d111O0A240i0%1S1D1F0|1Z2K0r2M0A0i2R1S0z0E0o1v2a1`2A2*0A2)2b2J012Y0E1d0-160c0)1n2-17192:2T202?2^2`0f2}2z182-2;340y2_040c0n382+3a311H1!3d3f0c0j3j2.3l1`3c2r353g0t3t2 3b323o3y3e2`0Q3C3v2c3F113p2`0s3L303w3O2=3H3q0S3T3E3n3P3Y2`0x3#3m2U3X2@3I040)0/3,3V3%3/3z0)2|2y3k3U3N3`3Q3=373 3u413x3:3f0)3i473D3-333)3=3s4f3M4a3|3B4m493W440)3K4r3$3.4u3S4x4h3G4b160)3!4C3_4z4j0)3+4J424L4F040f3@4P4o3;0f3~2~4n4t4j0f464#4s434(4e4+4y4i4S0f4l4:4D3(4?4q4_4K4=3z0f4w4~4Q504Y4B544X3f0f4I594%4?4O5e4-4S0n4V5i4R3z0n4!394,5o3;0n4*5s4;4E5p4/5y4`3{5v4^5D4 5A5v4}5I555K3f0n535N5a160n585T5f5p5d5Y5j5p5h5$5u3f0j5m5*565,5r405z4{3z0j5x5?5E440j5C5|5J5^3;0j5H615O635,5M675U040j5S6c5Z645X6h5%645#6l5+160j5)6p5:160t5.6u5P6w5=485@5F3f0t5{6D5}4j0t606J626F6w666O686Q040t6b6T6d0t6g2.1y2%2A2R2D0Z1:2I3W0I2Z281v6+1w6)412,2z056;0;2/6P0M0A160r0C0z2r0W3C0c5t3374041d0W0z0-0i0W1O0.0+0z0u7j7l7b7d1!0M160~7u6E0A7f7j7a4W3W737577797A5}7f13273^6U7I0476780E7F2~7c7B7f0E1`0Z0i0C3L4$4316220k6C3g7v110i160p7M6P7f0P0u2Z0r0;0P7k7Y6}6E15040K3C7@010%0)1602030n0x0U7:0V2%0D0.0%7X0)8i8k0U8c88160O7R3c7/1L7=8d7_040+8y5}160?0E0k0=8L6P890K8B4m7-3.7x040;0l7|6U0A0l160.0V0.1V0o0%7L4f8d8U8S8)160Z0y0W248`2;890O0#7,0c977!5E8!0l2r8(8D040b9e3W0i0B750A9i430.167%1l0o913W8_8@7B9q042g9v3`9x2~8d7f8}8 9n9y5E939496989R9H160%0B0y0z0z0o0Z9o3.8I7{4f99720I160d3e0%9u4m9R9S6E0I8g04030c0X2W0c0N8o2u0k1`2x4#9@988d9b9d9*9T7U9$209k9mah3o9A9s8Q9D3.9F875}9A9C9M8T168bax8{8#8~90aB928Aal7^160!aJ010C0r4Gaq2093959?a99@ab758%ae7B8|aE9L9G8z040(aS3o75a/11890FaN8I020k0W8xa$8MaD9Ka=0189a.aG4ta;a 6P8I0$aNaPaRb79E160FaVa8aXbn8d9`169}0G0o7X0y0V2t0T240c0A0m13a739bnboa%048 77a_7`aN9Ia)b3b5b37f0rbSbj3LbHaXaf9JaFa+9N16b6b)7}b9b-6Ua@bN049)7Zb$bRbharb+bUb/2z9+6UbcbeaQ3=bX04a^aWb!9^b0b%a*ataya-b agbac316bdcm2;bfc7b|aTbYcq9jbOcx7.bK0obMcbcc97af9V9X9Z9#cA9%czb_6E0M9-040H0E0V9=4#06bI9aa!bP9U9W9Y9!b?0pb^c1abcT9/0_cYchb;16blbGccaZ040.2%0y0M9QcHcR9r0=8ocg2+c29fcf7,af0l0o0-0Z0q0E1j9;db2.ddcyb@aNbTcu1!cs3?c80*c56w0/6y6%a,dCcN20dzdFdG71c`04dJcQ5Edz6xdO8^16dSc:6Ecs4UdFdBdD4TdWc8cacZaf0g0o0r9K0D0g0V0l0R0-1(c-dvb+d/5/a:04d=d@240D0B2r0%0W0I0~c^dc8HcPd#b*a-e36z11ac0Ec(04dq7?6Eaj7UevdscBdidkdmdob(c_aH04c|3kcd6Pbq9|0cd`d|d~1LbZaabJdfdK1!9(et9s7)7+dxaK8Jck0%267jehdHemaAb:3cana6e=dPeJe^eI3WdMdNdNc80Od!eibJevdY048Wbmd6b0ed1e86f95Ee$e!3P8N76e}eje-e+2=169Z0E0l0D6;0V0A8 esfv8Ufec}fgb.d08.8:8=7Xc8f02+b`b2fHaIcFaf24cMdTbbekflfM7Pfsex168Kfv7DbufAfCfEbufSfJeMeXcebwf`fo01fnf%aCf#b?aMg27ffifRfZbJe7d^eSd}d fv8If:e_b804cKg7fX8ack8}cXfGgobifd7,c!f~eO9{9}eb2s0W0{egeL3ueNaCeZg52;g4el7}av0redfSbUe{9tg!f;16fbdId+dXg,g28Ig9gz3.dzf6f|gOgEaCgcfkdrftc/f*aCf,b3gmckfyf@0ifDfFf{eWfLaC8-8/1WfQg e~9wazgvb{g?cvgBgeb0gsgSdth2h0bJh5glf/h8f?fBhbf_gyf1gA8VhfeB4za(gxe0ga16hxgVcn04g=hY9fg~hPd;d?d^gIedef9;h6hFg)gqc+0Af$hMb}guh?gwg1hs1!93gCaf7Eh;fui1fp047shmfcfTe?fMeDdldn0 eHfUg/hycBgge9gieUbFinemf8hB5E0%1}04020,0V7l0U0L0!iEiGa}d*hV9B0y0.dji7hAhn3`iB8hiFiH0Jd{gj1LiLiHf68Cgpi6hEi8h{33fx85g(i9fw04iieFilg+ixetir0AeaeceeegiOip3.iYiDi!a}iJi*iNgtiyewb00}iS0-iUb3jcjh0U0vj6gL9;jti,7GcBi/i`h7h?137mf-e@jr9{8v8l0hbw0lgg0c2q2c0YfO1W0e79jNa~i`i3jBhRib0-idf.i;iwfM0LjniTgtifiWjbjM8j8l9 1liR0o0kik9;bBj#jA5ni?j+j-fmh=i`7f0uj?jpj^jL8hj}0U0Jh+0c0(0%0Fk7gtg`4gfMjDi=e#kekBia1W8Qh_hej)kakAj:hZgnkEi{0%0T9kkJ4+0w6 2(6(kZ0w6^2B6-1n2Ek*iR1W6*1E2 k$0=0@0_04.
Lösung 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import matplotlib.pyplot as plt
import time
import random

fig1 = PyodidePlot('figure_bsrt1')
fig1.target()

def bubblesort(daten):

    for j in range(len(daten)):

        swapped = False
        # Ein Durchgang
        for i in range(len(daten) - 1):
            if daten[i] > daten[i + 1]:
                # vertauschen nötig
                temp = daten[i]
                daten[i] = daten[i + 1]
                daten[i + 1] = temp
                swapped = True

        if swapped == False:
            break

    return daten

feldGrössen = [10, 500, 1000, 1500, 2000, 2500]

zeiten_zufällig = []
zeiten_worstcase = []
for n in feldGrössen:
    # zufällig
    daten = random.sample(range(10000000), n)
    start = time.perf_counter()
    bubblesort(daten)
    end = time.perf_counter()
    dauer = end - start
    zeiten_zufällig.append(dauer)


    # worst case:
    daten = list(range(n, 0, -1))
    start = time.perf_counter()
    bubblesort(daten)
    end = time.perf_counter()
    dauer = end - start
    zeiten_worstcase.append(dauer)


plt.plot(feldGrössen, zeiten_zufällig, "x-", label="Zufällig")
plt.plot(feldGrössen, zeiten_worstcase, "x-", label="Worst case")
plt.title('Laufzeit von BubbleSort')
plt.xlabel('Eingabegrösse n')
plt.ylabel('Zeit [s]')
plt.legend()
plt.show()

Aufwand bestimmen

Alternativ können wir formell untersuchen wie viele Operationen im Allgemeinen benötigt werden, um ein Feld zu sortieren.

Aufwand bestimmen für BubbleSort

Verändere dein obiges Programm so ab, dass gezählt wird, wie ein Vergleich ausgeführt wird, für verschiedene Feldergrössen.

Im schlimmsten Fall, ist das zu sortierende Feld schon verkehrt geordnet. Dies lässt sich so untersuchen:

  • verändere die bubblesort Implementation, damit sie die Anzahl Vergleiche zählt
  • verwende das nachfolgende Programmfragment um die Daten zu generieren
N = 20
daten = list(range(N,0, -1))
2 3 4 5 10

###(De-)Aktiviert den Code nach der Zeile # Tests (Groß-/Kleinschreibung wird nicht beachtet)
(Ctrl+I)
Ein- oder Ausstieg aus dem "Split-Screen"-Modus
(Alt+: ; Ctrl, um die Spalten zu vertauschen)
Ein- oder Ausstieg aus dem "Vollbildmodus"
(Esc)
Kürzen/nicht kürzen der Rückmeldungen im Terminal (Standardausgabe & Stacktrace / Starte das Programm erneut zum Anwenden)
Wenn aktiviert, wird der aus dem Terminal kopierte Text in eine Zeile umgewandelt, bevor er in die Zwischenablage kopiert wird.

.128013j FS2zLo4gfö3e=i75yW/9apnwm_r]vTcZ(xkD)P6ä8h;utEBd-:+s[1,.qNlb0050Y0o0V0x0q0-0$0c0H0-0x0$0$0p010V0q0y010406050$0U0B0B0x0D0t040h0m1a0z0k050v1a1c1e1g180y04051u1n1x0v1u180Y0q0F0{0}0 110S0q0k0S0-1L0S0V16050?0.0-0o1G0~10011K1M1O1M0V1U1W1S0V0D1v0V0S0{0i0_0y0x0z110f011Y1I010l0^0o0z0x0B0o1S0$1_0z1 1!221W2527160a0c1i1k0k0$0F0i0D0$0H1N0x1m1o2b1v0v1;2A1.1:1/1T0Y2d111O0z240i0$1S1D1F0|1Z2K0q2M0z0i2R1S0y0D0o1v2a1`2A2*0z2)2b2J012Y0D1d0-160c0(1n2-17192:2T202?2^2`0f2}2z182-2;340x2_040c0n382+3a311H1!3d3f0c0j3j2.3l1`3c2r353g0s3t2 3b323o3y3e2`0P3C3v2c3F113p2`0r3L303w3O2=3H3q0R3T3E3n3P3Y2`0w3#3m2U3X2@3I040(0/3,3V3%3/3z0(2|2y3k3U3N3`3Q3=373 3u413x3:3f0(3i473D3-333)3=3s4f3M4a3|3B4m493W440(3K4r3$3.4u3S4x4h3G4b160(3!4C3_4z4j0(3+4J424L4F040f3@4P4o3;0f3~2~4n4t4j0f464#4s434(4e4+4y4i4S0f4l4:4D3(4?4q4_4K4=3z0f4w4~4Q504Y4B544X3f0f4I594%4?4O5e4-4S0n4V5i4R3z0n4!394,5o3;0n4*5s4;4E5p4/5y4`3{5v4^5D4 5A5v4}5I555K3f0n535N5a160n585T5f5p5d5Y5j5p5h5$5u3f0j5m5*565,5r405z4{3z0j5x5?5E440j5C5|5J5^3;0j5H615O635,5M675U040j5S6c5Z645X6h5%645#6l5+160j5)6p5:160s5.6u5P6w5=485@5F3f0s5{6D5}4j0s606J626F6w666O686Q040s6b6T6d0s6g2.1y2%2A2R2D0Y1:2I3W0H2Z281v6+1w6)412,2z056;0;2/6P0L0z160q0B0y2r0V3C0c5t3374041d0V0y0-0i0V1O0.0*0y0t7j7l7b7d1!0L160~7u6E0z7f7j7a4W3W737577797A5}7f13273^6U7I0476780D7F2~7c7B7f0D1`0Y0i0B3L4$4316220k6C3g7v110i160p7M6P7f0O0t2Z0q0;0O7k7Y6}6E15040J3C7@010$0(1602030n0w0T7:0U2%0C0.0$7X0(8i8k0T8c88160N7R3c7/1L7=8d7_040*8y5}160?0D0k0=8L6P890J8B4m7-3.7x040;0l7|6U0z0l160.0U0.1V0o0$7L4f8d8U8S8)160Y0x0V248`2;890N0!7,0c977!5E8!0l2r8(8D040b9e3W0i0A750z9i430.167%1l0o913W8_8@7B9q042g9v3`9x2~8d7f8}8 9n9y5E939496989R9H160$0A0x0y0y0o0Y9o3.8I7{4f99720H160d3e0$9u4m9R9S6E0H8g04030c0W2W0c0M8o2u0k1`2x4#9@988d9b9d9*9T7U9$209k9mah3o9A9s8Q9D3.9F875}9A9C9M8T168bax8{8#8~90aB928Aal7^160ZaJ010B0q4Gaq2093959?a99@ab758%ae7B8|aE9L9G8z040%aS3o75a/11890EaN8I020k0V8xa$8MaD9Ka=0189a.aG4ta;a 6P8I0#aNaPaRb79E160EaVa8aXbn8d9`169}0F0o7X0x0U2t0S240c0z0m13a739bnboa%048 77a_7`aN9Ia)b3b5b37f0qbSbj3LbHaXaf9JaFa+9N16b6b)7}b9b-6Ua@bN049)7Zb$bRbharb+bUb/2z9+6UbcbeaQ3=bX04a^aWb!9^b0b%a*ataya-b agbac316bdcm2;bfc7b|aTbYcq9jbOcx7.bK0obMcbcc97af9V9X9Z9#cA9%czb_6E0L9-040G0D0U9=4#06bI9aa!bP9U9W9Y9!b?0pb^c1abcT9/0_cYchb;16blbGccaZ040.2%0x0L9QcHcR9r0=8ocg2+c29fcf7,af0,c-aNbTcu1!cs3?c80)c56w0/6y6%a,drcN20dodudv71c`04dycQ5Edo6xdD8^16dHc:6Ecs4Ududqds4TdLc8cacZaf0g0o0q9K0C0g0U0l0Q0-1(djdz1!b5d!5/a:04d%d)240C0A2r0$0V0H0~c^dc8HcPdQb*a-d_6z11ac0Dc(04db2.dd9j9l7Uel7?bJdidma?c{bZaa9_9{9}d,d.d:1Leyd6ceb{dIbbeae8bJ9s7)7+ev018I8KeT7f0$267je7dwecaAb:3cana6e$dEaH8ab3dBdCdCc80NdPeOb0erdN048WbmeIb.04e31e86e|eMb@ej7Pe.e98Jck9Z0D0l0C6;0U0z8 eieT8Uf1c}f3aC8-8/1W8=7Xc8e)c_deeKfE9waIcFaf24cMeLcnfbd?3P8N76fe6EeVfhbufkfmfobufCft3kcdf48}cXfqfO2;9(ejfMb?aMfR2=9U8Of83uf+aCd}d*eDd/d;eTfXeX7yc+0zfNfHbie;g9aDf.e_7,c!ez5Ebq9|0ce12s0V0{e6c|f*gnf,fGf9fPc/gCe+161Oe3fCbUe,9tgKghe~dxdWdMgRf`8If_e*3Wdoe_f)f gzaCf6fBgVeNemaffdb3g8gYcBfif!0ifnfpf(eHencBfx8:fAf~e/fIggg?4za(b2frfJf2g h904f@g,fQf:b8bKfUg;16eWh83316g^flg`f$f/geb}8ag$17g0fFgjhjgEg.bJhihl3`gWejg*h4gmfv9fg2d gse3e59;hpfgghcKhMhAcvh7h+d{f-f%hcf0glaf7Eh$hrh.fS047sh4e fD2+dhdVf`7fhW0zd+d-g5eGh=e{hK5E0$1}04020+0U7l0T0K0Zilina}i5hNhg0}0.0o0-h$hJh53`ii8himio0IibeF0kisiogk7Gg@0-i0fWhqfh85gOhsd{eui!ewdGeji8e0e2e4e6iveb6PiGikiIa}iqiOiuieejiyiAiCb3i?i{0T0ui-gv9;j4iQ5nhth~iTh`ck137mfVe(j29{8v8l0hbw0lg20c2q2c0X8.8:0e79joa~i%b4hdd`h}h_g7iWgh0Ki iBh=i2e%i=jn8j8l9 1l0xiz0k0D1j9;bBjCjbjHf{jeiU5Eg=h|j-0tjOiZj=8f8hjV0T0Id(gu0%0$0Ej*h=hD8YjdjJjEj;i3bJ1W8Qgcg}iRhgkaj=kcjSg)0S9kki4+0v6 2(6(kw0v6^2B6-1n2EkDjZ1W6*1E2 kz0=0@0_04.
Aufwand formell bestimmen für BubbleSort

Bestimme die Anzahl Vergleiche mathematisch allgemein für N Elemente [anspruchsvoll]