WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

 
Gast > Registrieren       Autologin?   

Partner:




Forum
      Option
[Erweitert]
  • Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

Programmierung quicksort; Probleme mit den Pivotelement

 

Benjo2309
Forum-Newbie

Forum-Newbie


Beiträge: 1
Anmeldedatum: 06.06.22
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 06.06.2022, 15:13     Titel: Programmierung quicksort; Probleme mit den Pivotelement
  Antworten mit Zitat      
Hallo,

ich habe ein ein Programm geschrieben, welches nach dem Quicksortverfahren sortiert.

v steht für den Zeilenvektor
e für das Pivotelement.

Wenn ich als Pivotelement das Erste nehme, dann funktioniert alles korrekt, leider nicht für ein anderes Pivotelement.

Beispiel:

qsort22(['EineZeichenKette174'], 1)
ans = '147EKZceeeeehiinntt'

qsort22(['EineZeichenKette174'], 2)
ans = '1477Zceeeehhiinnttt'

Ich verstehe nicht warum mein EK verwindet und t und 7 auftaucht. Kann mir jemand weiter helfen? Liebe Grüße

Mein Code:

Code:
%

function [ v ] = qsort22( v, e )

% Pivot-Elemente
p=[];                                  
%Liste für alle großen Elemente aus v
b=[];                                
%Liste für alle kleineren Elemente aus v
s=[];                                  
l=length(v);

if(e>l)
    e=l;
end
%bei sortierbarem vektor
if(l>1)                                
    p=v(e);                             %Pivotelement
    for(i=2:length(v))                  %Elemente von v überprüfen
        if(v(i)<p)                      %Wenn Element kleiner als Pivot-Element
            s=[s,v(i)];                 %Element in kleiner-Liste
        elseif(v(i)>=p)                  %Wenn Element größer als Pivot-Element
            b=[b,v(i)];                 %Element in größer-Liste                
        end
       
    %quicksort_piv ausführen bis der Vektor nur noch ein Element enthält & Neubelegung des Vektors  
    end
    s=qsort22(s, e);                
    b=qsort22(b, e);              
    v=[s,p,b];                          
end

end


 
Private Nachricht senden Benutzer-Profile anzeigen


steve
Ehrenmitglied

Ehrenmitglied



Beiträge: 2.022
Anmeldedatum: 03.09.07
Wohnort: Wien
Version: R2023b
     Beitrag Verfasst am: 22.06.2022, 17:29     Titel:
  Antworten mit Zitat      
Hallo,

es sieht danach aus, dass der Fehler aus dieser Zeile resultiert:
Zitat:
Code:
   for(i=2:length(v))                  %Elemente von v überprüfen


Denn hier startest du immer bei der Position 2 des Vektors. Bei e=1 ist das auch die richtige Position (e+1), da 1 das Pivotelement ist. Für e=2 müsste der Startpunkt jedoch 1 und 3 sein, wenn ich das Konzept des Quicksort richtig verstanden habe (Quicksort bei Wikipedia). Denn bei e>1 hast du einen Teil links und einen Teil rechts des Pivotelements, welche iterativ sortiert werden müssen.

In deinem Code hast du quasi nur den rechten Teil berücksichtigt, was für den Spezialfall e=1 das richtige Ergebnis liefert, für alle anderen Werte von e aber nicht funktioniert, da jeweils der Teil links vom Pivotelement nicht berücksichtigt wird.

Gelöst habe ich es jetzt nicht, aber ich hoffe, du kommst mit dieser Analyse weiter.

Viele Grüße
Steve
_________________

>> I told me to.

____________________________________
Matlab Cheat Sheet
goMatlab-Knigge - dran gehalten?!
Schon in den FAQ gesucht?
Ist vielleicht bei den Skripten oder den Tutorials was für dich dabei?
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 24.432
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2017b
     Beitrag Verfasst am: 22.06.2022, 20:02     Titel:
  Antworten mit Zitat      
Hallo,

nach Steves Anstoß meine ich die Lösung zu wissen. In der von Steve genannten Zeile:
Code:

verwenden.

Grüße,
Harald
_________________

1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Neues Thema eröffnen Neue Antwort erstellen



Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:

Du kannst Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum posten
Du kannst Dateien in diesem Forum herunterladen
.





 Impressum  | Nutzungsbedingungen  | Datenschutz | FAQ | goMatlab RSS Button RSS

Hosted by:


Copyright © 2007 - 2024 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.