[FRAGE] - das pivotelement ist nicht immer die letzte Stelle oder?
Results 1 to 9 of 9
  1. #1
    Heavy's Avatar
    Title
    Super Moderator
    Join Date
    Feb 2002
    Posts
    1,340
    Thanks
    2
    Thanked 5 Times in 2 Posts

    das pivotelement ist nicht immer die letzte Stelle oder?

    Ja ich weiss die Frage ist blöd, aber ich hab bis jetzt noch nie eine Folge gesehen, bei der das Pivotelement z.B. genau in der Mitte vorkommt.
    Wie soll ich die Folge sortieren, wenn genau dieser Fall auftritt?

    z.B. 9 0 5 8 2 6 3 1 4 2, da kann ich die letzte Stelle nicht als Pivot wählen.


    Original geschrieben von eXe
    das pivotelement ist doch frei wählbar hängt von der implementierung ab ob mittleres letztes oder sonst eines

    wieso sollte 2 da nicht als pivotelement gehen?
    edit: z.B. dann halt diese Folge 9 0 5 8 2 6 3 2 4 1

    oder noch fieser: 9 8 7 6 5 4 3 2 1
    Last edited by Heavy; 16-04-2002 at 15:37.
    Religion ist ein Glaube,
    Wissenschaft als Teilgebiet ist ein Glaube,
    die Wahrheit liegt in der Gegenwart des Menschen.

  2. #2
    eXe's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    99
    Thanks
    0
    Thanked 0 Times in 0 Posts
    das pivotelement ist doch frei wählbar hängt von der implementierung ab ob mittleres letztes oder sonst eines

    wieso sollte 2 da nicht als pivotelement gehen?

  3. #3
    Heavy's Avatar
    Title
    Super Moderator
    Join Date
    Feb 2002
    Posts
    1,340
    Thanks
    2
    Thanked 5 Times in 2 Posts
    Heeelp bin am Verzweifeln!!!

    9 0 5 8 2 6 3 2 4 1 p=4
    2 0 5 8 2 6 3 9 4 1
    2 0 3 8 2 6 5 9 4 1
    2 0 3 2 8 6 5 9 4 1
    2 0 3 2 4 6 5 9 8 1
    -----------------------------------

    2 0 3 2 p=2
    2 0 3 2
    --------------------------------------
    ________6 5 9 p=9??

    Und wie geht's weiter?
    Religion ist ein Glaube,
    Wissenschaft als Teilgebiet ist ein Glaube,
    die Wahrheit liegt in der Gegenwart des Menschen.

  4. #4

    Title
    Master
    Join Date
    Feb 2002
    Posts
    141
    Thanks
    0
    Thanked 0 Times in 0 Posts
    muss da ganz links nicht ein "stop"element (kleinstes Element) stehen? habe nämlich genau das gleiche problem bei <7, 1012, 13, 128, 5, 4711, 34> ...

  5. #5

    Title
    Hero
    Join Date
    Feb 2002
    Location
    NIRVANA
    Posts
    180
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ja b-börnst
    es muss ein stop-element<min von 1-i A[i]
    ganz links stehen damit der algo funkt

  6. #6

    Title
    Hero
    Join Date
    Feb 2002
    Location
    NIRVANA
    Posts
    180
    Thanks
    0
    Thanked 0 Times in 0 Posts
    stopp-Element X < min 1-i von A[i]
    X ist kleiner als das Minimum des Arrays A[]

  7. #7
    jeuneS2's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Posts
    547
    Thanks
    1
    Thanked 45 Times in 29 Posts
    man könnte auch die Indexgrenzen überprüfen...
    Why bother spending time reading up on things? Everybody's an authority, in a free land.

  8. #8
    eXe's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    99
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ach das lag das problem sorry nicht gecheckt

    @jeuneS2: jo das hab ich mir auch mal überlegt warum das nicht so gemacht wird

  9. #9

    Title
    Veteran
    Join Date
    Feb 2002
    Posts
    22
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @jeuneS2: ist viel mehr Aufwand, bei jedem Durchlauf auf die Grenzen zu überprüfen, als einfach das Stoppelement einzubauen.

    @Jeff_Mills: Die Wahl des Stoppelements kommt auf die Implementation des Quicksorts an. Wenn man eine Quicksortimplementierung mit:
    Zeile 5: >=
    Zeile 8: <
    Zeile 9: <
    Zeile 12: >= (oder >, ist egal)
    verwendet, muß daß Stoppelement natürlich < dem Minimum sein und nicht nur <=.
    Nur wenn man eine Implementation mit:
    Zeile 5: >=
    Zeile 8: <=
    Zeile 9: <
    Zeile 12: >=
    verwendet, reicht es, wenn das Stoppelement <= dem Minimum ist.
    I'm a pessimist because of intelligence, but an optimist because of will. -- Antonio Gramsci

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •