Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- ef:algorithmen:sortieralgorithmen [2024/04/18 14:58] – angelegt lehmannr
+++ ef:algorithmen:sortieralgorithmen [2026/01/08 13:49] (aktuell) – lehmannr
@@ Zeile 1: / Zeile 1: @@
+====== Sortieralgorithmen in Python ======
+==== Bubble-Sort Algorithmus ====
+** Idee: ** Man vergleicht die ersten beiden Elemente. Wenn die Reihenfolge falsch ist, dann tauscht man sie. Danach wandert man eine Stelle nach rechts und vergleicht das zweite und das dritte Element und tauscht diese gegebenenfalls. Dies wiederholt man bis man am Ende der Liste angekommen ist. Danach beginnt man wieder von vorne und geht bis zum vorletzten Element (warum?). Dies wiederholt man n mal.
 <sxh python>
-# webtigerjython
+def bubbleSort(list1):
+    for i in range(len(list1)-1,0,-1): #i läuft rückwärts
+        for j in range(0,i,1):
+            drawList(list1,0.01)
+            if list1[j]>list1[j+1]:
+                list1[j],list1[j+1] = list1[j+1],list1[j]
-from gpanel import *
+bubbleSort(zufallsListe)
-import random
+</sxh>
-import time
-makeGPanel(0,600,0,400)
+==== Selection-Sort ====
+**Idee:** Man sucht das kleinste Element und setzt es ganz nach links. Danach sucht man im Rest der Liste das kleinste Element und setzt es an die zweite Stelle etc.
-# Liste der Zahlen von 0 bis 99 in zufälliger Reihenfolge
-zufallsListe = random.sample(range(0,100),100)
-setColor("red")
+<sxh python>
 #===============================================================
-# Hilfsfunktion drawList, zeichnet ein Diagramm einer Liste
+# Selection-Sort (Children-Sort)
 #===============================================================
-def drawList(l,sleeptime):
+def getSmallestIndex(Liste1):
-    clear()
+    smallestElement = Liste1[0]
-    x = 20
+    smallestIndex = 0
-    lineWidth(5)
+    for i in range(len(Liste1)):
-    for i in l:
+        if Liste1[i] < smallestElement:
-        line(x,30,x,i+30)
+            smallestElement = Liste1[i]
-        x = x + 5
+            smallestIndex = i
-    time.sleep(sleeptime)
+    return smallestIndex
+def selectionSort(Liste1):
+    for i in range(len(Liste1)):
+        drawList(Liste1,0.1)
+        index = getSmallestIndex(Liste1[i:]) + i
+        Liste1[i],Liste1[index] = Liste1[index],Liste1[i]
+</sxh>
+==== Swap-Sort ====
+<sxh python>
+def nAreSmaller(list1, n):
+    howMany = 0
+    for i in list1:
+        if (i<n):
+            howMany = howMany + 1
+    return howMany
-def bubbleSort(list1):
+def swapSort(list1):
-    for i in range(len(list1)-1,0,-1): #i läuft rückwärts
+    index = 0
-        for j in range(0,i,1):
+    while index<len(list1):
-            drawList(list1,0.01)
+        drawList(list1,0.1)
-            if list1[j]>list1[j+1]:
+        element = list1[index]
-                list1[j],list1[j+1] = list1[j+1],list1[j]
+        nSmaller = nAreSmaller(list1,element)
+        list1[index],list1[nSmaller] = list1[nSmaller],list1[index]
+        if (index == nSmaller):
+            index = index + 1
+</sxh>
-bubbleSort(zufallsListe)
+==== Merge-Sort ====
+<sxh python>
+def merge(l1,l2):
+    c = []
+    while len(l1) != 0 and len(l2) != 0:
+        if l1[0] < l2[0]:
+            c.append(l1[0])
+            l1.remove(l1[0])
+        else:
+            c.append(l2[0])
+            l2.remove(l2[0])
+    if len(l1) == 0:
+        c += l2
+    else:
+        c += l1
+    return c
+def mergesort(list1):
+    if len(list1) == 0 or len(list1) == 1:
+        return list1
+    else:
+        middle = int(len(list1)/2)
+        a = mergesort(list1[:middle])
+        b = mergesort(list1[middle:])
+        return merge(a,b)
 </sxh>