Quicksort mit Pivot als mittleres Element

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
Credator
User
Beiträge: 2
Registriert: Sonntag 24. Juni 2018, 16:47

Hi,
wenn ich diesen Code ausführen lasse kommt: 3 2 -1 9 0 1 4 17 Raus anstatt von -1 0 1 2 3 4 9 17 und ich habe keine Idee wie man das Ändern kann...
Danke für die Hilfe

Code: Alles auswählen

[/#4Test
def quicksort(array):
   _quicksort(array, int(len(array)/2), len(array) - 1)

def _quicksort(array, start, stop):
    if stop - start > 0:
        pivot, left, right = array[start], start, stop
        while left <= right:
            while array[left] < pivot:
                left += 1
            while array[right] > pivot:
                right -= 1
            if left <= right:
                array[left], array[right] = array[right], array[left]
                left += 1
                right -= 1
        _quicksort(array, start, right)
        _quicksort(array, left, stop)
        
array=list([3, 2, -1, 9, 17, 4, 1, 0])
quicksort(arr]ay)

print(array)
Zuletzt geändert von Credator am Sonntag 24. Juni 2018, 17:11, insgesamt 4-mal geändert.
Benutzeravatar
ThomasL
User
Beiträge: 1366
Registriert: Montag 14. Mai 2018, 14:44
Wohnort: Kreis Unna NRW

Hi Credator, könntest du deinen Code mit den Editorfunktionen [ code][ /code] oder besser [ Python][ /Python]
umrahmen, dann können wir ihn besser erkennen und dir helfen.
Im vollständigen Editor gibt es dazu die Buttons </> und Python.
Danke im Voraus.
Ich bin Pazifist und greife niemanden an, auch nicht mit Worten.
Für alle meine Code Beispiele gilt: "There is always a better way."
https://projecteuler.net/profile/Brotherluii.png
Benutzeravatar
__blackjack__
User
Beiträge: 13100
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@Credator: Beschreib doch mal was `_quicksort()` machen soll, in Abhängigkeit von `array`, `start`, und `stop`‽ Also nicht im Detail was der Code macht, sondern nur in Worten was mit `array` gemacht wird und wie die Werte von `start` und `stop` da rein spielen.

Der `list()`-Aufruf bei der Zuweisung von `array` auf Modulebene ist übrigens sinnlos, das ist ja bereits eine Liste. Und der Name `array` ist ein bisschen irreführend, denn es gibt in Python auch Array-Datentypen, darum geht der Code aber nicht. Ein allgemeiner Name für etwas das eine Länge hat und Indexzugriffe kennt, ist in Python Sequenz oder in Englisch „sequence“.
„All religions are the same: religion is basically guilt, with different holidays.” — Cathy Ladman
Credator
User
Beiträge: 2
Registriert: Sonntag 24. Juni 2018, 16:47

Danke für die schnelle Antwort.
Muss dazu sagen dass ich das Gerüst des Codes aus dem Internet habe(weil 3 von mir nicht funktioniert haben...)
Quicksort ist eine Möglichkeit Listen zu sortieren wobei ein Element( heir ist das die Mitte) genommen wird und das Linke Element und das Rechte Element damit verglichen werden und das größere Element auf die rechte Seite gebracht wird
Start zeigt hier auf das erste ELement des Arrays(oder leichter gesagt der unsortierten Liste)
die int(len(array)/2) funktion zeigt auf das mittlere Element der Liste wo die Sortierung beginnen soll
und Stop zeigt wenn die Anzahl der Durchläufe der Anzahl der Elemente gleich ist und alles normalerwese sortiert werden sollte
Das Problem hierbei ist, dass wenn ich die Anzahl der Durchläufe erhöhe es einen Fehler gibt und die Liste somit nie zu ende Sortiert wird
Benutzeravatar
__blackjack__
User
Beiträge: 13100
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@Credator: `start` soll also das erste Element sein. Welchen Index hat denn das erste Element? Und welchen Wert hat `start` beim ersten Aufruf von `_quicksort()`?
„All religions are the same: religion is basically guilt, with different holidays.” — Cathy Ladman
Antworten