C++でのバブルソートの実装

Question

バブルソートの実装には、以下のコードを使用します。この場合、テンプレートはなぜ使用されますか？ swapped variabeの目的は何ですか？私はループコードから変数swappedとswapped conditionを削除しても、まだ細かい

#include <algorithm> 
#include <iostream> 
#include <iterator> 

template <typename RandomAccessIterator> 
void bubble_sort(RandomAccessIterator begin, RandomAccessIterator end) { 
    bool swapped = true; 
    while (begin != end-- && swapped) { 
    swapped = false; 
    for (auto i = begin; i != end; ++i) { 
     if (*(i + 1) < *i) { 
     std::iter_swap(i, i + 1); 
     swapped = true; 
     } 
    } 
    } 
} 

int main() { 
    int a[] = {100, 2, 56, 200, -52, 3, 99, 33, 177, -199}; 
    bubble_sort(std::begin(a), std::end(a)); 
    copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " ")); 
    std::cout << "\n"; 
} 

別の実装を動作します：

template<typename Iterator> 
void bubbleSort(Iterator first, Iterator last) 
{ 
    Iterator i, j; 
    for (i = first; i != last; i++) 
     for (j = first; j < i; j++) 
      if (*i < *j) 
       std::iter_swap(i, j); // or std::swap(*i, *j); 
} 

Answer 1

異なるコンテナには独自のイテレータタイプがあります。たとえば、1次元配列の場合はイテレータとしてポインタが使用され、std :: vector型のオブジェクトの場合はこのテンプレートクラスで定義されたイテレータが使用されます。

変数swappedは、要素が既にソートされているかどうかの基準として使用されます。トラバースされたときにシーケンスの要素が入れ替わらなかった場合は、シーケンスが既にソートされていることを意味します。

範囲を空にすることができたときに、最後のイテレータをデクリメントしようとする試みがあるので、あなたが示した実装が原因この文

while (begin != end-- && swapped) { 
       ^^^^ 

に未定義の動作をしていることを考慮してください。したがって、実装は間違っています。

さらにアルゴリズムは効率的ではありません。例えば、配列の末尾は、内部ループの何回かの反復の後に既にソートされていてもよい。しかし、外部ループでは、最後のイテレータは1つだけの位置に移動します。

バブルソートには順方向イテレータを使用すれば十分です。この場合、std::forward_listとランダムアクセスイテレータを持たないコンテナでもアルゴリズムを使用できます。

ここでは、フォワードイテレータを使用してアルゴリズムを実装する方法を示すデモンストレーションプログラムです。

#include <iostream> 
#include <algorithm> 
#include <iterator> 
#include <forward_list> 

template <typename ForwardIterator> 
void bubble_sort(ForwardIterator first, ForwardIterator last) 
{ 
    for (ForwardIterator sorted = first; first != last; last = sorted) 
    { 
     sorted = first; 
     for (ForwardIterator current = first, prev = first; ++current != last; ++prev) 
     { 
      if (*current < *prev) 
      { 
       std::iter_swap(current, prev); 
       sorted = current; 
      } 
     } 
    } 
} 

int main() 
{ 
    int a[] = { 100, 2, 56, 200, -52, 3, 99, 33, 177, -199 }; 

    bubble_sort(std::begin(a), std::end(a)); 
    std::copy(std::begin(a), std::end(a), 
       std::ostream_iterator<int>(std::cout, " ")); 
    std::cout << "\n"; 

    std::forward_list<int> lst = { 100, 2, 56, 200, -52, 3, 99, 33, 177, -199 }; 

    bubble_sort(std::begin(lst), std::end(lst)); 
    std::copy(std::begin(lst), std::end(lst), 
       std::ostream_iterator<int>(std::cout, " ")); 
    std::cout << "\n"; 
} 

プログラムの出力は、プログラムでアレイとタイプstd::forward_listのオブジェクトが使用され、アルゴリズムは両方の容器にも適用することができる

-199 -52 2 3 33 56 99 100 177 200 
-199 -52 2 3 33 56 99 100 177 200 

ここあります。

Answer 2

テンプレートは、異なる種類の機能を使用しての利便性のために、単にそこにあります。単純な配列ではなく、イテレータを使用する関数を実装すると、ポインタとサイズに関する多くの問題を解決できます。

変数swappedは、最後に実行されたのがbeginからendまでであることをアルゴリズムに示すため、スワップは発生しませんでした。これは、配列が既にこの範囲内にソートされていることを意味します（これは、以前のパスで処理されたものであるため、endをソートしたものです）。beginとendイテレータが同じになるまでループする必要はありません。このチェックを外すとアルゴリズムは機能しますが、部分的にソートされた配列の場合は時間が浪費される可能性があります。

はのは、この例を見てみましょう：

0: {1 2 5 3 4} (begin = 0, end = 4) 
1: {1 2 3 4 5} (begin = 0, end = 3) 
2: {1 2 3 4 5} (begin = 0, end = 2) 
3: {1 2 3 4 5} (begin = 0, end = 1) 
4: {1 2 3 4 5} (begin = 0, end = 0) 

あなたは0:後に配列がすでにソートされていることを見ることができますが、swappedフラグなしアルゴリズムが破損してチェックを続けないだろう。 1:の後にフラグがある場合、swappedフラグはfalseであり、アルゴリズムは終了します。