Quicksort-Algorithmus in einer doppelt verknüpften Liste

Question

ich eine Liste von Nachnamen mit dem Algorithmus von Quicksort sortiert werden soll aber, wenn die Elemente austauschen es funktioniert nicht, es läßt sich, wie sie

waren

In diesem Teil wird die Werte von die Ketten werden ausgetauscht

void swap(string* a, string* b){ 


cout<<"A and B are "<<*a<<" - "<<*b<<endl; 

string t = *a; 
*a = *b; 
cout<<" A is ->"<<*a<<endl; 

*b= t; 
cout<<"B is ->"<<*b<<endl; 

} 

Hier wird die Partition erstellt. Ich habe bemerkt, dass, wenn * i und * j Werte annehmen, sie genau dieselben Namen sind und daher nicht später verglichen werden können. Es erscheint mir seltsam, dass diese Liste funktioniert, wenn es eine Zahl ist, aber wenn es sich um Strings handelt, tritt dieser Fehler auf.

User *i = lower; 

Aber dies nicht am Ende arbeiten, weil das Programm abgestürzt ist, aber wenn man den Wert der

Zeichenfolge ändern

User* partition(User *lower, User *high){ 

cout<<"Lower -> "<<lower->lastname<<endl; 
cout<<"High -> "<<high->lastname<<endl; 
string pivot = high->lastname; 
User *i = bajo->prev; 
for (User *j = lower; j != high; j = j->next) 
{ 
    if (j->lastname.compare(pivot)< 0) 
    { 
     i = (i == NULL)? lower : i->next; 
     cout<<"Atention J e I valen ->"<<i->lastname<<" - "<<j->lastname<<endl; 
     swap(&(i->lastname), &(j->lastname)); 
    } 
} 
i = (i == NULL)? lower : i->lastname; // Similar to i++ 
swap(&(i->lastname), &(alto->lastname)); 
return i; 
} 

Was bin ich versagt? Wie kann ich wirklich den gewünschten Wert erreichen?

EDITED:

Dies ist der Quellcode

#include <iostream> 
#include<iomanip> 
#include <string> 
#include<cstdlib> 

using namespace std; 

class User 
{ 

public : 
    string lastname; 
    User *next; 
    User *prev; 
    User() 
    { 
     lastname= ""; 
     next=NULL; 
     prev=NULL; 

    } 
    int empty(User *listt) 
    { 

     if(listt == NULL) 
     { 

      return 1; 
     } 
     else 
     { 

      return 0; 
     } 

    } 


    User *Insert(User *listt, string lastName) 
    { 

     User *temp = new User(); 

     if(empty(listt)) 
     { 

      temp->lastname=lastName; 
      listt = temp; 

     } 
     else 
     { 

      temp->lastname=lastName; 
      listt->prev=temp; 
      temp->next=listt; 
      listt=temp; 

     } 
     return listt; 
    } 
    void swap(string* a, string* b) 
    { 

     string t = *a; 
     *a = *b; 

     *b= t; 

    } 
    User* partition(User* lower, User* high) 
    { 

     cout<<"Lower -> "<<lower->lastname<<endl; 
     cout<<"High -> "<<high->lastname<<endl; 
     string pivot = high->lastname; 
     User *i = lower->prev; 
     for (User *j = lower; j != high; j = j->next) 
     { 
      if (j->lastname.compare(pivot)< 0) 
      { 
       i = (i == NULL)? lower : i->next; 
       swap(&(i->lastname), &(j->lastname)); 
      } 
     } 
     i = (i == NULL)? lower : i->next; // Similar to i++ 
     swap(&(i->lastname), &(high->lastname)); 
     return i; 
    } 
    User *Last(User *listt) 
    { 
     User *temp = listt; 

     while(temp && temp ->next) 
      temp=temp->next; 
     return temp; 


    } 
    void _quickSort(User* lower, User* high) 
    { 

     if(high != NULL && lower != high&&lower!= high->next) 
     { 
      User *p = partition(lower,high); 
      _quickSort(lower,p->next); //I change this part 
      _quickSort(p->next,high); 

     } 

    } 
    void quickSort(User *listt) 
    { 
     User *h = Last(listt); 

     _quickSort(listt, h); 


    } 
    User *Display(User *listt) 
    { 

     if(empty(listt)) 
     { 

      cout<<"List empty"<<endl; 

     } 
     else 
     { 

      User *temp = new User(); 
      temp = listt; 
      while(temp!= NULL) 
      { 

       cout<<"The last name is -> "<<temp->lastname<<endl; 
       temp=temp->next; 
      } 

     } 
     return listt; 


    } 
}; 

int main() 
{ 

    User *listt = NULL; 
    User y; 
    bool exit = false; 
    int opc; 
    string lastName; 
    while(!exit) 
    { 

     cout<<"1.-Insert an element"<<endl; 
     cout<<"2.-Sort element-(Quicksort)"<<endl; 
     cout<<"3.-Show elements"<<endl; 
     cout<<"4.-Exitt"<<endl; 
     cin>>opc; 
     switch(opc) 
     { 
     case 1: 
      cout<<"Inser your last name"<<endl; 
      cin>>lastName; 
      listt=y.Insert(listt,lastName); 
      system("pause"); 
      system("cls"); 
      break; 
     case 2: 
      cout<<"Sorting...."<<endl; 
      y.quickSort(listt); 
      system("pause"); 
      system("cls"); 
      break; 
     case 3: 
      cout<<"Display..."<<endl; 
      y.Display(listt); 
      system("pause"); 
      system("cls"); 
      break; 
     case 4: 
      exit = true; 
      break; 



     } 




    } 




} 

Answer 1

_quickSort(lower,p->next); //I change this part 

Diese p->prev sein sollte. Die korrekte Funktion:

void _quickSort(User* lower, User* high) 
{ 
    if(high != NULL && lower != high&&lower != high->next) 
    { 
     User *p = partition(lower, high); 
     _quickSort(lower, p->prev); //change it back! 
     _quickSort(p->next, high); 
    } 
} 

Zusätzlich gibt es ein Ressourcenleck in. Sie vergeben keine neuen Elemente in Anzeigefunktion:

User *Display(User *listt) 
{ 
    if(empty(listt)) 
    { 
     cout<<"List empty"<<endl; 
    } 
    else 
    { 
     //User *temp = new User(); <== don't allocate new item here 
     User *temp = listt; 
     while(temp!= NULL) 
     { 
      cout<<"The last name is -> "<<temp->lastname<<endl; 
      temp=temp->next; 
     } 

    } 
    return listt; 
} 

Testing mit 1000 Einheiten:

class User 
{ 
public: 
    class Node 
    { 
    public: 
     string lastname; 
     Node *next; 
     Node *prev; 
     Node() 
     { 
      prev = next = nullptr; 
     } 
    }; 

    Node *head; 
    User() 
    { 
     head = nullptr; 
    } 

    void Insert(string val) 
    { 
     Node *temp = new Node; 
     temp->lastname = val; 
     if (head) 
     { 
      head->prev = temp; 
      temp->next = head; 
     } 
     head = temp; 
    } 

    void swap(string &a, string &b) 
    { 
     string t = a; 
     a = b; 
     b = t; 
    } 

    Node *Tail() 
    { 
     Node *temp = head; 
     while(temp && temp->next) 
      temp = temp->next; 
     return temp; 
    } 

    Node* partition(Node* left, Node* right) 
    { 
     string pivot = right->lastname; 
     Node *i = left->prev; 
     for(Node *j = left; j != right; j = j->next) 
     { 
      if(j->lastname < pivot) 
      { 
       i = (i == nullptr) ? left : i->next; 
       swap(i->lastname, j->lastname); 
      } 
     } 
     i = (i == nullptr) ? left : i->next; // Similar to i++ 
     swap(i->lastname, right->lastname); 
     return i; 
    } 

    void quickSort(Node* left, Node* right) 
    { 
     if(!left || !right || left == right || left == right->next) 
      return; 
     Node *p = partition(left, right); 
     quickSort(left, p->prev); 
     quickSort(p->next, right); 
    } 

    void quickSort() 
    { 
     quickSort(head, Tail()); 
    } 

    void Display() 
    { 
     string last; 
     for (Node *n = head; n; n = n->next) 
     { 
      if(n->lastname < last) 
      { 
       cout << "error ***\n"; 
       break; 
      } 
      last = n->lastname; 
      cout << n->lastname << endl; 
     } 
    } 
}; 

int main() 
{ 
    User list; 

    list.Insert("z"); 
    list.Insert("c"); 
    list.Insert("a"); 
    list.Insert("g"); 

    for(int i = 0; i < 1000; i++) 
    { 
     string str; 
     for (int j = 0; j < 3; j++) 
      str.push_back('a' + rand() % 26); 
     list.Insert(str); 
    } 

    list.quickSort(); 
    list.Display(); 

    return 0; 
} 

Answer 2

Eigentlich Funktion Ihre Swap scheint zu funktionieren, aber string t = *a; Nutzung ist ein bisschen komisch, weil *a als int-Wert betrachtet wird, so dass Sie es nicht zuweisen sollte eine Zeichenkette, obwohl der Compiler es auf jede Art behandeln kann. Andererseits denke ich, was Sie erwähnten, ist, den Wert von "a" in eine temporäre Zeichenkette zu kopieren und es sollte als string* t = a; getan werden, und dann können Sie b = t; tun, aber anstatt durch Referenz zu gehen ist eine bessere Praxis wie

void swap(string &a, string &b){ 
    string t = a; 
    a = b; 
    b= t; 
} 

und Sie möchten Ihre Schnell sortieren Umsetzung überprüfen, finden Sie in der Referenz auf this page