Swap-Sort Element mehrmals vorkommen?

[Hetiras]

Hallo Leute,
ich bin neu hier falls das der falsche Bereich ist tut es mir Leid.

Ich habe eine Frage, wäre es möglich den Swap-Sort(http://de.wikipedia.org/wiki/Swap-Sort) Algorithmus zu verändern damit
auch Elemente mehrmals vorkommen können?
Meine erste Idee war zu vergleichen ob der Inhalt des alten Index mit dem neuen Index übereinstimmt, leider funktioniert das auch nicht so wie gewollt.

Hier mein Code, mit dem eine Liste sortiert wird in der Elemente nur einmalig vorkommen :

Code: Alles auswählen

L = [1,3,4,5,2]
index = 0
while index < len(L) - 1:
    neuerindex = sum(element < L[index] for element in L)
    if index == neuerindex:
        index += 1
    else:
        L[index], L[neuerindex] = L[neuerindex], L[index]
print(L)

[BlackJack]

@Hetiras: Nö. Oder ja. Kommt halt drauf an was Du unter verändern verstehst.

[Hetiras]

Mit verändern meine ich, Swap-Sort etwas anzupassen und nicht gleich einen komplett neuen Sortieralgorithmus erstellen

[BlackJack]

@Hetiras: Dann eher Nein, denn der basiert ja darauf zu zählen wie viele Elemente vor dem aktuell betrachteten kommen müssen weil sie kleiner oder gleich sind. Und irgendwo bekommt man dann bei gleichen Elementen Probleme zu entscheiden ob man tauschen muss oder nicht und dazu reicht die gesammelte Information nicht aus.

[Hetiras]

Also hast du vermutlich mit ja gemeint mit einem anderen Algorithmus wäre es möglich, oder?
Gibts es schon ein Sortieralgorithmus der auf dem Prinzip basiert, aber gleiche Elemente mehrmals erlaubt?

[BlackJack]

@Hetiras: Was ist denn das Prinzip hier? Also wie viel darf man am Algorithmus ändern, und an den Laufzeit und Speichereigenschaften, damit das noch das gleiche Prinzip ist?

Warum interessiert Dich das überhaupt? Der Algorithmus ist nicht wirklich brauchbar. Ein simpler Insertionsort ist besser als dieses Swap-Sort.

[Hetiras]

Mit dem Prinzip meine ich, dass nach der Anzahl der Elemente der Index bestimmt wird. Wäre das auf irgend eine Art möglich?
Speichereigenschaften und Laufzeit sind egal. Jemand meinte das ist möglich und das wollte ich versuchen umzusetzen.

Schaue mir mal Insertionsort an.

[EyDu]

Du könntest eine Zwischenstufe einbauen:

Code: Alles auswählen

import operator
import random


def count(index, data):
    counter = 0
    
    element = data[index]
    for i, e in enumerate(data):
        if e < element:
            counter += 1
        elif e == element:
            if i <= index:
                counter += 1
    
    return counter


def swap_sort(data):
    index = 0
    
    while index < len(data) - 1:
        less = sum(e < data[index] for e in data)
        
        if index == less:
            index += 1
        else:
            data[index], data[less] = data[less], data[index]


def swap_sort2(data):
    temp = [(count(index, data), element) for (index, element) in enumerate(data)]
    swap_sort(temp)
    data[:] = map(operator.itemgetter(1), temp)


def main():
    N = 20
    R = 10
    
    data = [random.randint(0, R-1) for _ in xrange(N)]
    
    print data
    swap_sort2(data)
    print data


if __name__ == "__main__":
    main()

[diesch]

Warum interessiert Dich das überhaupt? Der Algorithmus ist nicht wirklich brauchbar. Ein simpler Insertionsort ist besser als dieses Swap-Sort.

Swap-Sort ist minimal bezüglich Schreibaktionen.

[cofi]

Mit dem Prinzip meine ich, dass nach der Anzahl der Elemente der Index bestimmt wird. Wäre das auf irgend eine Art möglich?

Nein. Wenn du Elemente gleich sind, wie willst du dann festlegen was das i. Element ist? Sagen wir du hast eine Liste `[1, 5, 4, 2, 5, 5]` wie willst du fuer jede 5 ihre Position ableiten, wenn du nur weisst das sie 5en sind?

Man kann dann noch den Weg zu Bucket-Sort gehen und die Elemente von der 1-dimensionalen Liste erstmal in eine 2-dimensionale Liste sortieren. Dann hat man aber auch schon einen anderen Sortieralgorithmus.

[BlackJack]

@Hetiras: Wenn Speichereigenschaften und Laufzeit egal sind, dann ist es trivial einen „decorate, sort, undecorate”-Ansatz darum zu basteln. Einfach die Elemente in eine Liste mit Tupeln aus Wert und Index der Ursprungsliste stecken, damit sind die gleichen Elemente künstlich ungleich gemacht, und nach dem sortieren die Werte wieder heraus holen.

Code: Alles auswählen

def swap_sorted(sortme):
    decorated = [(value, index) for index, value in enumerate(sortme)]
    swap_sort(decorated)
    return [value for value, _ in decorated]

Nur der Sinn davon ist natürlich fragwürdig…

[Hetiras]

Ok, vielen dank euch allen. Damit hat sich meine Frage beantwortet.