C++のバブルソートのロジックが動かない

Question

バブルソートを0から実装しているのですが、バブルソートが適用されていません。

どこがおかしいのでしょうか？

gcc (Ubuntu 8.3.0-6ubuntu1) 8.3.0
gcc -o BubbleSort BubbleSort.cpp -lstdc++

#include <iostream>        
#include <vector>          
using namespace std;       
                           
void BubbleSort(vector<int>& v) {
    size_t s = v.size();
    for (int i = 0; i < s; ++i) {
        for (int j = 0; j >= (i + 1); ++j ) { 
            if (v[j] < v[j -1]) {
                int tmp = v[j];
                v[j] = v[i];
                v[i] = tmp;
            }              
        }                  
    }                      
    return;                
}                          
                           
int main() {               
    vector<int> v = {2,1,3};
                           
    for (int i = 0; i <= 2; ++i) {                                                                                                                            
        cout << v[i] << endl;
    }                      
                           
    BubbleSort(v);         
                           
    size_t s = v.size();
    for (int i = 0; i < s; ++i) {
      cout << v[i] << endl;
    }                      
    return 0;              
}                          
        

2
1
3
2
1
3

よろしくお願いいたします。

Answer 1

for (int i = 0; i < s; ++i) {
        for (int j = 0; j >= (i + 1); ++j ) { 

この部分、i に実際の数値を当てはめてどうなるか書いてみてください。
内側のループは j >= (i + 1) が満たされている間、回ります。

追記

if (v[j] < v[j -1]) {

j は 0 になるのでここもかなりまずいですね。

Answer 2

うーん、単にソートしたいだけならC++にもソート系関数があった気が...

ProgrammingPlace Plusとか?

課題とかで実装しなければいけないなら、

C++で様々なソートアルゴリズムを実装する...とかどうでしょうか?

これらを見る限り、バブルソートは

1. 要素数分、行う
2. 後ろから前に突撃(笑)
3. 比較...

となっています。

質問者さんのコードを見ると、

void BubbleSort(vector<int>& v) {
    size_t s = v.size();
    for (int i = 0; i < s; ++i) {
        for (int j = 0; j >= (i + 1); ++j ) { 
            if (v[j] < v[j -1]) {
                int tmp = v[j];
                v[j] = v[i];
                v[i] = tmp;
            }              
        }                  
    }                      
    return;                
}   

最初のforはいいとしても、二番目のforが...

初期値: 0, 条件: j(このforの独自の変数)が i+1(外側のforの変数に+1)より大きい間, jをインクリメント

となっています。

これが原因じゃないなかなぁと。

これを if( int j = s - 1; j > i; j-- )と単純に書いてみては?

ただし、上記サイトにあるように、「自分なりに」やってください。

そして、今回は有名なアルゴリズムなので探しやすいですが、こういう場合は「実際に数字や文字列を入れて考えてみる」のがコツかなぁと。

たとえば、もしv.sizeが 1 だったら?
v.size が 10 だったら?
v.size が 100だったら?
v.size が 3 だったら?
...

と実際に値を入れて検証してみる。

例えば、0～10までの数字で行うとするなら、i = 0 のとき、i = 1 のとき、i = 2 のとき...と「手作業で」検証してみる。

電卓を使ってもいいですし、Excelでもいいです。
とにかく、数字とかを適当に入れて検証してみる。

すると、ロジックがおかしい場合、「どこかがずれている」状態になります。

i = 1　なら最終的な値は x = 100 になるはずが、 x = 80 となっていたりとか。
この場合、差は20ですが、どこかで -20 をしているか、追加する数字が足りない...とかのような感じでロジックがおかしいっていう風に。

後は、デバッガを使うとか。

Answer 3

素直に書くならこうだと思います

    for (int i = 1; i < s; ++i) {
        for (int j = 0; j < s; ++j ) { 
            if (v[i] < v[i+1]) {
               ...
            }              
        }
    }                  

Comments

[Zuishin]

バブルソートってそんなんでしたっけ？

[izmktr]

バブルソートって学習用ソートですよ？

[Zuishin]

アルゴリズムの名前ですよ？

[Zuishin]

もしかして、学習用は全部バブルソートという認識でしたか？

[izmktr]

ここでフレームになるようなことをしたくないんですけど…
最適化することはバブルソートの要件ではありません
比較を途中で打ち切ったり、始点や終点の最適化をしてシェーカーソートと同等の効率まで引き上げてもバブルソートであるように、
最高に最適化されていないものも同等にバブルソートでしょう
そうやって、最終的に挿入ソートへ至る道までがバブルソートだと考えます

[Zuishin]

最適化の話などしていません。https://www.codereading.com/algo_and_ds/algo/insertion_sort.html

劣化挿入ソートではありませんか？

[Zuishin]

バブルソートはデータがバブルのように浮いてくることからその名が付けられています。

[Zuishin]

いや、挿入ソートとも違いますね。何だろう。

[Zuishin]

失礼。選択ソートだと思います。

[izmktr]

if文の中がおかしいって話ですか、
(そこならそう指摘してほしい)
他の人もいるし、この記事消しておきます

[Zuishin]

記事は消さず残しておいてください。私もよく間違えますが、間違えたら間違えたと書いて訂正していますし、それがここのルールでもあったと思います。