Какие тестовые случаи не учтены в коде пузырьковой сортировки на C++?

Question

Audrey

алгоритмы , cpp

Какие тестовые случаи не учтены в коде пузырьковой сортировки на C++?

Здравствуйте! Я реализую алгоритм пузырьковой сортировки строк по убыванию на C++14 без использования std::ranges и сравниваю строки стандартными операторами. Ниже представлен мой код: <br/> <pre><code class="cpp">#include &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;vector&gt;

int main() {
    std::vector&lt;std::string&gt; strs;
    std::string line;

    while (std::getline(std::cin, line)) {
        strs.push_back(line);
    }

    std::string current;

    for (size_t i = strs.size() - 1; i != 0; --i) {
        for (size_t j = 1; j &lt;= i; ++j) {
            if (strs[j - 1] &lt; strs[j]) {
                current = strs[j];
                strs[j] = strs[j - 1];
                strs[j - 1] = current;
            }
        }
    }
    
    for (size_t i = 0; i != strs.size(); ++i) {
        std::cout &lt;&lt; strs[i] &lt;&lt; "\n";
    }
}</code></pre> <br/> <br/> Я загружаю этот код в систему Яндекс.Контест, однако он не проходит 4-й тест. Не могу понять, какие дополнительные тесты мне следует проверить. Мне кажется, что я уже перепробовал множество вариантов. <br/> P.S. Хотя я мог бы сразу посмотреть решение, мне хотелось бы получить обратную связь от опытного человека. Заранее благодарю за помощь!

19 февраля 2025 г. 16:44

Ответы на вопрос 1

Похожие вопросы

Answer 1

Здравствуйте!

Ваш код для пузырьковой сортировки строк выглядит в целом правильно, но в нем есть несколько моментов, которые могут приводить к ошибкам или неэффективной работе. Также могут быть некоторые случаи, которые не были учтены. Давайте разберемся с возможными тестовыми случаями и проблемами:

1. **Проверка на пустой ввод:**
- Если входной поток не содержит строк, у вас будет пустой вектор. Проверьте, как программа обрабатывает такой случай. Она должна просто завершиться без вывода.

2. **Повторяющиеся строки:**
- Убедитесь, что ваш код правильно обрабатывает ситуации, когда входные строки повторяются. Например, при вводе следующих строк:
```
apple
apple
banana
```
- После сортировки должно быть:
```
banana
apple
apple
```

3. **Строки разной длины:**
- Проверьте, как ваш код обрабатывает строки разной длины. Например, если у вас есть строки:
```
a
aa
aaa
```
- После сортировки должно быть:
```
aaa
aa
a
```

4. **Пробелы и специальные символы:**
- Убедитесь, что строки, содержащие пробелы или специальные символы, сортируются правильно. Например:
```
!important
1important
important
```
- После сортировки порядок должен быть корректным относительно лексикографического порядка.

5. **Чувствительность к регистру:**
- Если вам не нужно учитывать регистр, используйте `std::tolower` для приведения строк к одному регистру перед сравнением. В противном случае, например:
```
apple
Apple
```
- Ваша сортировка должна учитывать, что `apple` больше, чем `Apple` в ASCII порядку.

6. **Обработка длинных строк:**
- Проверяйте код на больших объёмах данных, чтобы убедиться, что он работает эффективно и не вызывает утечек памяти.

7. **Граничные случаи:**
- Хотя это нормально, когда строки пустые, учтите крайние случаи с одной строкой (один элемент), чтобы убедиться, что сортировка не вызывает никаких ошибок.

Что касается кода, вот несколько предложений для улучшения:

- Возвращая код к более "читаемому" виду, подумайте о использовать `std::swap` для обмена значениями, что поможет избежать ручного создания временной переменной `current`.

Также стоит рассмотреть использование других эффективных сортировок, так как пузырьковая сортировка имеет O(n^2) сложность и неэффективна для больших объемов данных. Однако, если ваша цель — именно пузырьковая сортировка, то проведите указанные тесты и смотрите, где возникают проблемы.