quicksort knapp daneben?

ich hab dieses quicksort programmiert:

def quicksort2(a): # hoare
    
    if len(a) < 2:
        return a
    
    r1, r2 = 0, len(a)-1
    pivot = a[random.randint(0,r2)]
    
    while r1 < r2:
        while a[r1] < pivot and r1 < r2:
            r1 += 1
        
        while a[r2] > pivot and r1 < r2:
            r2 -= 1
        
        a[r1], a[r2] = a[r2], a[r1]
        r1,r2 = r1+1,r2-1
    
    return quicksort2(a[:r1]) + quicksort2(a[r1:])

und das Ergebnis ist fast richtig, lediglich werden manchmal Zahlen im Ergebnis vertauscht. Ich hab schon mehrere gefragt, was das Problem ist, aber nicht mal ein Informatiklehrer konnte mir helfen. Auch chatgpt hat nur Schmutz geliefert, und deswegen frag ich hier. Und falls ihr denkt, ihr habt es, probiert es erst aus, weil das jeder bisher meinte.

Danke im vorraus.

1 Antwort

Vom Fragesteller als hilfreich ausgezeichnet

Jangler13

05.01.2023, 04:35

Beispiel:

Das Array a=[4,3,2,1]

Wir wählen das Pivot 1.

Dann kommt bei der ersten Iteration r1=0 und r2=3 raus.

Somit hast du nach Vertauschung:

[1,3,2,4]

Wegen r1,r2 = r1+1,r2-1

Ist r1 dann 1 und r2 ist 2

Am Ende der Schleife kommt dann r1=1 und r2=1 raus (da die Aufteilung passt)

Jedoch wird nun wieder r1,r2 = r1+1,r2-1

Weswegen r1 nun gleich 2 ist.

Somit wird a in die beiden Arrays [1,3] und [2,4] aufgeteilt, was aber nicht sein darf, da es so of gesplittet werden soll, sodass jedes Element aus dem linken Array kleiner sein muss, als alle Elemente aus dem rechten. Der Fehler ist hier, dass r1 um 1 zu hoch ist, du musst also korrigieren, dass dies nicht mehr passiert.

Versuch erst Mal selbst den Fehler zu finden, bevor du weiter liest.

================

Der Fehler ist, dass die Zeile

r1,r2 = r1+1,r2-1

Fehl am Platz ist. Du musst die entfernen, dann funktioniert der Algorithmus auch.

HiroNeedsHelp

Fragesteller

05.01.2023, 07:44

dann hängt es aber manchmal komplett, ich glaube weil es entweder 2 zahlen immer und immer wieder tauscht, oder weil die liste nicht klein genug wird zum rekursionsausgang

Jangler13

05.01.2023, 11:52

@HiroNeedsHelp

Hm, ich würde dir raten, dass du bei jedem Rekursionsschritt ausgibst, wie die derzeitige Liste aussieht, was das Pivot ist, wie die Liste unsortiert wurdet und was ri ist.

Dann sollte es vielleicht etwas leichter sein, den Fehler zu erkennen.

HiroNeedsHelp

Fragesteller

05.01.2023, 21:39

@Jangler13

das hatte ich schon ausprobiert, aber kam nicht darauf. die endgültige lösung war es scheinbar, nach dem vertauschen, nur r1 zu erweitern, um loops zu entkommen, aber nicht r2 zu ändern. bin nur durch zufall drauf gekommen, aber kanns mir auch nicht ganz erklären, wieso das einen so großen unterschied macht. evtl verhindert das, dass der pivot in die rechte liste kommt(?)

Ähnliche Fragen

Quicksort "Code" erklären?

Hi Leute, ich habe ein Problem mit Quicksort code und zwar ich verstehe wie das irl gemacht wird aber für mich ist der Code schwer zu verstehen. Kann mir bitte jemand diesen Code erklären?

public class QuicksortSimple {

  public void sort(int[] elements) {
    quicksort(elements, 0, elements.length - 1);
  }

  private void quicksort(int[] elements, int left, int right) {
    // End of recursion reached?
    if (left >= right) return;

    int pivotPos = partition(elements, left, right);
    quicksort(elements, left, pivotPos - 1);
    quicksort(elements, pivotPos + 1, right);
  }

  public int partition(int[] elements, int left, int right) {
    int pivot = elements[right];

    int i = left;
    int j = right - 1;
    while (i < j) {
      // Find the first element >= pivot
      while (elements[i] < pivot) {
        i++;
      }

      // Find the last element < pivot
      while (j > left && elements[j] >= pivot) {
        j--;
      }

      // If the greater element is left of the lesser element, switch them
      if (i < j) {
        ArrayUtils.swap(elements, i, j);
        i++;
        j--;
      }
    }

    // i == j means we haven't checked this index yet.
    // Move i right if necessary so that i marks the start of the right array.
    if (i == j && elements[i] < pivot) {
      i++;
    }

    // Move pivot element to its final position
    if (elements[i] != pivot) {
      ArrayUtils.swap(elements, i, right);
    }
    return i;
  }

}

...zur Frage

Wie kann man die Länge r1 berechnen?

Bei der r2 muss man ja nur 2,5pq und was ist dann mit der r1 ? Wie kann ich sie dann berechnen, um das Ergebnis abzuziehen, um den kreisring auszurechen ?:)

...zur Frage

Wieso kommt None raus? #Python?

Ich habe einen Code:

def Wurzelziehen(Input):

  try:

    float(Input)

  except ValueError:

    return False

    exit()

  def Mitte(x, y):

    if x > y:

      Ergebnis = x + ((x - y) / 2)

    if x == y:

      Ergebnis = x

    else:

      Ergebnis = x + ((y - x) / 2)

    return Ergebnis

  a = 0

  b = Input

  b = int(b)

  if a * a == Input or b * b == Input:

    if a * a == Input:

      return a

    else:

      return b

  else:

    while (Mitte(a, b) * Mitte(a, b)) != Input:

      Zwischenzahl = float(Mitte(a, b)) * float(Mitte(a, b))

      if len(str(Mitte(a, b))) > 17:

        return Mitte(a, b)

      if Zwischenzahl < float(Input):

        a = Mitte(a, b)

      elif Zwischenzahl > float(Input):

        b = Mitte(a, b)

      else:

        return Mitte(a, b)

print(Wurzelziehen(16))

und da kommt aus irgeneinem Grund "None" raus. Wieso? Kann mir jemand helfen?

Liebe Grüße Alex950.

...zur Frage

Wieso funktioniert mein Python-Code für eine binäre Suche in einem Array nicht?

Wenn ich diesen Code auf meiner Konsole eingebe funktioniert nichts, was sehr fragwürdig ist da ich den Code schon dutzende male durchgegangen bin. Kann mir irgendjemand helfen? Die genaue Aufgabenstellung befindet sich als Bild im Anhang.

Code:

def binarySearch(arr, num):

. a = 0

. b = len(arr) - 1

. counter = 0

. while a <= b:

. m = (a + b) // 2

. if num <= arr[m]:

. b = m

. else:

. a = m + 1

. counter += 1

. if num == arr[a]:

. return counter

. else:

. return -1

mein_array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

gesuchte_zahl = 8

ergebnis = binarySearch(mein_array, gesuchte_zahl)

...zur Frage

Was haltet ihr von diesem Weg um ein Wort in einem String zu suchen?

Ich habe das mal so programmiert.

String = "     Hai"


len(String)


i = 0
state = 0
while i <  len(String) :
  if String[i].isspace() and state == 0:
    i = i +1
    print ("whitespace")
 
    if String[i].isspace() == False and state == 0:
     state = 1
     
  if String[i] == "H" and state == 1:
    print("H found")
    state = 2
    i = i +1
  if String[i] == "a" and state == 2:
    print ("a gefunden")
    state = 3
    
    i = i +1 
  if String[i] == "i" and state == 3:
    print("i")
    state = 4
  if state == 4:
    print ("Hai gefundem")
    break

...zur Frage

Warum werden in diesem Code Klassen verwendet?

Also was für einen Vorteil hat das?:

Der Code ist für ein Tic-Tac-Toe-Spiel

class Board():
    def __init__(self):
        self.state = [0, 0, 0, 0, 0, 0, 0, 0, 0]

    def make_turn(self, cell, player):
        if self.is_valid_turn(cell):
            self.state[cell] = player.symbol
            return True
        return False

    def is_valid_turn(self, cell):
        if self.state[cell] == 0:
            return True
        else:
            return False

    def check_win(self, player):
        s = player.symbol
        if self.state[0] == s and self.state[1] == s and self.state[2] == s:
            return True
        elif self.state[3] == s and self.state[4] == s and self.state[5] == s:
            return True
        elif self.state[6] == s and self.state[7] == s and self.state[8] == s:
            return True

        elif self.state[0] == s and self.state[3] == s and self.state[6] == s:
            return True
        elif self.state[1] == s and self.state[4] == s and self.state[7] == s:
            return True
        elif self.state[2] == s and self.state[5] == s and self.state[8] == s:
            return True

        elif self.state[0] == s and self.state[4] == s and self.state[8] == s:
            return True
        elif self.state[2] == s and self.state[4] == s and self.state[6] == s:
            return True

    def is_full(self):
        for i in self.state:
            if i == 0:
                return False
        return True

    def sign_to_printable(self, sign):
        if sign == 0:
            return " "
        elif sign == 1:
            return "X"
        else:
            return "O"

    def print_board(self):
        print(" " + self.sign_to_printable(self.state[0]) + " | " + self.sign_to_printable(self.state[1]) + " | " + self.sign_to_printable(self.state[2]) + " \n" +
              " " + self.sign_to_printable(self.state[3]) + " | " + self.sign_to_printable(self.state[4]) + " | " + self.sign_to_printable(self.state[5]) + " \n" +
              " " + self.sign_to_printable(self.state[6]) + " | " + self.sign_to_printable(self.state[7]) + " | " + self.sign_to_printable(self.state[8]) + " \n")


class Player:
    def __init__(self, symbol):
        self.symbol = symbol


if __name__ == '__main__':
    player_a = Player(1)
    player_b = Player(-1)
    board = Board()
    active_player = player_a
    while not board.is_full():
        board.print_board()
        try:
            cell = int(input("Where do you want to place your sign? [1-9]"))
        except ValueError:
            continue
        cell = cell - 1
        if cell < 0 or cell > 8:
            print("Please enter a number between 1 and 9")
            continue
        if not board.make_turn(cell, active_player):
            print("Invalid Move")
            continue

        if board.check_win(active_player):
            print("You wonnered! GW.")
            break

        if …

...zur Frage

Gesamtwiederstand bei Parallelschaltung berechnen?

Die Aufgabe lautet bei einer Parallelschaltung Rg auszurechnen aus R1 und R2 ich weiß dass ich 1/R1 +1/R2 rechnen muss aber wenn ich die Werte für die Widerstände einsetze ( jeweils 155Ohm) und das in den Taschenrechner eintippe kommt irgendwas mit 0,0 was ein unrealistische Ergebnis ist...was rechne ich falsch ?

...zur Frage

Mein Python Code funktioniert nicht?

Guten Abend erst einmal,

ich habe versucht mittels Python ein Mau Mau spiel zu erstellen, aber wenn ich es ausprobieren will, zeigt mir das Programm mitten im code " invalid Syntax " an.

Kann einer von euch mal bitte drüber schauen und mir sagen, was fehlt?

Hier ist der Code (,was mir als Fehler angezeigt wurde habe ich markiert( es ist das deck.shuffel ())).

import random

class Card:

def __init__(self, value, suit):

self.value = value

self.suit = suit

def __repr__(self):

return f"{self.value} of {self.suit}"

class Deck:

suits = ["Hearts", "Diamonds", "Spades", "Clubs"]

values = ["Ace", "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King"]

def __init__(self):

self.cards = [Card(value, suit) for suit in self.suits for value in self.values]

def shuffle(self):

random.shuffle(self.cards)

def deal(self):

return self.cards.pop()

class Player:

def __init__(self, name):

self.name = name

self.hand = []

def draw(self, deck):

self.hand.append(deck.deal())

def play_card(self, card):

self.hand.remove(card)

class AIPlayer(Player):

def choose_card(self, top_card):

for card in self.hand:

if card.value == top_card.value or card.suit == top_card.suit:

return card

return self.hand[0]

def play_game():

deck = Deck()

... deck.shuffle()

...

... player = Player("Player")

... ai = AIPlayer("AI")

...

... for i in range(7):

... player.draw(deck)

... ai.draw(deck)

...

... top_card = deck.deal()

...

... while len(player.hand) > 0 and len(ai.hand) > 0:

... print(f"Top card: {top_card}")

... print(f"{player.name}'s hand: {player.hand}")

...

... chosen_card = player.play_card(player.hand[int(input("Choose a card to play (index): "))])

... if chosen_card.value == top_card.value or chosen_card.suit == top_card.suit:

... top_card = chosen_card

... else:

... player.draw(deck)

... print(f"{player.name} drew a card.")

...

... if len(ai.hand) > 0:

... chosen_card = ai.choose_card(top_card)

... print(f"{ai.name} played {chosen_card}.")

... if chosen_card.value == top_card.value or chosen_card.suit == top_card.suit:

... top_card = chosen_card

... else:

... ai.draw(deck)

... print(f"{ai.name} drew a card.")

...

... if len(player.hand) == 0:

... print(f"{player.name} wins!")

... else:

... print(f"{ai.name} wins!"

>>> [DEBUG ON]

>>> [DEBUG OFF]

...zur Frage

Widerstände im unbelasteten Spannungsteiler berechnen?

Moin,

Ich habe zwei eigentlich recht kurze Aufgaben, bei denen ich aber einfach nicht auf's richtige Ergebnis komme.
Die Aufgaben lauten wie folgt:

Ein Spannungsteiler besteht aus den Widerständen R1 und R2. Eine Spannungsquelle versorgt den Spannungsteiler mit der Spannung UB.

Wie groß sind die Widerstände R1 und R2, wenn U2 und UB vorgegeben sind und wie groß ist R2, wenn R1, U1 und U2 gegeben sind?

Zahlen gibt es dazu natürlich nicht, nur die Variablen.
Kennt da zufällig jemand die entsprechenden Formeln?

...zur Frage

Python Primzahlen erraten umschreiben?

Hey ich hab ein Programm zu Primzahlen erraten entworfen. Allerdings gefällt es mir noch nicht so gut. Könnte jemand das ganze etwas eleganter programmieren bzw umschreiben?

def teiler(N):

liste=[]

i = 2

rest = 0

while i < N:

rest = N%i

if rest == 0:

liste.append(i)

i=i+1

else:

i=i+1

return(liste)

print("PRIMZAHLENDETEKTOR")

print()

N=2

while N != 0:

N=int(input("Bitte eine Zahl eingeben (Abbruch mit 0): "))

ergebnis=teiler(N)

if len(ergebnis)==0:

print(N," ist eine Primzahl!")

else:

print(N," ist keine Primzahl!")

...zur Frage

Wiederstandschaltung U2/Ug berechnen?

Ich verzweifel grade an dieser scheinbar völlig simplen Aufgabe. Ich muss UG berechnen, aber ich komme schlichtweg nicht auf Ur2. Eigentlich sollte I2=I1 sein ( da Reihe) aber mit dieser Überlegung komme ich auf kein Ergebnis. Spannungsteiler and R1 /R2 brachte mir auch keine lösung

...zur Frage

[Python]Wie kann ich eine Rechnung von einem string zu integer wandeln?

Ich möchte eine Aufgabenstellung, z.B str(12+12-12), in int/float umwandeln und das Ergebnis ausgeben.

import random

lst = ["Was ergibt: 17*3+5*2", "Was ist das Ergebnis von: 12*11+15 ", "Sag mir das Ergebnis von: ((19-1+2)*3+20)*4 "]

x = random.randint(0, len(lst)-1)
v = lst[x].split(":")[1].strip()

print(v)
print(int(v))

#
#ValueError             Traceback (most recent #call last)
#Input In [39], in <cell line: 9>()
#      6 v = lst[x].split(":")[1].strip()
#      8 print(v)
#----> 9 print(int(v))
#
#ValueError: invalid literal for int() with base 10: '12*11+15'

...zur Frage

Python Pickle Vokabeltrainer?

Hallo,

ich will einen simplen Vokabeltrainer mit python programmieren. Um die Vokabeln die vom user eingeben werden zu speichern verwende ich pickle. Leider werden ohne Fehlermeldung keine Vokabeln in der von mir angelegten Datei gespeichert.

import random
import pickle



class Entry:
    def __init__(self, deutsch, englisch):
        self.deutsch = deutsch
        self.englisch = englisch


    def toString(self):
        return self.deutsch + " - " + self.englisch
        
eintraege = [Entry("hallo", "hello")]


def save():
    with open('vocabulary.pkl', 'wb') as voc_pkl:
        pickle.dump(eintraege, voc_pkl)


save()
 
with open('vocabulary.pkl', 'rb') as voc_pkl:
    eintraege = pickle.load(voc_pkl)



def eingabe():
    while True:
        deutsch = input("Deutsches Wort: ")
        if deutsch == "#fertig":
            return
        englisch = input("Englisches Wort: ")
        if englisch == "#fertig":
            return
        eintraege.append(Entry(deutsch, englisch))
        save()
        
def abfrage():
    while True:
        i = random.randint(0,len(eintraege)-1)
        englisch = input("Englische Übersetzung von " + eintraege[i].deutsch + ": ")
        if(englisch == "#fertig"):
            return
        if eintraege[i].englisch == englisch:
            print("korrekt!")
        else:
            print("leider falsch. Richtige Antwort: " + eintraege[i].englisch)
            
def printall():
    for eintrag in eintraege:
        print(eintrag.toString())
        
while True:
    befehl = input("Befehl: ")
    if befehl == "eingabe":
        eingabe()
    elif befehl == "abfrage":
        abfrage()
    elif befehl == "beenden":
        break
    elif befehl == "ausgabe":
        printall()
    else:
        print("keine bekannte Ausgabe. Tippe: eingabe, abfrage, ausgabe oder beenden.")

...zur Frage

Gilt das Ergebnis für beliebige Vektoren?

Habe den Ausdruck berechnet, und komme auf den Vektor (0,0,0) bzw Nullvektor. Gilt das Ergebnis für beliebige Vektoren r1,r2,r3?

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen