Array Sortierung

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
TheLegendaryTwo
User
Beiträge: 6
Registriert: Dienstag 30. November 2021, 13:33

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 :)
__deets__
User
Beiträge: 14493
Registriert: Mittwoch 14. Oktober 2015, 14:29

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.
TheLegendaryTwo
User
Beiträge: 6
Registriert: Dienstag 30. November 2021, 13:33

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?
Benutzeravatar
pillmuncher
User
Beiträge: 1482
Registriert: Samstag 21. März 2009, 22:59
Wohnort: Pfaffenwinkel

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]
In specifications, Murphy's Law supersedes Ohm's.
Sirius3
User
Beiträge: 17710
Registriert: Sonntag 21. Oktober 2012, 17:20

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.
Benutzeravatar
/me
User
Beiträge: 3554
Registriert: Donnerstag 25. Juni 2009, 14:40
Wohnort: Bonn

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.
TheLegendaryTwo
User
Beiträge: 6
Registriert: Dienstag 30. November 2021, 13:33

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.
TheLegendaryTwo
User
Beiträge: 6
Registriert: Dienstag 30. November 2021, 13:33

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.
Benutzeravatar
__blackjack__
User
Beiträge: 13003
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@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.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
TheLegendaryTwo
User
Beiträge: 6
Registriert: Dienstag 30. November 2021, 13:33

@__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.
__deets__
User
Beiträge: 14493
Registriert: Mittwoch 14. Oktober 2015, 14:29

Man kann Bubblesort optimieren, denn wenn man keinerlei Vertauschung vorgenommen hat (was man sich extra merken muss), dann kann man fruehzeitig abbrechen.
TheLegendaryTwo
User
Beiträge: 6
Registriert: Dienstag 30. November 2021, 13:33

Achso ok, danke. Hört sich irgendwie logisch an. Werde ich gleich mal umsetzen.
Benutzeravatar
__blackjack__
User
Beiträge: 13003
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

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.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Antworten