CIN строки в вектор и QuickSort их

Question

Написать функцию пустот под названием string_list_sort(), который читает в любом количестве строк (дубликаты разрешены) от CIN, хранит их в векторе, а затем сортирует их. Не используйте стандартную функцию сортировки C++ здесь - используйте созданную вами версию quicksort.

Моя проблема, я пытался использовать strcmp() но у меня много ошибок, поэтому я попробовал этот метод, но у меня есть проблема с char val = v[end]. Я не уверен, как сравнить два значения std::string. Я изменил char на строку, и он работает. Теперь моя проблема - это, например, v = {"apple", "car", "fox", "soap", "foz"}; результат я получаю яблоко, мыло, автомобиль, лисица, Фос, не в алфавитном порядке

#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 почти имеет функцию сортировки. Две ошибки, в частности, выделяются:

char val = v[end]; 
char temp; 

v является vector<string> так v[end] возвратит string.

string val = v[end]; 
string temp; 

Заботится об этом и заставляет программу скомпилировать и успешно отсортировать. Нет необходимости заходить внутрь string s для сравнения символа по персонажам. string это работает для вас.

Вторая проблема: статсумма QuickSort, как предполагается выглядеть (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] 

и статсумма ФПА в подцепила кучу дополнительного багажа, который должен быть удален, чтобы получить оптимальную марку от их инструктор. Взгляните на приведенную выше псевдо-реализацию и сравните ее с вашим. Вы можете увидеть ошибки правильно, но если нет, встаньте на плечи гигантов и переведите их на C++ (подсказки: := - простой старый = на C++, и вам нужно будет добавить ; s и брекеты). Отлаживайте результат по мере необходимости.Я не буду переводить его, потому что это почти полностью победит в задаче.

Боковых ноты (собирающие несколько важных замечаний):

При написании тестового драйвера не принимать на входе пользователя, пока вы не знаете алгоритм работы. Начните с предустановленным входом, который легко визуализировать, как

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

    } 
} 

Когда выход «ABC», измените вход на что-то более сложное, но все же легко визуализировать

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

И когда это работает идти орехи и накормить его чем-то неприятным. Мне нравится Major General's Song от Pirates of Penzance.

Answer 2

Вы можете сравнить строки с помощью std::string::compare() или реляционных операторов. Похоже, вы пробовали, используя реляционные операторы здесь, но, как @ user4581301 указал, в partition() на первую линию, у вас есть

char val = v[end]; 

Однако v[end] имеет «строки» типа, не 'char'. Если вы объявите val и temp как string вместо char, вы можете сортировать их с помощью реляционных операторов, которые у вас есть, и я думаю, что с вами все будет в порядке.

compare() документация: FTTP: //www.cplusplus.com/reference/string/string/compare/

реляционные операторы: http://www.cplusplus.com/reference/string/string/operators/