QWERTY Sort

Bei Problem 7 bei HP Codewars war 2011 ein „QWERTY Sort“ zu implementieren, wofür die Teilnehmer damals 7 Punkte bekamen. Die Besonderheit bei diesem Sortieralgorithmus ist, dass eine Liste von Elementen nicht alphabetisch sortiert wird, sondern die Sortierung der Buchstabenfolge auf einer Tastatur mit US-amerikanischem Layout (Z und Y sind vertauscht) folgen soll.

Die Begründung für diese abwägige Aufgabenstellung ist ziemlich schräg, aber das Problem ist lösbar, wenn es auch etwas länger gedauert hat:

# URL http://www.hpcodewars.org/past/cw14/problems/ProblemSet2011Final.pdf
# Problem: 7. QWERTY Sort (7 P)

# Sortierschluessel
ordnung = [a for a in "QWERTYUIOPASDFGHJKLZXCVBNM"]

data = """ARREST
SUBDIVISION
DISCONTENT
SUPERIOR
TOPOLOGY
DEBUNK
APPENDIX
SUBDUE
TRUNK
."""


def liste_sortieren(liste,ordnung):
    ''' Diese Funktion erledigt die Sortierung
    und gibt die sortierte Liste zurueck

    '''
    while True:
        # Wenn die Liste sortiert ist,
        # bleibt das beim Durchlauf auf True
        sortiert = True
        
        # Iterier über die Liste
        for i in range(len(liste)):
            # Prüfe 2 benachbarte Listenelemente,
            # ihre Buchstaben von vorn nach hinten,
            # wenn die Buchstaben gleich, dann weiter
            # sonst
            # a.) bekomme für den Buchstaben1 den Listenindex,
            # b.) bekomme für den Buchstaben2 den Listenindex,
            # wenn a > b, dann tausche
            # sonst bleibt es so
            try:
                for id in range(len(liste[i])):
                    
                    if liste[i][id] == liste[i+1][id]:
                        pass
                    else:
                        if ordnung.index(liste[i][id]) > ordnung.index(liste[i+1][id]):
                            # print("Tausche!",liste[i],liste[i+1])
                            # print("Pruefe gerade:",liste[i][id],liste[i+1][id])
                            # Dreh die beiden Elemente in der Liste um
                            liste[i], liste[i+1] = liste[i+1], liste[i]
                            # print("Getauscht:",liste[i],liste[i+1])
                            # Liste war noch nicht sortiert (!)
                            sortiert = False
                        break  
            except IndexError:  # Ende der Liste erreicht
                pass
            # gehe zum nächsten Listenpaar

        if sortiert == True:
            return liste             # Brich ab!!!
            # Normal break, dann Ausgabe, hier return,
            # weil in eine Funktion gepackt


# Bekomm die Werte
data = data.split("\n")
liste = []
for zeile in data:
    if not zeile == ".":
        liste.append(zeile)


# Liste soll sortiert werden
# Da es nur "eine" Liste gibt,
# brauche ich die nicht an die Funktion zu binden,
# also nicht liste = liste_sortieren(liste,ordnung)
liste_sortieren(liste,ordnung)

# Elemente der Liste werden ausgegeben        - - - Ausgabe
for item in liste:
    print(item)

Naja, noch frage ich mich, ob ein alternatives Sortierverfahren die Aufgabe performanter lösen könnte. Im Kern kopiere ich hier eine Abwandlung des Bubblesort-Algorithmus, wobei meine Implementierung nicht sehr performant ist, weil - wie mir scheint - nicht jeder mögliche Tausch vorgenommen wird.