InsertionSort Funktion zum sortieren einer dictionary in Python


0

Hallo liebe Community,

Ich habe folgendes gegeben:

languages={"Javascript": 1, "Java": 2, "Python": 3, "CSS": 4, "PHP": 5, "Ruby": 6, "C++": 7, "C": 8, "Shell": 9, "C#": 10}

Das ist eine Folge von beliebten Programmiersprachen, welche nach der Popularität sortiert sind.

Weiter soll ich den Algorithmus insertionSort implementieren als in place Algorithmus. Dies habe ich bereits gemacht.

def insertionSort(L):
for i in range(1, len(L)):
    value = L[i]
    position = i
    while position > 0 and L[position-1] > value:
        L[position] = L[position-1]
        position = position-1
    if position != i:
        L[position] = value
return L

Die Funktion soll ich jetzt so ändern, dass die übergebene Liste von Programmiersprachen nach der Popularität aufsteigend sortiert wird Um zu sortieren soll ich die Datenstruktur dictionary (languages) nutzen.

Bisher habe ich gelesen, dass Dictionarys by Value oder Key sortiert werden können. In meinem Fall wäre es dann by Value oder? Wie ich meinen Code demnach verändern kann ist mir nicht ganz klar.

Ich würde mich freuen wenn mir hierbei jemand helfen kann! :)

 

gefragt vor 3 Wochen, 3 Tage
u
unixmelo,
Punkte: 10
 
Kommentar schreiben Diese Frage melden
2 Antworten
0

Hi unixmelo

Die genaue Interna von Python kenne ich leider nicht. Die Idee hinter einem Dict (Map) ist ein schneller Lookup via Hashvalue und nicht die Sortierung.
Ein dict ab Python 3.7 behält seine Einfüge-Ordnung bei und ist nicht nach Key sortiert.

Du hast es richtig gesehen, du diesmal by Value sortieren.
Die einfachste und schnellste Option für deine bestehende Lösung ist aus meiner Ansicht folgende:
1. Das Dict in eine Liste von Tupeln umzuwandeln (pop, (lang, pop)) --> list(zip(d.values(), d.items()))
2. Aus dem Resultat wieder ein Dict generieren. --> Your job ;-)

Ich empfinde diese Variante aber nicht als wirklich schön, denn Prinzipiell ist dict der "falsche" Datentyp hierfür.

Noch eifacher würde es folgendermassen gehen ;-)
sorted(dict, key=lambda x: dict[x])

Weiterführende Links Warum ein Dict die Einfügeordnung beibehält: https://stackoverflow.com/questions/1867861/how-to-keep-keys-values-in-same-order-as-declared Mehr Informationen zu einem dict in Python: https://docs.python.org/3/library/stdtypes.html#dict

geantwortet vor 3 Wochen, 3 Tage
_
_marc,
Student, Punkte: 25
 
Kommentar schreiben Diese Antwort melden
0

Hallo unixmelo,

ich verstehe noch nicht genau, welche Daten Du bekommst. Du sprichst von einer Liste der Programmiersprachen, gibst aber ein dict an. Je nachdem was Du machen musst, ändert sich aber die Lösung.

Wie bereits von _marc geschrieben, ist die Schwierigkeit, dass die dicts in Python nur mit O(1) einen Wert zum Schlüssel ausgeben können, aber dafür bei der Ausgabe seit Python 3.7 nach Einfügenordnung ausgeben (davor war dies eine zufällige Reihenfolge).

Falls Du wirklich mit einem dict startest und ein sortiertes dict benötigst, sehe ich folgende Ansätze:

Counter oder ValueSortedDict

Wenn Du Funktionen, welche in Python implementiert sind, nutzen darfst, solltest Du mal den Counter()aus dem Modul collections mit seiner eingebauten Funktion most_common() aus der Python-Dokumentation nachschlagen. Ein Counter ist nur ein spezielles dict, ich gehe aber davon aus, dass bei der Umwandlung die Speicheradresse unter der das Objekt gespeichert wird, sich ändert, von daher ist das nicht wirklich in-place. Das Modul ist in der Standard Library. Noch klarer wäre ein ValueSortedDict aus dem Modul sortedcollections, welches man aber über pip install sortedcollections installieren müsste. Da sehe ich aber prinzipiell auch die Frage nach dem in-place Eigenschaften.

Eigene Funktion die dictmodifiziert

Mit dem Wissen, dass ein dict in Python seine Einfügeordnung behält, und Du das dict in-place sortieren sollst, kann ich mir nur das Arbeiten mit del und gezieltes Einfügen vorstellen. Dabei könnte man dann einen Schlüssel mitdel L['Python']erst löschen und dann mit L['Python'] = 3 wieder anlegen. Das entspricht meines Erachtens aber dann nicht mehr wirklich Insertion-Sort, sondern eher Selection-Sort.

Umweg über Liste

Alle bisher vorgeschlagenen Wege gehen ja den Umweg über eine Liste, da man dort überhaupt erst sinnvoll Insertion-sort implementieren kann, dann ist dort zwar das Sortieren in-place, aber wegen der neuen Hilfsliste wird ja trotzdem anderen Speicherplatz benötigt. D.h. Du startest mit L = {key0: value0, ...} einem dict, gehst zu L = [(value0, key0), ... (valuen, keyn)] einer Liste, dann folgt in-place Dein Insertion-Sort, der die Liste modfiziert zu L = [(valuen, keyn), ..., (value0, key0)] und du gehst wieder zum dictüber. Die Wechsel lassen sich alle über die sogennten Comprehension machen, z.B. L = [(value, key) for key, value in L.items()] um vom dict L zur list L zu wechseln bzw. L = {key: value for key, value in L] um von der list zum dict zu wechseln. Dazwischen muss man natürlich Lin-place sortiert haben.

geantwortet vor 2 Wochen, 6 Tage
m
 
Kommentar schreiben Diese Antwort melden