Lexiographische Sortierung in einer while-Schleife

Question

Aufgabe:

Schreiben Sie ein Programm, welches eine Eingabe in der Konsole entgegennimmt und diese in einer while-Schleife buchstabenweise lexikographisch sortiert. Erlaubt sind Zeichen [A-Z], [a-z] sowie die Umlaute ö,ä und ü (Hinweis: Lassen Sie benachbarte Zeichen gegebenenfalls paarweise austauschen)

1. Geben Sie die Zwischenschritte (gesamte teilsortierte Zeichenkette) nach jedem Austausch in der Konsole aus.

2. Geben Sie das Endergebnis der Sortierung in der Konsole aus.

3.Geben Sie anschließend die Anzahl der getätigten Vergleiche in der Konsole aus.

4. Geben Sie mindestens drei begründete Testfälle.

Beschreiben Sie als Kommentar in ihrem Code, wann die while-Schleife in Ihrer Implementierung beendet wird und warum Sie sich dafür entschieden haben. Hinweis: Nicht lauffähige Programme werden mit null Punkten bewertet, dabei gilt als Maßstab NUR die Ausführbarkeit in der Konsole. Wir testen jede Aufgabe gegen jede, finden also Plagiate ⇒ 0 Punkte

Wie kann man das am besten mittels while-Schleife modellieren. Verstehe ich das richtig, dass mit Zwischenschritte angegeben ist, z.B. zuerst nach Großbuchstaben zu sortieren, dann nach Umlauten oder erstmal alles einzelen? Außerdem sollen nicht lauffähige Abgaben abgefangen werden.

Ansatz: Leider mit For-Schleife

eingabe = input ('Eingabe: ')

S = []
x = len(eingabe)
for i in range (0,x):
    S.append(eingabe[i])

print("List is : ",S)


for i in range(0,x):
    for j in range(0,x):
        if S[i]<S[j]:
            temp = S[i]
            S[i]= S[j]
            S[j]=temp
j=""

for i in range(0,x):
    j = j+S[i]

print("After sorting String is : ",j)

Answer 1

Antwort mit KI erzeugt

Lexikographische Sortierung in einer while-Schleife

Für die Aufgabe, eine Eingabezeichenkette buchstabenweise lexikographisch unter Berücksichtigung von Groß- und Kleinbuchstaben sowie den Umlauten (ö,ä,ü) zu sortieren, kann das Bubble-Sort-Verfahren als einfache Lösung angewendet werden. Dabei werden benachbarte Elemente vertauscht, bis die gesamte Liste sortiert ist. Statt einer for-Schleife wird eine while-Schleife für den iterativen Vergleich verwendet.

Um dieses Verfahren in Python umzusetzen, folgt eine detaillierte Beschreibung und Implementierung:

1. Initialisierung: Eine Liste aus den einzelnen Zeichen der Eingabe wird erstellt.
2. Vergleiche und Tausche: Innerhalb einer while-Schleife werden benachbarte Zeichen verglichen und falls nötig getauscht. Dies wird wiederholt, bis ein Durchlauf ohne Tauschoperationen erfolgt, was bedeutet, dass die Liste sortiert ist.
3. Ausgabe: Die Zwischenschritte und das Endergebnis werden ausgegeben. Zusätzlich wird die Anzahl der Vergleiche gezählt und ausgegeben.

Der unten angegebene Code zeigt die Implementierung dieses Ansatzes. Wesentliche Kommentare erklären einzelne Schritte und Entscheidungen:

python
def lexi_sort(string):
    # Konvertiere den Eingabestring in eine Liste von Zeichen
    char_list = list(string)
    n = len(char_list)
    vergleiche = 0  # Zählvariable für die Anzahl der Vergleiche
    swapped = True

    # Der äußere while-Loop läuft, bis kein Tauschvorgang im inneren Loop mehr stattfindet
    while swapped:
        swapped = False
        for i in range(n-1):
            vergleiche += 1  # Erhöhe die Anzahl der Vergleiche
            if char_list[i] > char_list[i+1]:
                # Tausche die benachbarten Zeichen, wenn sie in falscher Reihenfolge sind
                char_list[i], char_list[i+1] = char_list[i+1], char_list[i]
                swapped = True
                print("".join(char_list))  # Ausgabe der aktuellen Liste nach jedem Tauschvorgang

    # Die Schleife endet, wenn während des gesamten Durchlaufs keine Tauschaktion erforderlich war
    print("Final sorted string:", "".join(char_list))
    print("Anzahl der Vergleiche:", vergleiche)

# Eingabe und Ausführung
eingabe = input('Eingabe: ')
lexi_sort(eingabe)

Begründung für die Beendigung der while-Schleife:
Die while-Schleife wird beendet, wenn im letzten Durchlauf keine Tauschoperationen mehr erforderlich sind. Das ist ein Hinweis darauf, dass die Liste vollständig sortiert ist. Diese Bedingung verhindert unnötige Wiederholungen, sobald die Sortierung abgeschlossen ist.

Testfälle:

1. Eingabe: "bBaA"
- Erwartetes Ergebnis: Zeigt den Austauschprozess und "AaBb" als finale Ausgabe.
- Begründung: Großbuchstaben kommen vor ihren entsprechenden Kleinbuchstaben, sortiert nach ihrem ASCII-Wert.

2. Eingabe: "üäö"
- Erwartetes Ergebnis: Sollte als "äöü" ausgegeben werden.
- Begründung: Die lexikographische Sortierung der Umlaute entsprechend ihrer Unicode-Position.

3. Eingabe: "Zebra"
- Erwartetes Ergebnis: Zeigt die Teilsortierungen bis zum Endergebnis "Zabeer".
- Begründung: Die Sortierung erfolgt von A bis Z unter Berücksichtigung der Groß- und Kleinschreibung.