このバブルソートを別の方法で実装するにはどうすればよいですか？

Question

バブルソートを実装しようとしています。私は、doループの内部にforループを使用する次のコードを書いています。これを2つのループを使用するバブルソートにするにはどうすればよいですか？

ここに私のコードです：

do { 
    switched = false; 
    for (int i = 1; i < size; i++) { 
     if (a[i] < a[i-1]) { 
      int temp = a[i]; 
      a[i] = a[i-1]; 
      a[i-1] = temp; 
      switched = true; 
     } 
    } 
} while (switched); 

（これは宿題をタグ付けされたが、これは最終試験ではなく、実際の宿題のために勉強している）

Answer 1

リストの最後の要素が常にソートされていることがわかっているので（上から泡立っているので）、そこで停止することができます。

for(int x = size; x >= 0; x--) { 
    bool switched = false; 
    for(int i = 1; i < x; i++) { 
     if(blah) { 
      // swap code here 
      switched = true; 
     } 

    } 
    if(!switched) break; // not the biggest fan of this but it gets the job done 
} 

Answer 2

ビット絶対、ちょっと、あなたはそれを求め：

ループの

for(bool switched=true; switched;) 
{ 
    switched = false; 
    for (int i = 1; i < size; i++) { 
     if (a[i] < a[i-1]) { 
      int temp = a[i]; 
      a[i] = a[i-1]; 
      a[i-1] = temp; 
      switched = true; 
     } 
    } 
} 

つ...

Answer 3

あなたは内側のループを実行することができますをチェックする代わりに、外側ループfor(int j=0; j<size; ++j)をチェックする代わりに回。それを少し悪く非効率的にするために、毎回内部ループを1ステップ短くすることができます。

Answer 4

ループの最初のフルパス（つまり、ループの最初の反復であるdo）は、最大要素を位置a[size - 1]に配置することが保証されています。 （理由は分かりますか？）次のフルパスは、との2番目に大きい要素を位置a[size - 2]に置くことが保証されています。 （やはり、あなたはなぜそれを見ますか？）などです。だから、最初のパスは1からsize - 1に行くためにiを必要としますが、2番目は唯一の3分の1が唯一のように1からsize - 3に行くためにiを必要とし、1からsize - 2に行くためにiを必要とします。全体として、最大でsize - 1のパスが必要です（最後のパスは位置をカバーし、a[1]〜a[0]を比較すると最小の要素が適切に配置されていることを確認してください）。

ので、max_iに1からiを変化させるために必要-loop当初size - 1に設定し、1で終わる、max_iを変更する必要があり、あなたの内側のfor -loopあなたの外側for。

Answer 5

はdoループが実行できる最大回数について考えてみよう。

Answer 6

内部ループが実行される最大回数はsize回であるため、外側ループのみをsizeでバインドすることができます。次のようにループのための2つを使用する

for (int x = 0; x < size; x++) 
{ 
    switched = false; 
    for (int i = 1; i < size; i++) 
    { 
     if (a[i] < a[i - 1]) 
     { 
      int temp = a[i]; 
      a[i] = a[i - 1]; 
      a[i - 1] = temp; 
      switched = true; 
     } 
    } 

    if(switched) 
    { 
     break; 
    } 
} 

Answer 7

A本当に愚かな方法は次のようになります。

for(bool switched=true;switched;) 
{ 
    switched=false; 
    for(int i=1; i<size; ++i) 
    { 
     if (a[i] < a[i-1]) 
     { 
      int temp = a[i]; 
      a[i] = a[i-1]; 
      a[i-1] = temp; 
      switched = true; 
     } 
    } 
} 

より深刻な答えは以下の通りであるかもしれません...

for(int i=0; i<(size-1); ++i) 
{ 
    for(int j=(i+1); j<(size-1); ++j) 
    { 
     if(a[i]>a[j]) 
     { 
      temp=a[i]; 
      a[i]=a[j]; 
      a[j]=temp; 
     } 
    } 
} 

Answer 8

バブルソートへの単純な改善がスワップが発生した最後場所を覚えておくことですが、今、私はそれについて考える、これはおそらく、バブルソートではありません。各パスの後、その点を超える要素がソートされます。次回ループを通過すると、前の最高水準点まで反復されます。

void bubble_sort(int *arr, int size) 
{ 
    for (int hwm; size > 1; size = hwm) 
    { 
     hwm = 0; 
     for (int i = 1; i < size; ++i) 
     { 
      if (arr[i] < arr[i-1]) 
      { 
       std::swap(arr[i], arr[i-1]); 
       hwm = i; 
      } 
     } 
    } 
}