Сортировка заданного текста по алфавиту без дополнительной библиотеки

Question

Моя домашняя работа заключалась в написании приложения, которое сортирует заданный текст в алфавитном порядке. Для этого мне было разрешено использовать только библиотеки 'vector', 'string' и 'iostream'.

Я добился успеха, но теперь борюсь со странной проблемой - хотя я пытаюсь отсортировать короткий текст, все работает хорошо, но при более длинных входах программа, похоже, попадает в бесконечный цикл или проблему эффективности. Например, в тексте

"Albert Einstein 14 March 1879 – 18 April 1955 was a German-born theoretical physicist who developed the theory of relativity one of the two pillars of modern physics alongside quantum mechanics His work is also known[...]" 

все прекрасно работает до фразы "механика". После добавления этого или любого другого слова программа работает вечно, как я упоминал ранее.

Боюсь, что в этом случае мне нужно вставить весь код (пожалуйста, прости).

#include <iostream>
#include <string>
#include <vector>

int compare(std::string first, std::string second){
    int flag = 1;
    int i;
    if (first.size() <= second.size()){
        for (i = 0; i<first.size(); ++i ){
            if (first[i] == second[i]){
                continue;}
            else if (first[i] > second[i]){
                flag = 0;
                break;}
            else {
                break;}}}
    else {
        for (i = 0; i<second.size(); ++i ){
            if (first[i] == second[i]) {
                continue;}
            else if (first[i] > second[i]){
                flag = 0;
                break;}
            else {
                break;}
        }
        int m = second.size() - 1;
        if (first[m] == second[m]){
                flag = 0;}}
return flag;}


int main() {
    std::vector<std::string> text;
    std::string word;
    std::string tmp;
    while(std::cin >> word){
        text.push_back(word);}
    int mistakes, m = 1;
    while(m) {
        mistakes = 0;
        for (int index = 1; index < text.size() ; ++index){
            if (!(compare(text[index-1], text[index]))){
                tmp = text[index];
                text[index] = text[index-1];
                text[index-1] = tmp;
                mistakes += 1;}}
        m = mistakes;}
    for (auto element: text){
        std::cout << element << " ";}}

Мне бы очень хотелось услышать, как это исправить и почему именно эта проблема возникает - по крайней мере, время выполнения не увеличивается с длиной ввода, но больше похоже на «работает / не работает», что в отличие от вопросов эффективности.

Answer 1

Вы пропустили некоторые условия, из-за которых ваш цикл while работает бесконечно. Например:

1. Ваша переменная ошибок , значение которой выполняет цикл while, никогда не становится равным 0, если самая первая пара слов находится в неправильном порядке. Отрицательный тестовый случай будет: «шариковое яблоко». В этом случае ваш код работает бесконечно.

2. В вашем методе сравнения из-за следующей строки кода тестовый пример, как этот "яблочный шар", давал неправильные ответы. Здесь first [m] = second [m] = l, поэтому в соответствии с вашим условием он вернет false и поменяет их местами. Он заменит «Яблоко» на «Мяч», что неправильно.

   int m = second.size() - 1;
       if (first[m] == second[m]){
               flag = 0;
   }
   

3. Вам также необходимо обработать случаи, когда будет сравнение между прописными и строчными буквами. Например: «Месяц также». В этом случае ответом должен быть также «Месяц». Поэтому, прежде чем сравнивать две строки, вы должны привести их к одному и тому же регистру, а затем сравнить.

4. Случай сравнения чисел, где 1874 должен следовать после 18. (вы можете добавить это)

Ниже приведен исправленный код.

---

#include <iostream>
#include <string>
#include <vector>
#include <cctype>

int compare(std::string first, std::string second){

    // this is to handle the comparison of two words with mixed case(upper/lower) of letters.
    // earlier solution failed for comparison between 'Month' and 'a'
    for(int i=0;i<first.size();i++){
        first[i] = tolower(first[i]);
    }

    for(int i=0;i<second.size();i++){
        second[i] = tolower(second[i]);
    }

    int flag = 1;
    int i;
    if (first.size() <= second.size()){
        for (i = 0; i<first.size(); ++i ){
            if (first[i] == second[i]){
                continue;}
            else if (first[i] > second[i]){
                flag = 0;
                break;}
            else {
                break;}}}
    else {
        for (i = 0; i<second.size(); ++i ){
            if (first[i] == second[i]) {
                continue;}
            else if (first[i] > second[i]){
                flag = 0;
                break;}
            else {
                break;}
        }

    }
    return flag;}


    int main() {
    std::vector<std::string> text;
    std::string word;
    std::string tmp;
    while(std::cin >> word){
        text.push_back(word);}



    // bubble short
    for(int i=0;i<(text.size()-1);i++){

        for(int j=0;j<(text.size()-1-i);j++){
            if (!(compare(text[j], text[j+1]))){
                tmp = text[j];
                text[j] = text[j+1];
                text[j+1] = tmp;
            }
        }
    }



    for (auto element: text){
        std::cout << element << " ";}}