Fügen Sie ein Element in Python in eine sortierte Liste ein

74

Ich erstelle eine Klasse, in der eine der Methoden ein neues Element in die sortierte Liste einfügt. Das Element wird an der korrigierten (sortierten) Position in der sortierten Liste eingefügt. Ich bin nicht eingebaute Liste Funktionen oder andere Verfahren als die Verwendung erlaubt [], [:], +, und lenzwar. Dies ist der Teil, der mich wirklich verwirrt.

Was wäre der beste Weg, dies zu tun?

Will S.
quelle
9
Hausaufgaben? Sie würden wahrscheinlich damit beginnen, im Web zu suchen, wie Elemente in eine sortierte Liste eingefügt werden.
Felix Kling
3
Ich darf jedoch keine integrierten Listenfunktionen verwenden
Will S
1
@FelixKling das OP erklärte, dass die Nichtzulassung von das .insert()ist, was es für das OP verwirrend macht. Es ist nicht sehr zu erwarten, dass bei jeder Suche jemand einen guten Fokus darauf im jeweiligen Kontext findet.
n611x007

Antworten:

122

Verwenden Sie die Insort Funktion des bisect Modul:

import bisect 
a = [1, 2, 4, 5] 
bisect.insort(a, 3) 
print(a)

Ausgabe

[1, 2, 3, 4, 5] 
stanga
quelle
6
Fehlt, was zu tun ist, wenn Elemente keine ganzen Zahlen sind. Dh wie kann ich es in realen Problemen verwenden?
Velda
2
@ Velda hier ist ein nicht ganzzahliges Beispiel:s = ['a', 'b', 'd']; bisect.insort(s, 'c'); assert(s == ['a', 'b', 'c', 'd'])
Joseph Holsten
8
Immer noch ganzzahliges Beispiel. Und übrigens, wie oft sortieren Sie Buchstaben ...? Was ist, wenn ich Instanzen einer Klasse nach einer Eigenschaft davon sortieren möchte?
Velda
2
@Velda Wenn Sie benutzerdefinierte Klassen vergleichen, können Sie die Methode __lt__ implementieren, und bisect.insort kann Klasseninstanzen korrekt sortieren. docs.python.org/3/library/operator.html#operator.__lt__
Drakenation
2
Dies läuft in O (n). Es ist nicht algorithmisch besser, als einfach die Liste zu
durchsuchen
78

Tipp 1: Möglicherweise möchten Sie den Python-Code im Bisect-Modul studieren .

Tipp 2: Das Schneiden kann zum Einfügen von Listen verwendet werden:

>>> s = ['a', 'b', 'd', 'e']
>>> s[2:2] = ['c']
>>> s
['a', 'b', 'c', 'd', 'e']
Raymond Hettinger
quelle
Da OP keine Funktionen oder Methoden verwenden durfte, bleibt das Slicing die einzige Möglichkeit, ein neues Element in eine Liste einzufügen.
Raymond Hettinger
4
Bisect eignet sich gut zum Einfügen sortierter Listen, fällt jedoch in der Geschwindigkeit auf O (N) ab, da die Basislisten von Python verwendet werden. Gibt es etwas auf dem Markt mit verknüpften Listen oder so etwas?
Maksim Gayduk
@MaksimGayduk Probieren Sie das Blist-Modul unter pypi.python.org/pypi/blist/1.3.6 aus . Das OP für diesen Beitrag unterliegt jedoch einigen recht strengen Einschränkungen, welche Tools verwendet werden durften.
Raymond Hettinger
36

Sie sollten das Halbierungsmodul verwenden. Außerdem muss die Liste sortiert werden, bevor bisect.insort_left verwendet wird

Es ist ein ziemlich großer Unterschied.

>>> l = [0, 2, 4, 5, 9]
>>> bisect.insort_left(l,8)
>>> l
[0, 2, 4, 5, 8, 9]

timeit.timeit("l.append(8); l = sorted(l)",setup="l = [4,2,0,9,5]; import bisect; l = sorted(l)",number=10000)
    1.2235019207000732

timeit.timeit("bisect.insort_left(l,8)",setup="l = [4,2,0,9,5]; import bisect; l=sorted(l)",number=10000)
    0.041441917419433594
Ricky
quelle
3

Ich lerne gerade Algorithmus, also frage ich mich, wie das Halbierungsmodul schreibt. Hier ist der Code aus dem Halbierungsmodul zum Einfügen eines Elements in eine sortierte Liste, die Dichotomie verwendet:

def insort_right(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted.
    If x is already in a, insert it to the right of the rightmost x.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]:
            hi = mid
        else:
            lo = mid+1
    a.insert(lo, x)
请 叫 我 小马哥
quelle
1

Dies ist eine mögliche Lösung für Sie:

a = [15, 12, 10]
b = sorted(a)
print b # --> b = [10, 12, 15]
c = 13
for i in range(len(b)):
    if b[i] > c:
        break
d = b[:i] + [c] + b[i:]
print d # --> d = [10, 12, 13, 15]
ngoc thoag
quelle
8
Nicht die beste Lösung, das bisectModul würde die Einfügemarke in O (log n) Schritten finden. Möglicherweise muss Ihr Modul die gesamte Liste durchsuchen, O (n) Komplexität.
Martijn Pieters
0
# function to insert a number in an sorted list


def pstatement(value_returned):
    return print('new sorted list =', value_returned)


def insert(input, n):
    print('input list = ', input)
    print('number to insert = ', n)
    print('range to iterate is =', len(input))

    first = input[0]
    print('first element =', first)
    last = input[-1]
    print('last element =', last)

    if first > n:
        list = [n] + input[:]
        return pstatement(list)
    elif last < n:
        list = input[:] + [n]
        return pstatement(list)
    else:
        for i in range(len(input)):
            if input[i] > n:
                break
    list = input[:i] + [n] + input[i:]
    return pstatement(list)

# Input values
listq = [2, 4, 5]
n = 1

insert(listq, n)
Vikas
quelle
-9

Dies ist der beste Weg, um die Liste anzuhängen und Werte in die sortierte Liste einzufügen:

 a = [] num = int(input('How many numbers: ')) for n in range(num):
     numbers = int(input('Enter values:'))
     a.append(numbers)

 b = sorted(a) print(b) c = int(input("enter value:")) for i in
 range(len(b)):
     if b[i] > c:
         index = i
         break d = b[:i] + [c] + b[i:] print(d)`
Veera Pathiran
quelle