Считается ли это допустимой функцией пузырьковой сортировки? Если да, то как я могу его улучшить? - PullRequest
Новая
       201

Считается ли это допустимой функцией пузырьковой сортировки? Если да, то как я могу его улучшить?

0 голосов
/ 07 августа 2020

Я новичок в алгоритмах сортировки, так что сейчас я более или менее просто пытаюсь понять основы. Это то, что я написал на C ++, чтобы отсортировать строку и вернуть ее символы в алфавитном порядке. Я вполне уверен, что это считается пузырьковой сортировкой, но мне бы хотелось получить подтверждение от экспертов :). Я также хотел бы узнать ваше мнение о том, как это можно улучшить? 

bool inOrder(std::string s){
    for(int i = 0; i < s.length(); i++){
        int thisLetterNum = s[i];
        int nextLetterNum = s[i + 1];
        if(thisLetterNum > nextLetterNum){
            return false;
        }
    }
return true;
}
std::string alphabetSoup(std::string str) {
    std::string &result = str;
    while(!inOrder(result)){
        for(int i = 0; i < str.length(); i++){
            int thisLetterNum = str[i];
            int nextLetterNum = str[i + 1];
            if(thisLetterNum > nextLetterNum){
                result[i] = nextLetterNum;
                result[i + 1] = thisLetterNum;
            }
        }
    }
    return result;
}

Спасибо!

Ответы [ 2 ]

0 голосов
/ 11 августа 2020

Третье улучшение. Декремент str.length() по 1 за каждый проход. Это изменяет поведение с n ^ 2 на quadrati c ((n * n) + n) / 2. Это, в сочетании с предыдущими предложениями, радикально улучшает сортировку обмена [другое название пузырьковой сортировки]. К сожалению, он по-прежнему уступает другим методам сортировки, поскольку его легко кодировать.

0 голосов
/ 07 августа 2020

Да, это форма пузырьковой сортировки.

Я также хотел бы узнать ваше мнение о том, как это можно улучшить

У вас неопределенное поведение когда i = length() - 1, потому что вы используете str[i + 1], поэтому исправление этого является первым улучшением, которое я бы предложил.

Вы также можете сделать меньше итераций и пропустить inOrder(). Вы можете отслеживать, в порядке ли это, отмечая, сделали ли вы обмен или нет.

Пример: 

std::string alphabetSoup(std::string str) {
    bool swapped;
    size_t ei = str.length();
    do {
        --ei; // you can decrease this each iteration since the last element will be in
              // the correct place after each iteration
        swapped = false;
        for(size_t i = 0; i < ei; ++i) {
            if(str[i + 1] < str[i]) {
                std::swap(str[i], str[i + 1]);
                swapped = true;
            }
        }
    } while(swapped);

    return str;
}
...