Programmieren mit Harald R. Haberstroh

Erweitern Sie die Klasse IntList aus dem letzten Beispiel (Liste von ganzen Zahlen (POS1: 2BHIF)) um Sortiermethoden:

1. void sel_sort() ... Sortieren mit Selection Sort.
2. void bubble_sort() ... Sortieren mit Bubble Sort.
3. void ins_sort() ... Sortieren mit Insertion Sort.
4. void sort() ... Sortieren mit der Methode java.util.Arrays.sort() von Java.

Im folgenden finden Sie die Algorithmen in Python formuliert.

Selection Sort

Suche das minimale Element und tausche es mit dem ersten Element. Setze den Algorithmus mit dem Rest der Liste fort (d.h. suche beginnend mit dem 2. Element das Minimum und tausche es mit dem 2. Element), bis das letzte Element erreicht wurde.

def sel_sort(seq):
    """sort the mutable sequence (list) in place with selection sort.
       seq MUST BE A MUTABLE SEQUENCE.
 
       As with list.sort() and random.shuffle this does NOT return 
    """
    for i in range(0, len(seq)-1):
        mn = min(range(i, len(seq)), key=seq.__getitem__) # find minimal item
        seq[i], seq[mn] = seq[mn], seq[i]

Bubble Sort

Gehe alle Elemente der Liste durch und vertausche jeweils zwei benachbarte Elemente, falls das erste der beiden größer als das zweite ist. Setze das ganze fort, bis nicht mehr vertauscht wurde.

def bubble_sort(seq):
    """Inefficiently sort the mutable sequence (list) in place.
       seq MUST BE A MUTABLE SEQUENCE.
 
       As with list.sort() and random.shuffle this does NOT return 
    """
    changed = True
    while changed:
        changed = False
        for i in range(len(seq) - 1):
            if seq[i] > seq[i+1]:
                seq[i], seq[i+1] = seq[i+1], seq[i]
                changed = True

Insertion Sort

Jedes Element wird in den bereits sortierten Bereich an der richtigen Stelle eingefügt. Der verbleibende Rest des sortierten Bereichs wird nach hinten geschoben. Die Stelle, an die ein Element eingefügt werden muss, wird von hinten aus gesucht, damit das Nach-hinten-schieben in der selben Schleife erfolgen kann (sonst hätte man immer zwei Schleifen, eine zum Suchen und eine zweite zum Verschieben).

def ins_sort(seq):
    """Sort the mutable sequence (list) in place with insertion sort.
       seq MUST BE A MUTABLE SEQUENCE.
 
       As with list.sort() and random.shuffle this does NOT return 
    """
    for i in range(1, len(seq)):
        j = i-1 
        key = seq[i]
        while (seq[j] > key) and (j >= 0):
            seq[j+1] = seq[j]
            j -= 1
        seq[j+1] = key

Labels: algorithmen, Aufgabe, Java, POS1-2, Python