Hypercell ein ] Hypercell aus ] Zeige Navigation ] Verstecke Navigation ]
c++.net  
   

Die mobilen Seiten von c++.net:
https://m.c-plusplus.net

  
C++ Forum :: C++ (alle ISO-Standards) ::  Quicksort mit 50% Wahrscheinlichkeit auf fehlerhafte Ausgabe  
Gehen Sie zu Seite 1, 2  Weiter
  Zeige alle Beiträge auf einer Seite
Auf Beitrag antworten
Autor Nachricht
InvisibleGhost
Mitglied

Benutzerprofil
Anmeldungsdatum: 21.04.2017
Beiträge: 5
Beitrag InvisibleGhost Mitglied 17:18:29 21.04.2017   Titel:   Quicksort mit 50% Wahrscheinlichkeit auf fehlerhafte Ausgabe            Zitieren

Hallo liebe Community,

unten findet ihr ein selbst geschriebenes Quicksort. Ich brauche das zum Einen so und habe mich außerdem das erste Mal mit Vektoren beschäftigt.

Grundsätzlich läuft das Quicksort auch wie erwünscht. Es besteht nur folgendes Problem: Bei ca. jedem zweiten Durchlauf passiert beim Auslesen ein Fehler, genauer gesagt steht dann an erster Stelle ein Zufallswert (Stellen 2-10 sind komplett korrekt). In der anderen Hälfte der Fälle, liefert das Programm absolut den richtigen Output.

Ich finde den Fehler ums Verderben nicht. Hat jemand von euch eine Idee?
C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <vector>
 
using namespace std;
 
void quickSort(vector<int>&,int,int);
 
int partition(vector<int>&, int,int);
 
int main()
{
    vector<int> A = {6,10,13,5,8,3,2,25,4,11};
    int p=0;
    int q= A.size();
 
    cout<<"======Original======="<<endl;
    for(auto e: A)
        cout<< e <<" ";
    cout<< endl;    
 
    quickSort(A,p,q);
 
    cout<<"======Sorted======="<<endl;
    for(auto e: A)
        cout<< e <<" ";
    cout<< endl;  
}
 
 
void quickSort(vector<int>&A, int p,int q)
{
    int r;
    if(p < q)
    {
        r=partition(A, p, q);
        cout << "geteilt\n";
        quickSort(A,p,r);
        quickSort(A,r + 1,q);
    }
}
 
 
int partition(vector<int>&array, int bottom, int top)
{
     int x = array[bottom];
     int i = bottom - 1;
     int j = top + 1;
     int temp;
 
     while (true){
        do {
                  j--;
           } while (x < array[j]);
 
          do {
                 i++;
          } while (x > array[i]);
 
          if (i < j) {
                temp = array[i];    
                array[i] = array[j];
                array[j] = temp;
                for(auto e: array)
                   cout << e <<" ";
                cout << endl;
         } else {
            return j;           // returns middle subscript  
         }
     }  
   
 
}


Danke und liebe Grüße
InvisibleGhost


Zuletzt bearbeitet von InvisibleGhost am 17:19:25 21.04.2017, insgesamt 1-mal bearbeitet
manni66
Unregistrierter




Beitrag manni66 Unregistrierter 18:27:35 21.04.2017   Titel:              Zitieren

Dann wirst du wohl mindestens einen ungültigen Index verwenden. Benutze at() statt [], dann wird sich der Vector melden.
wob
Unregistrierter




Beitrag wob Unregistrierter 18:29:37 21.04.2017   Titel:              Zitieren

Deine Partition-Funktion sieht sehr verdächtig aus.

Ersetze doch mal die eckigen Klammern array[] durch vector.at() - dann wird wird dir auch mitgeteilt, wenn du außerhalb des Arrays zugreifst.
InvisibleGhost
Mitglied

Benutzerprofil
Anmeldungsdatum: 21.04.2017
Beiträge: 5
Beitrag InvisibleGhost Mitglied 23:07:01 21.04.2017   Titel:              Zitieren

Ich danke euch beiden vielmals für den Hinweis! Damit fällt auch sofort auf, dass es
C++:
int q= A.size() - 1;

und nicht
C++:
int q= A.size();

heißen muss. Wie gesagt, ich bin mit Vektoren noch unsicher.
manni66
Unregistrierter




Beitrag manni66 Unregistrierter 00:04:57 22.04.2017   Titel:              Zitieren

C++:
while (x < array[j]);

Und was ist damit?
InvisibleGhost
Mitglied

Benutzerprofil
Anmeldungsdatum: 21.04.2017
Beiträge: 5
Beitrag InvisibleGhost Mitglied 10:59:24 22.04.2017   Titel:              Zitieren

Das habe ich natürlich durch
C++:
while (x < array.at(j));

ersetzt. Aber da spätestens an erster Stelle am Pivot-Element (sortierte Liste) der Vergleich scheitert, bekomme ich damit keinen fehlerhaften Speicherzugriff.
Schlangenmensch
Mitglied

Benutzerprofil
Anmeldungsdatum: 28.11.2008
Beiträge: 179
Beitrag Schlangenmensch Mitglied 11:30:56 22.04.2017   Titel:              Zitieren

Was passiert denn hier.:

C++:
do {
     i++;
} while (x > array[i]);


Wenn X das größte Element in dem vector ist.
InvisibleGhost
Mitglied

Benutzerprofil
Anmeldungsdatum: 21.04.2017
Beiträge: 5
Beitrag InvisibleGhost Mitglied 13:05:23 22.04.2017   Titel:              Zitieren

Nicht viel, i steht dann einfach an der ersten Stelle des Vektors. Und das macht ja auch soweit Sinn, das ist nämlich der klassische Fall einer umgedreht sortierten Liste. Es wird dann einfach nur das Pivot Element mit dem ersten kleineren Element von rechts getauscht.
Schlangenmensch
Mitglied

Benutzerprofil
Anmeldungsdatum: 28.11.2008
Beiträge: 179
Beitrag Schlangenmensch Mitglied 13:31:45 22.04.2017   Titel:              Zitieren

Und wann soll die Schleife beendet werden? Wenn du hier mit at(i) arbeiten würdest, würde dir dein Programm um die Ohren fliegen. Du brichst dann die Schleife nämlich erst ab wenn zufällig an der Stelle an der du liest ein Wert steht, der als Zahl interpretiert, größer oder gleich x ist.

Edit : falsch sry. Im ersten schleifen Durchlauf bist du da bei array[bottom] ==x und brichst ab, weil x nicht größer als x ist.


Zuletzt bearbeitet von Schlangenmensch am 13:36:06 22.04.2017, insgesamt 2-mal bearbeitet
unskilled
Mitglied

Benutzerprofil
Anmeldungsdatum: 06.07.2007
Beiträge: 3912
Beitrag unskilled Mitglied 15:39:44 22.04.2017   Titel:              Zitieren

C++:
    vector<int> A = { 6,10,13,5,8,3,2,25,4,11 };
    int p = 0;
    int q = A.size();
 
    quickSort(A, p, q);

->
C++:
void quickSort(vector<int>&A, int p, int q)
{
    int r;
    if (p < q)
    {
        r = partition(A, p, q);

->
C++:
1
2
3
4
5
6
7
8
9
10
11
int partition(vector<int>&array, int bottom, int top)
{
    int x = array[bottom];
    int i = bottom - 1;
    int j = top + 1;
    int temp;
 
    while (true) {
        do {
            j--;
        } while (x < array[j]);


j = 11
size = 10

_________________
Keiner kann besser nix als ich - Tagedieb mit Lächeln im Gesicht :o)
C++ Forum :: C++ (alle ISO-Standards) ::  Quicksort mit 50% Wahrscheinlichkeit auf fehlerhafte Ausgabe  
Gehen Sie zu Seite 1, 2  Weiter
Auf Beitrag antworten

Zeige alle Beiträge auf einer Seite




Nächstes Thema anzeigen
Vorheriges Thema anzeigen
Sie können Beiträge in dieses Forum schreiben.
Sie können auf Beiträge in diesem Forum antworten.
Sie können Ihre Beiträge in diesem Forum nicht bearbeiten.
Sie können Ihre Beiträge in diesem Forum nicht löschen.
Sie können an Umfragen in diesem Forum nicht mitmachen.

Powered by phpBB © 2001, 2002 phpBB Group :: FI Theme

c++.net ist Teilnehmer des Partnerprogramms von Amazon Europe S.à.r.l. und Partner des Werbeprogramms, das zur Bereitstellung eines Mediums für Websites konzipiert wurde, mittels dessen durch die Platzierung von Werbeanzeigen und Links zu amazon.de Werbekostenerstattung verdient werden kann.

Die Vervielfältigung der auf den Seiten www.c-plusplus.de, www.c-plusplus.info und www.c-plusplus.net enthaltenen Informationen ohne eine schriftliche Genehmigung des Seitenbetreibers ist untersagt (vgl. §4 Urheberrechtsgesetz). Die Nutzung und Änderung der vorgestellten Strukturen und Verfahren in privaten und kommerziellen Softwareanwendungen ist ausdrücklich erlaubt, soweit keine Rechte Dritter verletzt werden. Der Seitenbetreiber übernimmt keine Gewähr für die Funktion einzelner Beiträge oder Programmfragmente, insbesondere übernimmt er keine Haftung für eventuelle aus dem Gebrauch entstehenden Folgeschäden.