Seite 1 von 1
Array Sortierung
Verfasst: Dienstag 30. November 2021, 13:42
von TheLegendaryTwo
Hallo,
ich sitze jetzt schon etwas länger an diesem Problem. Grundsätzlich die Sortierung hab ich verstanden, allerdings weiß ich nicht genau, warum sich meine Variable "LISTE" auch ändert, wenn ich die Funktion bubblesort aufrufe und das Ergebnis in der Variable arrBubbleSort speichere.
Soweit ich es bis jetzt gelesen habe, gibt es ja dann Pointer zu diesen Array, wie kann ich das verhindern und quasi ein neues Array erzeugen?
Am Ende brauche ich das originale Array, nämlich für die nächste Funktion, insertionSort.
Hier einmal der Code:
Code: Alles auswählen
from numpy import random
import time
def getRandomIntList(listSize):
return random.randint(100, size=(listSize))
def bubblesort(arr):
startTime = time.time()
for i in range(0, len(arr)-1):
for j in range(0, len(arr)-i-1):
if arr[j] > arr[j+1]:
cache = arr[j]
arr[j] = arr[j+1]
arr[j+1] = cache
endTime = time.time()
print("Benötigte Zeit: " + str(endTime-startTime) + " Sekunden\n")
return arr
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arr
LISTE = getRandomIntList(10)
print("Origanle liste: \n" + str(LISTE))
arrBubbleSort = bubblesort(LISTE)
print("Origanle liste: \n" + str(LISTE))
arrInsertionSort = insertionSort(LISTE)
print("Bubblesort: \n" + str(arrBubbleSort))
print("arr: \n" + str(LISTE))
print("Insertionsort: \n" + str(arrInsertionSort))
Vielen Dank für die Hilfe

Re: Array Sortierung
Verfasst: Dienstag 30. November 2021, 13:51
von __deets__
Weil Python keine Kopien von Argumenten anlegt. Sondern nur Zugriff auf das übergeben Objekt via Parameternamen gewährt. Die Kopie musst du also selbst machen, natürlich am besten vor dem aufruf, um zu verhindern, dass dieser Akt in die Laufzeit eingeht.
Re: Array Sortierung
Verfasst: Dienstag 30. November 2021, 13:58
von TheLegendaryTwo
Ok danke, hab dafür mal eine kleine Funktion gemacht, bis jetzt gehts glaube ich.
Code: Alles auswählen
def copyArray(arr):
newArr = []
for i in range(len(arr)):
newArr.append(arr[i])
return newArr
Wäre das so der beste Weg, oder gibt's da noch bessere Ansätze?
Re: Array Sortierung
Verfasst: Dienstag 30. November 2021, 14:09
von pillmuncher
Code: Alles auswählen
>>> xs = [1, 2, 3]
>>> ys = xs[:]
>>> ys
[1, 2, 3]
>>> xs.append(4)
>>> xs
[1, 2, 3, 4]
>>> ys
[1, 2, 3]
Re: Array Sortierung
Verfasst: Dienstag 30. November 2021, 14:25
von Sirius3
Variablennamen und Funktionen schreibt man komplett klein: `get_random_int_list`.
Benutze keine Abkürzungen, `arr` soll wohl `array` heißen. Das was übergeben wird ist aber eine Liste und kein Array.
Strings stückelt man nicht mit + zusammen, sondern benutzt Format-Strings.
Der Defaultstartwert von `range` ist 0.
Um zwei Variablen zu tauschen benutzt man Tuple.
Da die Sortierfunktionen die übergebene Liste verändern, ist es guter Stil, keinen Rückgabewert zu haben.
Code: Alles auswählen
def bubblesort(values):
start_time = time.time()
for i in range(len(values) - 1):
for j in range(len(values) - i - 1):
if values[j] > values[j+1]:
values[j], values[j+1] = values[j+1], values[j]
end_time = time.time()
print(f"Benötigte Zeit: {end_time - start_time} Sekunden\n")
`LISTE` ist so geschrieben, als ob es eine Konstante wäre, da aber die Liste verändert wird, muss es `liste` heißen.
`copyArray` läßt sich einfach durch `list` ersetzen.
Re: Array Sortierung
Verfasst: Dienstag 30. November 2021, 14:34
von /me
Code: Alles auswählen
>>> xs = [1, 2, 3]
>>> ys = xs.copy()
>>> ys.append(4)
>>> xs
[1, 2, 3]
>>> ys
[1, 2, 3, 4]
Und ggf. auch
copy.deepcopy.
Re: Array Sortierung
Verfasst: Dienstag 30. November 2021, 14:41
von TheLegendaryTwo
Auch euch nochmal Danke, bin gerade in Java unterwegs, und hab deswegen nicht dran gedacht mir die Python Konvention anzugucken.
Variablen abkürzen war jetzt nur auf die schnelle, werde ich auch noch anpassen.
Eigentlich soll die Funktion garnicht die Variable ändern, auch etwas ungewohnt, dass Python so arbeitet. Werde das auch noch anpassen, damit ich eine neue Liste zurückgebe.
Und als letztes, 'LISTE' war nur ein Test, ob ich Python zwingen kann, die Variable nicht anzufassen, jetzt weiß ich ja aber woran das lag.
Vielen Dank euch allen für die schnelle Hilfe, den Rest schaff ich bestimmt alleine.
Re: Array Sortierung
Verfasst: Dienstag 30. November 2021, 15:00
von TheLegendaryTwo
So, ich hab jetzt nochmal etwas rumprobiert.
Gibt es hier noch irgendwelche Einwände?
Code: Alles auswählen
from numpy import random
import time
import copy
def get_random_int_list(list_size):
return random.randint(100, size=(list_size))
def bubblesort(original_list):
new_list = copy.copy(original_list)
start_time = time.time()
for i in range(len(new_list) - 1):
for j in range(len(new_list) - i - 1):
if new_list[j] > new_list[j+1]:
cache = new_list[j]
new_list[j] = new_list[j+1]
new_list[j+1] = cache
end_time = time.time()
print(f"Benötigte Zeit Bubblesort: {end_time - start_time} Sekunden\n")
return new_list
def insertionsort(original_list):
new_list = copy.copy(original_list)
start_time = time.time()
for i in range(1, len(new_list)):
key = new_list[i]
j = i - 1
while j >= 0 and key < new_list[j]:
new_list[j+1] = new_list[j]
j -= 1
new_list[j+1] = key
end_time = time.time()
print(f"Benötigte Zeit Insertionsort: {end_time - start_time} Sekunden\n")
return new_list
original_list = get_random_int_list(10)
print(f"Origanle Liste: {str(original_list)}")
bubblesorted_list = bubblesort(original_list)
insertionsorted_list = insertionsort(original_list)
print(f"Bubblesort: {str(bubblesorted_list)}")
print(f"Insertionsort: {str(insertionsorted_list)}")
print(f"Origanle Liste: " + str(original_list))
Edit: Tuple hab ich absichtlich nicht verwendet, finde es so für mich gerade übersichtlicher, werde mir das aber auch noch genauer angucken.
Re: Array Sortierung
Verfasst: Dienstag 30. November 2021, 15:52
von __blackjack__
@TheLegendaryTwo: Was ist am verändern der Liste ungewöhnlich bei Python wenn Du schreibst Du bist gerade in Java unterwegs? Java verhält sich da doch genau so.
Warum sollte die Funktion die Liste nicht verändern? Eine oft wichtige Entscheidungsfrage bei (Sortier)Algorithmen ist, ob dass „in place“ geht oder nicht. Und Bubblesort hat als Vorteil gegenüber einigen effizentieren Algorithmen, dass der wenigstens keinen zusätzlichen Speicherplatz braucht der von der Anzahl der Elemente abhängt. Da völlig ohne Grund erst einmal die ganze Liste zu kopieren macht IMHO keinen Sinn und ist kontraproduktiv. Gleiches gilt für Insertion-Sort.
Ich würde nicht `copy.copy()` verwenden. Am besten `list()`. Das hat dann wenigstens den Vorteil, dass man keine Liste übergeben muss, sondern beliebige iterierbare Objekte übergeben kann. Aber wie gesagt, sollte das eigentlich dem Aufrufer überlassen sein.
Die Zeitmessung und die `print()`-Ausgaben gehören nicht *in* die Funktionen. Das würde man einmal ausserhalb lösen. In einer Schleife, über eine Funktion, oder einen Kontextmanager.
Für solche Zeitmessungen ist `time.time()` nur bedingt geeignet. `time.monotonic()` wäre geeignet und `time.perf_counter()` die dafür vorgesehene Funktion.
Wenn Du an Zeitmessungen vom *Sortieren* interessiert bist, solltest Du wirklich *Listen* verwenden, denn bei Arrays hast Du bei den ganzen Zugriffen unnötige Umwandlungen bei den Elementen, deren Zeit Du auch mit misst, die aber gar nichts mit dem Sortieren an sich zu tun haben und das Ergebnis verzerren können.
Bubblesort ist falsch implementiert. Welche Definition legst Du denn da zugrunde? Das ist ja eh schon ein recht ineffizienter Algorithmus, und Du schreibst den so, dass die Laufzeit tatsächlich *immer* den „worst case“ hat. Der „best case“ bei der Laufzeit ist nach der üblichen Definition O(n). Das leistet Deine Implementierung nicht.
Re: Array Sortierung
Verfasst: Dienstag 30. November 2021, 16:04
von TheLegendaryTwo
@__blackjack__
Sinn der Aufgabe ist es, die Verschiedenen Sortiermethoden zu vergleichen, also welche mit der gleichen Liste am schnellsten ist. Dafür brauche ich natürlich dann auch die gleiche Liste.
Ich bin jetzt kein Java Profi, da ich gerade erst angefangen hab, kann also sein das es mir dort noch nicht aufgefallen ist.
Die Zeitmessung sollen wir genau so machen, um nur die Zeit zu sehen die für das Sortieren gebraucht wird. Außerdem wird uns die Funktion time.time() vorgeschrieben, also wollte ich jetzt nichts anderes nehmen.
Bei Bubblesort sehe ich gerade keinen Fehler, hab extra nochmal die Lösung vom Lehrer von der letzten Aufgabe angeguckt. Was ist da denn Falsch?
Ich merke auch, dass ich mir den Unterschied zwischen Arrays und Listen nochmal genauer angucken muss, da blick ich noch nicht so durch.
Re: Array Sortierung
Verfasst: Dienstag 30. November 2021, 16:10
von __deets__
Man kann Bubblesort optimieren, denn wenn man keinerlei Vertauschung vorgenommen hat (was man sich extra merken muss), dann kann man fruehzeitig abbrechen.
Re: Array Sortierung
Verfasst: Dienstag 30. November 2021, 16:13
von TheLegendaryTwo
Achso ok, danke. Hört sich irgendwie logisch an. Werde ich gleich mal umsetzen.
Re: Array Sortierung
Verfasst: Dienstag 30. November 2021, 17:46
von __blackjack__
Klar brauchst Du dafür die gleiche Liste, aber nicht die selbe Liste. Das ist ja externe Anforderung, die sich nicht aus dem Sortieralgorithmus selbst ergibt, sondern dem konkreten Fall für den Du den verwendest.
Bei `time.time()` würde ich trotz Anforderung abweichen, mit Begründung. So eine Anforderung liegt oft einfach daran, dass der Aufgabensteller es nicht besser wusste. So kann der was dazu lernen und es beim nächsten mal besser machen.
Und das weicht von der Anforderung dann nicht einmal so weit ab als wenn man das `timeit`-Modul aus der Standardbibliothek verwenden würde, das noch besser geeignet ist um Zeitmessungen vorzunehmen. Um einen Satz aus dessen Dokumentation zu zitieren: „This module avoids a number of common traps for measuring execution times.“ Ich denke ich hätte sogar *das* genommen, mit entsprechender Begründung, statt die `time.time()`-Vorgabe.
Wenn man einen (weiteren!) Funktionsaufruf tatsächlich nicht mit messen will, dann würde man halt messen was der alleine kostet und das dann abziehen. Aber einen gewissen, konstanten Mehraufwand wird man bei einer Messung alleine durch die Messung ja immer irgendwie haben. Den Aufruf von der Zeitfunktion, welche auch immer man da nimmt, wird man ja beispielsweise nicht weg bekommen. Wenn *ein* zusätzlicher Funktionsaufruf ein Problem ist, würde ich mal behaupten sind durch die ganzen Schwankungen und äusseren Einflüsse, an denen man gar nichts ändern kann, die Ergebnisse schon soweit verzerrt, dass die Messungen an sich nicht wirklich aussagekräftig sind. Und wenn man dann noch sieht, dass durch die Verwendung von einem Numpy-Array bei jedem lesenden/schreibenden Zugriff eine zusätzliche Typumwandlung mitgemessen wird…
Was auch gegen das Auslassen des Aufrufs aus der Messung spricht, ist das Sortieralgorithmen ja in der Regel tatsächlich in Funktionen stecken und ein „inlinen“ in der Regel keinen signifikanten Geschwindigkeitsvorteil bringt.