Im Ramen des Informatikunterrichts soll ich einen Sortieralgorithmus (Merge Sort) programmieren, welcher mir Wortlisten in komplett alphabetisch sortierter Reihenfolge wieder ausgibt. Dabei bin ich allerdings auf das Problem gestoßen, dass mein Programm dabei nur die ersten Buchstaben berücksichtigt und ich bin ehrlich gesagt nicht gut genug, um das Problem selber zu finden :/
Hier ist das Programm:
import timeit
start = timeit.timeit()
def merge_sort(array):
if len(array) <= 1:
return array
midpoint = int(len(array) / 2)
left, right = merge_sort(array[:midpoint]), merge_sort(array[midpoint:])
return merge(left, right)
def merge(left, right):
result = []
left_pointer = right_pointer = 0
while left_pointer < len(left) and right_pointer < len(right):
if left[left_pointer] < right[right_pointer]:
result.append(left[left_pointer])
left_pointer += 1
else:
result.append(right[right_pointer])
right_pointer += 1
result.extend(left[left_pointer:])
result.extend(right[right_pointer:])
return result
def main():
array = ['ade', 'htzre', 'fgrs', 'kmvirj', 'lsdnr']
print(array)
result = merge_sort(array)
print(result)
if __name__ == "__main__":
main()
end = timeit.timeit()
print (end-start)
Ich hoffe jemand kann mir dabei wenigstens einen Hinweis geben, weil ich sonst absolut nicht weiter komme. Danke im Voraus!
MergeSort mit alphabetischer Wortliste
- __blackjack__
- User
- Beiträge: 13100
- Registriert: Samstag 2. Juni 2018, 10:21
- Wohnort: 127.0.0.1
- Kontaktdaten:
@soRu: Also erst einmal ist `timeit()` total falsch verwendet. Du misst da einmal am Anfang wie lange es im Schnitt dauert die ``pass``-Anweisung auszuführen und das gleiche machst Du noch mal am Ende, und dann ziehst Du die beiden Werte voneinander ab. Ergebnis davon ist die Abweichung von zwei Messungen die den gleichen Code profilen, nämlich eine einzelne ``pass``-Anweisung. Das ist insgesamt sehr, sehr sinnlos.
Das was Du da `array` nennst ist kein Array, sondern eine Liste. Grunddatentypen sollten aber auch nicht in Namen stehen. `words` wäre ein passender Name.
Statt ``/`` und `int()` könnte man die Ganzzahldivision mit ``//`` verwenden.
Das mit der Zuweisung an ``left, right`` ist ziemlich irreführend, weil man nicht sofort sieht, das links von der Zuweisung ein Tupel steht.
Ansonsten sehe ich gerade das Problem nicht. Das Beispiel sortiert richtig.
Das was Du da `array` nennst ist kein Array, sondern eine Liste. Grunddatentypen sollten aber auch nicht in Namen stehen. `words` wäre ein passender Name.
Statt ``/`` und `int()` könnte man die Ganzzahldivision mit ``//`` verwenden.
Das mit der Zuweisung an ``left, right`` ist ziemlich irreführend, weil man nicht sofort sieht, das links von der Zuweisung ein Tupel steht.
Ansonsten sehe ich gerade das Problem nicht. Das Beispiel sortiert richtig.
„All religions are the same: religion is basically guilt, with different holidays.” — Cathy Ladman