cin Strings in einen Vektor und QuickSort sie

Question

eine Lücke Funktion schreiben in einer beliebigen Anzahl von Strings liest (Duplikate erlaubt sind) von cin, speichert sie in einem Vektor, genannt string_list_sort(), die dann sortiert sie. Verwenden Sie nicht die Standard C++ Sortierfunktion hier - verwenden Sie die Version von Quicksort, die Sie erstellt haben.

Mein Problem ist, ich versuchte strcmp() zu verwenden, aber ich habe viele Fehler, so habe ich versucht, diese Methode, aber ich habe ein Problem mit char val = v[end]. Ich bin mir nicht sicher, wie man zwei std::string Werte vergleicht. Ich habe Char in String geändert und es funktioniert. Nun ist mein Problem zum Beispiel v = {"Apfel", "Auto", "Fuchs", "Seife", "FOZ"}; das Ergebnis, das ich bekommen, ist Apfel, Seife, Auto, Fuchs, foz die

#include <iostream> 
#include <string> 
#include <cstdio> 
#include <cstring> 
#include <vector> 
#include "error.h" 

using namespace std; 

void string_list_sort(vector<string> v){ 
    string line; 
    while (getline(cin, line)){ 
     if (line.empty()){ 
      break; 
     } 
     v.push_back(line); 
    } 
} 

int partition(vector<string>&v, int begin, int end) 
{ 
    char val = v[end]; 
    char temp; 

    int j = end; 
    int i = begin - 1; 

    while (true) 
    { 
     while (v[++i] < val) 
     while (v[--j] > val) 
     { 
      if (j == begin) 
       break; 
     } 

     if (i >= j) 
      break; 

     temp = v[i]; 
     v[i] = v[j]; 
     v[j] = temp; 
    } 

    temp = v[i]; 
    v[i] = v[end]; 
    v[end] = temp; 

    return i; 
} 

void quicksort(vector<string>& v, int begin, int end) 
{ 
    if (begin < end) 
    { 
     int p = partition(v, begin, end); 
     quicksort(v, begin, p - 1); 
     quicksort(v, p + 1, end); 
    } 
} 
void quick_sort(vector<string>& v) 
{ 
    quicksort(v, 0, v.size() - 1); 
} 

int main() 
{ 
    vector<string> v; 
    v = 
    { " this is a test string,.,!"}; 
    string word; 
    while (cin >> word) 
    { 
     v.push_back(word); 
    } 
    quick_sort(v); 
    for (int i = 0; i < v.size(); i++) 
    { 
     cout << v[i] << " "; 

    } 
} 

Answer 1

OP fast eine Sortierfunktion. Zwei Fehler insbesondere auffallen:

char val = v[end]; 
char temp; 

v ein vector<string> ist so v[end] eine string zurück.

string val = v[end]; 
string temp; 

Kümmert sich darum und macht das Programm kompilieren und erfolgreich sortieren. Es ist nicht notwendig, in die string s zu gehen, um Zeichen für Zeichen zu vergleichen. string funktioniert das für Sie.

Das zweite Problem: Quicksort Partitionsfunktion aussehen (Looting from wikipedia here)

algorithm partition(A, lo, hi) is 
    pivot := A[lo] 
    i := lo – 1 
    j := hi + 1 
    loop forever 
     do 
      i := i + 1 
     while A[i] < pivot 

     do 
      j := j – 1 
     while A[j] > pivot 

     if i >= j then 
      return j 

     swap A[i] with A[j] 

Partitionsfunktion

und OPs ein paar Pfunde zu viel hat abgeholt soll, die von einer optimalen Markierung erhalten entfernt werden muss, um ihre Lehrer. Schau dir die obige Pseudo-Implementierung an und vergleiche sie mit deiner. Sie können die Fehler richtig sehen, aber wenn nicht, stehen Sie auf den Schultern von Riesen und übersetzen Sie es in C++ (Hinweise: := ist einfach alt = in C++, und Sie müssen einige ; s und geschweifte Klammern hinzufügen). Debuggen Sie das Ergebnis nach Bedarf.Ich werde es nicht übersetzen, weil das den Punkt des Auftrags fast vollständig besiegen würde.

Side Noten (einige wichtige Anmerkungen zu sammeln):

Wenn ein Testfahrer Schreiben nehmen nicht in eine Benutzereingabe, bis Sie die Algorithmus funktioniert wissen. Beginnen Sie mit vorinstallierten Eingang, die einfach zu visualisieren wie

int main() 
{ 
    vector<string> v{"C","B","A"}; 
    quick_sort(v); 
    for (size_t i = 0; i < v.size(); i++) 
    { 
     cout << v[i] << " "; 

    } 
} 

Wenn der Ausgang ist „ABC“, ändern Sie den Eingang zu etwas komplizierter, aber immer noch leicht

vector<string> v{"A","C","Q","B","A"}; 

zu visualisieren Und wenn das geht funktioniert Nüsse und füttere es etwas fies. Ich mag die Major General's Song von den Piraten von Penzance.

Answer 2

Sie können Strings vergleichen mit std::string::compare() oder relationalen Operatoren nicht in alphabetischer Reihenfolge ist. Es sieht aus wie Sie versucht haben, hier relationalen Operatoren, sondern als @ user4581301 wies darauf hin, in partition() auf der ersten Zeile, haben Sie

char val = v[end]; 

jedoch v[end] vom Typ ‚String‘ ist, nicht "char". Wenn Sie val und temp als string anstelle von char deklarieren, können Sie sie mit den relationalen Operatoren sortieren, die Sie haben, und ich denke, es wird Ihnen gut gehen.

compare() Dokumentation: FTTP-: //www.cplusplus.com/reference/string/string/compare/

Relationale Operatoren: http://www.cplusplus.com/reference/string/string/operators/