Eine unsortierte Liste musst du zuerst (zumindestens teilweise) sortieren
Wenn die bestehende Liste aber schon nach Punkten vollständig sortiert/indiziert ist, und nun lediglich die Frage im Raum steht, wo in dieser bestehenden, sortierten Liste der neue User A mit seinen Punkten einsortiert werden soll, musst du, wenn du das "Einsortieren" wirklich "händisch" machen willst, natürlich nicht mehr alle 100k Einträge durchgehen.
Ein Algortihmus wäre, immer A mit dem User zu vergleichen, der genau in der Mitte einer Teilmenge ist. Das kann man rekursiv und damit sehr kurz implementieren.
n = 100'000 (erste Teilmenge ist die Gesamtmenge)
- Schritt: A < U_n/2 ? (hat A weniger Punkte als User auf Platz 50'000?)
Wenn ja, dann muss A ja einen Rang zwischen 1 und (n/2-1) einnehmen Wenn nein, dann ist der Rang zwischen n/2 und n
mal angenommen, er gehört zur 2. Hälfte, nämlich n/2 bis n (zweite Teilmenge also nur noch 50'000 bis 100'000)
- Schritt: A < U_(3/4 n) (wir schauen also, ob A kleiner als Platz 75'000 ist)
Wenn ja, dann muss A ja einen Rang zwischen n/2 und (3/4 n -1) einnehmen (also 50'000 und 74'999) Wenn nein, dann ist der Rang zwischen 3/4 n und n (also in deinem Beispiel 75000 und 100000)
... usw. ... diesen Algorithmus als Schleife oder rekrusiv implementieren ...
Hinweis: Wenn dir das Arbeiten mit 100k Einträgen aber schon ein Problem mit dem RAM bringt, ist es weniger eine mathematische Frage, sondern eher eine Frage, wie du die Daten modelliert und wie genau implementiert hast. 100k Zeilen sortieren kann ja selbst Excel ... in SQL oder Pandas ist alles schon eingebaut, was du benötigst, um dieses Problem zu lösen - ohne Basis-Algorithmen wie sortieren/indizieren/filtern/einfügen/ändern etc. neu schreiben zu müssen.
Punkte: 35