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.

.128013öOesh;qft2lv10g3n[dbIcpmo(ari=])/y:ELk45 ux050t0d0j0B0D0l0e0P0w0l0B0e0e0E010j0D0x010406050e0Q0y0y0B0C0I040L0b0?0r0p050H0?0^0`0|0;0x04051a131d0H1a0;0t0D0m0!0$0(0*0f0D0p0f0l1r0f0j0/050V0u0l0d1m0%0)011q1s1u1s0j1A1C1y0j0C1b0j0f0!0z0Y0x0B0r0*0k011E1o010i0X0d0r0B0y0d1y0e1Y0r1(1G1+1C1.1:0/0a0P0~100p0e0m0z0C0e0w1t0B12141@1b0H1T2g1Q1S1R1z0t1_0*1u0r1-0z0e1y1j1l0#1F2q0D2s0r0z2x1y0x0C0d1b1?1Z2g2M0r2L1@2p012E0C0_0l0/0n132P0:0=2S2z1)2V2X0/0k2#2f0;2P2T2,0B2Y040q2:2N2=2)1n1G2^2`0N2}2Q2 1Z2@272-040O362g2I2K132x2j0t1S2o2*1G0w2F1;1b3k1c2J2R2N3f053r0T3y1^3p0*0w0n0/030P0d280j0d0Z0K1C1:0r0j0P0f0B3W0v0r0T0R0J0P0o3f383F310*0M0/0D0i3f0P2(393G2U0/0t2u1-3A2?3|0.040s42302A010y0D0/3+2e3z433/01450F3^3`3.4a0z0/020l0j0g4n4i4a0r3~400r483{4j45474g2Q4o2T4c2Z4E4p1)4l0J3,0P4V3_4y2+0u0/2I2C0j4P2T450A4)3|0e1$04020h0Q0z4v2_1C0Z0z0M4=4@4v4-4G0/0G3,4L3|3;040d0Y0d524a454T4J0:4W4X494Z4#0C4%5e4R0/4,5i574j4/4s4?4^0g0i2_290f1D0c0C0t0r0Q114 5B5r1G45555i0;0H3C3i1g3x3j1k3l2j2m2h0B1B5Y3k5V0T0V0X0e04.
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.

.128013öäeshuftlv10g3n[dbVcpmoari=]/wyEzLS 2050r0d0i0y0A0j0e0K0u0j0y0e0e0B010i0A0v010406050e0g0w0w0y0z0F040I0b0-0p0n050D0-0/0;0?0+0v0405140}170D140+0r0A0k0U0W0Y0!0f0A0n0f0j1l0f0i0)050P0s0j0d1g0X0Z011k1m1o1m0i1u1w1s0i0z150i0f0U0x0S0v0y0p0!0L011y1i010h0R0d0p0y0w0d1s0e1S0p1Y1A1#1w1(1*0)0a0K0^0`0n0e0k0x0z0e0u1n0y0|0~1.150D1N2a1K1M1L1t0r1:0!1o0p1%0x0e1s1d1f0V1z2k0A2m0p0x2r1s0v0z0d151-1T2a2G0p2F1.2j012y0z0:0j0)0l0}2J0*0,2M2t1Z2P2R0)0L2V290+2J2N2$0y2S040o2*2H182D2a2r2d0r1M2i2!1A0u2z1+152|162`2Y2^282^330N2L1T2.0)0i0d0w0v2@2K0K3a1/310!0x0)0B3o043q2-3t2O0)0r2o1%3y3r2N0(040q3I3B1h1A0w0A0)0m3O2Z3Q0!3L0C3y3A3X2u010u0l0)030K3k3m210c2D0K0t0;0A0y1v1x0.0K0r0X0K0G1w1*0p0i0K0H0E0A230f1%0H0g1-0d0A240d0z0p3y2,3(2#3E3G4o3c2K3J3C3L3N4w3g3s3Y013S3U3W3h4z0)3#4C3%4K4F3v043x4O4y4F0p4t0e3H4C4W3)4A4J4E3)4H042U4$3P4(4M3$4%1Z3+3-490E4j3k0T3h1d1x0J3k0j1w0K200w0K4m0e3k4v2W4q4Q3)4Y043F4!5f294^1A4)4:4r3R3T4.4*3K4?4V4;1Z4S4U2W4P4+4s043:3n4C0+0D3e2E2_5R0D372b2~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.

.128013öeshä;ft2lv16g3-n[dbVc+pmo(ari=])/wy:EzLkS45 u050t0c0i0C0E0k0d0T0w0k0C0d0d0F010i0E0y010406050d0U0z0z0C0D0K040O0b0_0r0o050I0_0{0}0 0@0y04051d161g0I1d0@0t0E0l0%0)0+0-0e0E0o0e0k1u0e0i0=050Y0u0k0c1p0*0,011t1v1x1v0i1D1F1B0i0D1e0i0e0%0A0#0y0C0r0-0j011H1r010h0!0c0r0C0z0c1B0d1#0r1+1J1.1F1;1?0=0a0T11130o0d0l0A0D0d0w1w0C15171`1e0I1W2j1T1V1U1C0t1|0-1x0r1:0A0d1B1m1o0(1I2t0E2v0r0A2A1B0y0D0c1e1_1$2j2P0r2O1`2s012H0D0|0k0=0m162S0?0^2V2C1,2Y2!0=0j2(2i0@2S2W2/0C2#040p2?2Q2^2,1q1J2{2}0R302T321$2`2a2:040S392*2_2-353e2|0=0n3i1h2M2j2A2m0t1V2r3l0-0w2I1@1e3v1f3t2+2Q3r3C0W2U3c3A010P0=0h2a3i0T3J1{3Q0r0=0E3W3Y2W0A0J3$0r3(3k340-0r0u0=0D1$0o0c3r3:2D010;040B3}333 3?0=1 443P3;400=432h3K3~2.0=0t2x1:4a3Z4c410H4o3*0=0q4t3Q0z0E2$4x4q0=0H0L3i06060T4K3X4i1J3S040E0h3/454j044l0d4n4g2T3)3Q410s4C463$4*1,410G4T4b3 0A0=020o0i0g4;4p4+4W4m3.4!3O4~4.0=4)534$4c3#4Q4-1J4@040x5e0-4z4B594N0-4/4G534J4L5u5a4 0i0c0z0y4}4u040F5C3!4k515j4d04582)5w4V3%5n4U1J4/5G4c0w0m0=030T5y5A2a0f2M0T0v0}0E0C1E1G0`0T0t0*0T0M1F1?0r0i0T0N0J0E2c0e1:0N0U1_0c0E2d0c0D522)5t5u4K5P355I4Y6f2i6k5p575K5c5R5O5o5L4:534M5T0-5g5F6A6q2X6m4Z6w6C5L5N6p6x6u5K5g5i5S4=1,5l042%6V555U0=6z2)6B6W1J5Y5!600J6a5y0$3c1m1G0Q5y0k1F0T290z0T6d0d5y6o316i4L6H5c4X6K6P6M4(6t4,6#2W5V6G6x6E5W5x5z5B5s163M2N3s7w0I3G2k3x162n7D5: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öesh;98ft2lv1760g3-n[dbc+pmo(ari=])/wy:ELk45D u050w0c0j0E0G0l0d0U0y0l0E0d0d0H010j0G0A010406050d0V0B0B0E0F0M040P0b0`0u0r050K0`0|0~100^0A04051e171h0K1e0^0w0G0m0(0*0,0.0e0G0r0e0l1v0e0j0?050Z0x0l0c1q0+0-011u1w1y1w0j1E1G1C0j0F1f0j0e0(0C0$0A0E0u0.0k011I1s010i0#0c0u0E0B0c1C0d1$0u1,1K1/1G1=1@0?0a0U12140r0d0m0C0F0d0y1x0E16181{1f0K1X2k1U1W1V1D0w1}0.1y0u1;0C0d1C1n1p0)1J2u0G2w0u0C2B1C0A0F0c1f1`1%2k2Q0u2P1{2t012I0F0}0l0?0U0n172T0@0_2W2D1-2Z2#2%0k2*2j0^2T2X2;0E2$040U0s2^2R2`2.1r1K2}2 0U0R332U351%2|2b2=300S3d2,2{2/383i2~2%0p3m3f1|3p0.392%0o3v2-3g3y2Y3r3a0h3D3o373z3I2%0g3L362E3H2!3s040n0q3S3F3N3V3j0n2)2i343E3x3%3A3Y2@3,3e3.3h3W2 0n323@2k2M2O172B2n0w1W2s3G0y2J1^1f441g2N2V2R3m054a0X4h3/3U0Q0?0X0i3m0U3_3G0u0i0?0x0V0x1F0c0d2b0j4j3M3U0=040D4J3T2:4r0E0j1;4P3$4L0?0J0N3v0U4%4v4K1-4q040i2b4u4w3:0?0V4:4*1K0C0L0?2G4^4Q380x0?0F1%0r0c4W4o1-4M4O3 4;3U0u520420582X5b5k4x4S4U0u5n3%4M0J4!3v064(5z4)500.0y0n0?030U0O2G0U0T0V0F2e0r554$5A4%5e4+0?4.0F4 4X4R040G5!594`4|5%5r3 5B5#515355575d4_0.5m5_5C2Y5h5j5}5;5{0?5c2+5V385p4V625*64040J5)2X0C0?0t6h3G0B0G0?3+675`015u4#3 065y5T5A680.4,0G4t5/6C2Y6a5.6s5~4M0v5s5f4}6Q5a0?0I6m3%6j04020r0j0f6X6R040w4T6b6M636u0?6P6c2|6S6H6t6Z0z6)1-6o6q6T1K4M0I6w2+6z6A6A6I5E5G0U0m0c0F0Z0V2d0e1;0U0u0b0:2h7779796I0u0?4U0B0A6~4`0?0H7B3z6K726e6?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,2N0j5N7!2R8D5o7Y7_6x174l421k4g431o452n2q2l0E4E2k440^0K0X0Z0#0d04.
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

.128013öesh;98fTt2lv1760g3-n[dbcFpm+o(ari=])/wy:jELk45D u050x0c0k0G0I0m0d0X0z0m0G0d0d0J010k0I0B010406050d0Y0C0C0G0H0O040S0b0}0v0s050M0}0 11130{0B04051h1a1k0M1h0{0x0I0n0+0-0/0;0e0I0s0e0m1y0e0k0_050$0y0m0c1t0.0:011x1z1B1z0k1H1J1F0k0H1i0k0e0+0E0)0B0G0v0;0l011L1v010i0(0c0v0G0C0c1F0d1)0v1/1N1=1J1^1`0_0a0X15170s0d0n0E0H0d0z1A0G191b1~1i0M1!2n1X1Z1Y1G0x200;1B0v1@0E0d1F1q1s0,1M2x0I2z0v0E2E1F0B0H0c1i1}1*2n2T0v2S1~2w012L0H100m0_0X0o1a2W0`0|2Z2G1:2$2(2*0l2-2m0{2W2!2@0G2)040X0t2{2U2}2;1u1N30320X0U362X381*2 2e2^330V3g2/2~2=3b3l312*0q3p3i1 3s0;3c2*0p3y2:3j3B2#3u3d0h3G3r3a3C3L2*0g3O392H3K2%3v040o0r3V3I3Q3Y3m0o2,2l373H3A3*3D3#2`3/3h3;3k3Z320o353`3q3W2?3S3#3f423z3}3,3o493|3J3@0o3x4e3P3X4h3F4k443t3~0_0o3N421l2Q2n2E2q0x1Z2v3J0z2M1{1i4A1j4y3;2V2m054G0!2Y3)3X0T0_0!0i3p0X4f3?0i0_0y0Y0y1I0c0d2e0k3p4$3X0^040F4=4l2?4X0G0k1@4{4q0;4^0L0P3y060X5a4#4|1N4W040i2e4!4?4}040Q5j5d0;0E0N0_2J5o532#0y0_0H1*0s0c524U1:4^4`4w5p5x0_235E3=4@0_5I2.5k3b4~500v5O2!5556585b5(5c5w0v0_0d0N0G0B0B0c0x5v5F1N0E0_0J5^5P1:0T0z0_0A310d5D495)5b5U0;0z0o0_030X0R2J0X0W0Y0H2h0s5B3y695a6b015f5h0H5~2 5t6z3J5r5t5Y425*5_3C5y045A18675T5K5H5Z4g6L5N5J5w6S6X6J2#5W516!5 1N556C3*5{040u6-3X0C0I4t6T3*5557686s5(6u5f0I4Z6H6u5,040x4 6(6Q6Y0_0w6`4m6B6)5!0_0K6=1:6/020s0k0f7n5V787a6G7c6#4^7f7j4g7i2.6I6*5q0_0D7u0;6@6_7D6{7l6}2.596 6s6u6d6f0X0n0c0H0$0Y2g0e1@0X0v0b0?2k7U7W7X5K77500C0B7M016/5}757_6%7y4P6R7e7g5l0I896+7l6r7@5)76848c54887Q7h048b8n5G8e825w807~77795X8k017B8B778q7G6u6/7L8u6#7O3#8B4^7m6~8g6a837w8A8r8d047C7z7I6$8p7~8J7~8N3.8$7k048R8H5K8w8L8%7`0c7|8f8T6t8V5.5:5=5@8_2!8^8?5w610_0j0H0Y6P2|7V69715t74996#77925;5?8*5|819n8%9b04640)9g2U6u4^7T2|8T9k040y2Q0G0T5%8U9a5z0#6m852U7H6A8W7b2|1a4R2R4x9(0M4K2o4C1a2r9/0G4-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.

.128013öeuhq9Tt_l3-dcFmo(a]Z:LG5D B2xäs;f1v760gn[Wb+pri=)/wyjPEz,k.S48050n0c0i0t0W0k0G0B0o0k0t0G0G0X010i0W0U010406050G0d0q0q0t0V0#040x0b1a0P0O050Z1a1c1e1g180U04051u1n1x0Z1u180n0W0K0{0}0 110e0W0O0e0k1L0e0i16050?0S0k0c1G0~10011K1M1O1M0i1U1W1S0i0V1v0i0e0{0r0_0U0t0P110D011Y1I010I0^0c0P0t0q0c1S0G1_0P1 1!221W2527160a0B1i1k0O0G0K0r0V0G0o1N0t1m1o2b1v0Z1;2A1.1:1/1T0n2d111O0P240r0G1S1D1F0|1Z2K0W2M0P0r2R1S0U0V0c1v2a1`2A2*0P2)2b2J012Y0V1d0k160B0J1n2-17192:2T202?2^2`0D2}2z182-2;340t2_040B0l382+3a311H1!3d3f0B0.3j2.3l1`3c2r353g0z3t2 3b323o3y3e2`0M3C3v2c3F113p2`0L3L303w3O2=3H3q0/3T3E3n3P3Y2`0g3#3m2U3X2@3I040J0N3,3V3%3/3z0J2|2y3k3U3N3`3Q3=373 3u413x3:3f0J3i473D3-333)3=3s4f3M4a3|3B4m493W440J3K4r3$3.4u3S4x4h3G4b160J3!4C3_4z4j0J3+4J424L4F040D3@4P4o3;0D3~2~4n4t4j0D464#4s434(4e4+4y4i4S0D4l4:4D3(4?4q4_4K4=3z0D4w4~4Q504Y4B544X3f0D4I594%4?4O5e4-4S0l4V5i4R3z0l4!394,5o3;0l4*5s4;4E5p4/5y4`3{5v4^5D4 5A5v4}5I555K3f0l535N5a160l585T5f5p5d5Y5j5p5h5$5u3f0.5m5*565,5r405z4{3z0.5x5?5E440.5C5|5J5^3;0.5H615O635,5M675U040.5S6c5Z645X6h5%645#6l5+160.5)6p5:160z5.6u5P6w5=485@5F3f0z5{6D5}4j0z606J626F6w666O686Q040z6b6T6d0z6g2.1y2%2A2R2D0n1:2I3W0o2Z281v6+1w6)412,2z056;0;2/6P0+0P160W0q0U2r0i3C0B5t3374041d0i0U0k0r0i1O0S0,0U0#7j7l7b7d1!0+160~7u6E0P7f7j7a4W3W737577797A5}7f13273^6U7I0476780V7F2~7c7B7f0V1`0n0r0q3L4$4316220O6C3g7v110r160X7M6P7f0%0#2Z0W0;0%7k7Y6}6E15040s3C7@010G0J1602030l0g0H7:0d2%0j0S0G7X0J8i8k0H8c88160Y7R3c7/1L7=8d7_040,8y5}160?0V0O0=8L6P890s8B4m7-3.7x040;0I7|6U0P0I160S0d0S1V0c0G7L4f8d8U8S8)160n0t0i248`2;890Y0w7,0B977!5E8!0I2r8(8D040$9e3W0r0!750P9i430S167%1l0c913W8_8@7B9q042g9v3`9x2~8d7f8}8 9n9y5E939496989R9H160G0!0t0U0U0c0n9o3.8I7{4f99720o160p3e0G9u4m9R9S6E0o8g04030B0(2W0B0A8o2u0O1`2x4#9@988d9b9d9*9T7U9$209k9mah3o9A9s8Q9D3.9F875}9A9C9M8T168bax8{8#8~90aB928Aal7^160maJ010q0W4Gaq2093959?a99@ab758%ae7B8|aE9L9G8z040QaS3o75a/11890uaN8I020O0i8xa$8MaD9Ka=0189a.aG4ta;a 6P8I0TaNaPaRb79E160uaVa8aXbn8d9`169}0K0c7X0t0d2t0e240B0P0b13a739bnboa%048 77a_7`aN9Ia)b3b5b37f0WbSbj3LbHaXaf9JaFa+9N16b6b)7}b9b-6Ua@bN049)7Zb$bRbharb+bUb/2z9+6UbcbeaQ3=bX04a^aWb!9^b0b%a*ataya-b agbac316bdcm2;bfc7b|aTbYcq9jbOcx7.bK0cbMcbcc97af9V9X9Z9#cA9%czb_6E0+9-040h0V0d9=4#06bI9aa!bP9U9W9Y9!b?0Xb^c1abcT9/0_cYchb;16blbGccaZ040S2%0t0+9QcHcR9r0=8ocg2+c29fcf7,af0I0c0k0n0y0V1j9;db2.ddcyb@aNbTcu1!cs3?c80*c56w0N6y6%a,dCcN20dzdFdG71c`04dJcQ5Edz6xdO8^16dSc:6Ecs4UdFdBdD4TdWc8cacZaf0)0c0W9K0j0)0d0I0F0k1(c-dvb+d/5/a:04d=d@240j0!2r0G0i0o0~c^dc8HcPd#b*a-e36z11ac0Vc(04dq7?6Eaj7UevdscBdidkdmdob(c_aH04c|3kcd6Pbq9|0Bd`d|d~1LbZaabJdfdK1!9(et9s7)7+dxaK8Jck0G267jehdHemaAb:3cana6e=dPeJe^eI3WdMdNdNc80Yd!eibJevdY048Wbmd6b0ed1e86f95Ee$e!3P8N76e}eje-e+2=169Z0V0I0j6;0d0P8 esfv8Ufec}fgb.d08.8:8=7Xc8f02+b`b2fHaIcFaf24cMdTbbekflfM7Pfsex168Kfv7DbufAfCfEbufSfJeMeXcebwf`fo01fnf%aCf#b?aMg27ffifRfZbJe7d^eSd}d fv8If:e_b804cKg7fX8ack8}cXfGgobifd7,c!f~eO9{9}eb2s0i0{egeL3ueNaCeZg52;g4el7}av0WedfSbUe{9tg!f;16fbdId+dXg,g28Ig9gz3.dzf6f|gOgEaCgcfkdrftc/f*aCf,b3gmckfyf@0rfDfFf{eWfLaC8-8/1WfQg e~9wazgvb{g?cvgBgeb0gsgSdth2h0bJh5glf/h8f?fBhbf_gyf1gA8VhfeB4za(gxe0ga16hxgVcn04g=hY9fg~hPd;d?d^gIedef9;h6hFg)gqc+0Pf$hMb}guh?gwg1hs1!93gCaf7Eh;fui1fp047shmfcfTe?fMeDdldn0 eHfUg/hycBgge9gieUbFinemf8hB5E0G1}04020f0d7l0H0E0miEiGa}d*hV9B0t0Sdji7hAhn3`iB8hiFiH0vd{gj1LiLiHf68Cgpi6hEi8h{33fx85g(i9fw04iieFilg+ixetir0PeaeceeegiOip3.iYiDi!a}iJi*iNgtiyewb00}iS0kiUb3jcjh0H0Rj6gL9;jti,7GcBi/i`h7h?137mf-e@jr9{8v8l0xbw0Igg0B2q2c0CfO1W0-79jNa~i`i3jBhRib0kidf.i;iwfM0EjniTgtifiWjbjM8j8l9 1liR0c0Oik9;bBj#jA5ni?j+j-fmh=i`7f0#j?jpj^jL8hj}0H0vh+0B0Q0G0uk7gtg`4gfMjDi=e#kekBia1W8Qh_hej)kakAj:hZgnkEi{0G0e9kkJ4+0Z6 2(6(kZ0Z6^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.

.128013öeuhq9Tt_l3-dcFmo(a]Z:L5D B2xäs;f1v760gn[Wb+pri=)/wyjNPEz,k.S48050n0c0i0t0V0k0F0A0o0k0t0F0F0W010i0V0T010406050F0d0q0q0t0U0!040x0b1a0O0N050Y1a1c1e1g180T04051u1n1x0Y1u180n0V0J0{0}0 110e0V0N0e0k1L0e0i16050?0R0k0c1G0~10011K1M1O1M0i1U1W1S0i0U1v0i0e0{0r0_0T0t0O110C011Y1I010H0^0c0O0t0q0c1S0F1_0O1 1!221W2527160a0A1i1k0N0F0J0r0U0F0o1N0t1m1o2b1v0Y1;2A1.1:1/1T0n2d111O0O240r0F1S1D1F0|1Z2K0V2M0O0r2R1S0T0U0c1v2a1`2A2*0O2)2b2J012Y0U1d0k160A0I1n2-17192:2T202?2^2`0C2}2z182-2;340t2_040A0l382+3a311H1!3d3f0A0.3j2.3l1`3c2r353g0y3t2 3b323o3y3e2`0L3C3v2c3F113p2`0K3L303w3O2=3H3q0/3T3E3n3P3Y2`0g3#3m2U3X2@3I040I0M3,3V3%3/3z0I2|2y3k3U3N3`3Q3=373 3u413x3:3f0I3i473D3-333)3=3s4f3M4a3|3B4m493W440I3K4r3$3.4u3S4x4h3G4b160I3!4C3_4z4j0I3+4J424L4F040C3@4P4o3;0C3~2~4n4t4j0C464#4s434(4e4+4y4i4S0C4l4:4D3(4?4q4_4K4=3z0C4w4~4Q504Y4B544X3f0C4I594%4?4O5e4-4S0l4V5i4R3z0l4!394,5o3;0l4*5s4;4E5p4/5y4`3{5v4^5D4 5A5v4}5I555K3f0l535N5a160l585T5f5p5d5Y5j5p5h5$5u3f0.5m5*565,5r405z4{3z0.5x5?5E440.5C5|5J5^3;0.5H615O635,5M675U040.5S6c5Z645X6h5%645#6l5+160.5)6p5:160y5.6u5P6w5=485@5F3f0y5{6D5}4j0y606J626F6w666O686Q040y6b6T6d0y6g2.1y2%2A2R2D0n1:2I3W0o2Z281v6+1w6)412,2z056;0;2/6P0+0O160V0q0T2r0i3C0A5t3374041d0i0T0k0r0i1O0R0,0T0!7j7l7b7d1!0+160~7u6E0O7f7j7a4W3W737577797A5}7f13273^6U7I0476780U7F2~7c7B7f0U1`0n0r0q3L4$4316220N6C3g7v110r160W7M6P7f0%0!2Z0V0;0%7k7Y6}6E15040s3C7@010F0I1602030l0g0G7:0d2%0j0R0F7X0I8i8k0G8c88160X7R3c7/1L7=8d7_040,8y5}160?0U0N0=8L6P890s8B4m7-3.7x040;0H7|6U0O0H160R0d0R1V0c0F7L4f8d8U8S8)160n0t0i248`2;890X0w7,0A977!5E8!0H2r8(8D040#9e3W0r0Z750O9i430R167%1l0c913W8_8@7B9q042g9v3`9x2~8d7f8}8 9n9y5E939496989R9H160F0Z0t0T0T0c0n9o3.8I7{4f99720o160p3e0F9u4m9R9S6E0o8g04030A0(2W0A0z8o2u0N1`2x4#9@988d9b9d9*9T7U9$209k9mah3o9A9s8Q9D3.9F875}9A9C9M8T168bax8{8#8~90aB928Aal7^160maJ010q0V4Gaq2093959?a99@ab758%ae7B8|aE9L9G8z040PaS3o75a/11890uaN8I020N0i8xa$8MaD9Ka=0189a.aG4ta;a 6P8I0SaNaPaRb79E160uaVa8aXbn8d9`169}0J0c7X0t0d2t0e240A0O0b13a739bnboa%048 77a_7`aN9Ia)b3b5b37f0VbSbj3LbHaXaf9JaFa+9N16b6b)7}b9b-6Ua@bN049)7Zb$bRbharb+bUb/2z9+6UbcbeaQ3=bX04a^aWb!9^b0b%a*ataya-b agbac316bdcm2;bfc7b|aTbYcq9jbOcx7.bK0cbMcbcc97af9V9X9Z9#cA9%czb_6E0+9-040h0U0d9=4#06bI9aa!bP9U9W9Y9!b?0Wb^c1abcT9/0_cYchb;16blbGccaZ040R2%0t0+9QcHcR9r0=8ocg2+c29fcf7,af0$c-aNbTcu1!cs3?c80*c56w0M6y6%a,drcN20dodudv71c`04dycQ5Edo6xdD8^16dHc:6Ecs4Ududqds4TdLc8cacZaf0)0c0V9K0j0)0d0H0E0k1(djdz1!b5d!5/a:04d%d)240j0Z2r0F0i0o0~c^dc8HcPdQb*a-d_6z11ac0Uc(04db2.dd9j9l7Uel7?bJdidma?c{bZaa9_9{9}d,d.d:1Leyd6ceb{dIbbeae8bJ9s7)7+ev018I8KeT7f0F267je7dwecaAb:3cana6e$dEaH8ab3dBdCdCc80XdPeOb0erdN048WbmeIb.04e31e86e|eMb@ej7Pe.e98Jck9Z0U0H0j6;0d0O8 eieT8Uf1c}f3aC8-8/1W8=7Xc8e)c_deeKfE9waIcFaf24cMeLcnfbd?3P8N76fe6EeVfhbufkfmfobufCft3kcdf48}cXfqfO2;9(ejfMb?aMfR2=9U8Of83uf+aCd}d*eDd/d;eTfXeX7yc+0OfNfHbie;g9aDf.e_7,c!ez5Ebq9|0Ae12s0i0{e6c|f*gnf,fGf9fPc/gCe+161Oe3fCbUe,9tgKghe~dxdWdMgRf`8If_e*3Wdoe_f)f gzaCf6fBgVeNemaffdb3g8gYcBfif!0rfnfpf(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`7fhW0Od+d-g5eGh=e{hK5E0F1}04020f0d7l0G0D0milina}i5hNhg0}0R0c0kh$hJh53`ii8himio0vibeF0Nisiogk7Gg@0ki0fWhqfh85gOhsd{eui!ewdGeji8e0e2e4e6iveb6PiGikiIa}iqiOiuieejiyiAiCb3i?i{0G0Qi-gv9;j4iQ5nhth~iTh`ck137mfVe(j29{8v8l0xbw0Hg20A2q2c0B8.8:0-79joa~i%b4hdd`h}h_g7iWgh0Di iBh=i2e%i=jn8j8l9 1l0tiz0N0U1j9;bBjCjbjHf{jeiU5Eg=h|j-0!jOiZj=8f8hjV0G0vd(gu0P0F0uj*h=hD8YjdjJjEj;i3bJ1W8Qgcg}iRhgkaj=kcjSg)0e9kki4+0Y6 2(6(kw0Y6^2B6-1n2EkDjZ1W6*1E2 kz0=0@0_04.
Aufwand formell bestimmen für BubbleSort

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