Wie sortiere ich einen String Alphabetisch ohne Sort-Funktion in Python?
String (adbx) alphabetisch sortieren
5 Antworten
Wie schon erwähnt, solltest du dir mal Sortieralgorithmen ansehen. Ansonsten habe ich mal ein Beispiel für einen ganz schlechten Algorithmus erstellt. Dabei werden die Buchstaben zufällig angeordnet und das so oft, bis sie sortiert sind. D. h. die Ausführungszeit ist zufällig.
from random import randint
def sort(inputStr):
result = inputStr
while (not isSorted(result)):
letters = list(inputStr)
result = ''
while (len(letters) > 0):
i = randint(0, len(letters) - 1)
result += letters[i]
letters.pop(i)
return result
def isSorted(inputStr):
if (len(inputStr) in (0, 1)):
return True
for i in range(0, len(inputStr)-1):
if (inputStr[i].lower() > inputStr[i+1].lower()):
return False
return True
print(sort('adxbx'))
Schau dir verschiedene Sortieralgorithmen an.
Stichwort: Bubblesort, Insertionsort, Quicksort...
Es wär aber schlauer wenn du zuerst versuchst, ohne auf die Performance zu achten, deinen eigenen Algorithmus erstellst.
Es wär aber schlauer wenn du zuerst versuchst, ohne auf die Performance zu achten, deinen eigenen Algorithmus erstellst.
Heißt das dann jetzt, dass der Algorithmus "dumb_sort" aus meiner Antwort "schlau" ist? Ich hab extra nicht auf Performance geachtet! ><
wandelst dein string zuerst in eine liste um -> split Funktion
jetzt fehlt nur noch ein sortieralgorithmus:
Ich habe mir eben überlegt, wie man deine Aufgabenstellung möglichst "dämlich" lösen könnte, so wie ich es bei solchen Fragen immer tue, bin dann aber auf eine ganz interessante - wenn auch höllisch ineffiziente - Lösung gekommen:
#!/usr/bin/python3
from collections import Counter
def dumb_sort(text):
counter = Counter(text)
result = []
for i in range(0xffff + 1):
ch = chr(i)
if ch in counter:
result.append(ch * counter[ch])
return ''.join(result)
if __name__ == '__main__':
print(dumb_sort('adxbx')) # abdxx
Dein Lehrer erwartet aber garantiert eher, dass du ihm so etwas wie ein selbst geschriebenes QuickSort, MergeSort, o. ä. ablieferst! :)
Naja prinzipiell funktioniert dein Sortieralgorithmus. Allerdings ist er von der Performance her schon extrem schlecht. Du musst bei einem Durchlauf alle möglichen Werte durchlaufen bei utf16 mag das vielleicht noch möglich sein mit ca. 65000 werten. Stell dir aber vor du müsstest jetzt ein Array aus Integern sortieren (4 Milliarden durchläufe) oder vielleicht sogar einen 64 Bit Datentyp. Vielleicht solltest du dir den Algorithmus so ausdenken das er allgemeingültig ist. Also beliebige Datentypen welche vergleichbar sind sortieren kann und das die Laufzeitkomplexität von der Größe des Arrays abhängt und nicht von der Größe des Datentyps.
1.) Wieso ohne Sort-Funktion?
2.) Du möchtest die Buchstaben im String sortieren?
hahaha ... genau das gleiche habe ich hier vor ca. 2 Jahren mal unter einer Java Frage gepostet. :)
Dazu hatte ich mir noch den maximal effizienten Sortieralgorithmus "assume_sort" ausgedacht, bei dem einfach angenommen wird, dass die Eingangsdaten bereits sortiert sind ... der hat zwar eine extrem hohe Fehlerrate, aber aus der Spieleentwicklung sind ja Sortieralgorithmen bekannt, die durchaus Fehler produzieren dürfen, dabei aber unvergleichbar schnell sind.
Und da dachte ich mir eben: "Wenn schon, denn schon!". ;)