次の選択ソートコードとの混乱

Question

int i,j,t; 

for(i=0;i<n-1;i++) 
{ 
    for(j=i+1;j<n;j++) 
    { 
     if(a[i]>a[j]) 
     { 
      t=a[i]; 
      a[i]=a[j]; 
      a[j]=t; 
     } 
    } 
} 

私の質問は、上記のコードが正しい選択ソートコードであるかどうかです。私は様々な本からこのコードを手に入れました。それが間違っている場合は、理由を説明してください。

Answer 1

はいコードは正しいです。基本的には、配列を昇順にソートするには高価なO(n^2)が必要です。

各ステップi [0..n-1]で、[i..n-1]のインデックスの中で最小の要素をインデックスiに配置します。

スワップ機能を使用すると、iインデックスにある2つの比較値の小さい方の値を置く連続ていることを確認します。

Answer 2

私の見解では、質問に表示されるソートは選択ソートではなくバブルソートです。

私はアーカイブの中で蹴っているコードの中に、さまざまなソートアルゴリズムのテストベッドがあります。テストベッドにはバブル、選択、挿入、クイックソートが含まれ、比較とスワップを監視します。

一種であるバブルソートと選択のためのコード：

static void selection_sort(Data a[], int n) 
{ 
    for (int i = 0; i < n - 1; i++) 
    { 
     int min = i; 
     for (int j = i + 1; j < n; j++) 
     { 
      inc_comps(); 
      if (a[j] < a[min]) 
       min = j; 
     } 
     inc_comps(); 
     if (min != i) 
      swap(&a[min], &a[i]); 
    } 
} 

static void bubble_sort(Data a[], int n) 
{ 
    for (int i = n - 1; i > 0; i--) 
    { 
     for (int j = 0; j < i; j++) 
     { 
      inc_comps(); 
      if (a[j] > a[j+1]) 
       swap(&a[j], &a[j+1]); 
     } 
    } 
} 

バブルの外側のループは、ソートというよりも、アップダウンカウントが、より重要な点は、その選択である理由私は今覚えていません。ソートは質問に表示されているコードとは大きく異なり、質問内のコードはバブルソートに非常によく似ています。

ウィキペディアでは、これらのアルゴリズムと他の多くのアルゴリズムが概説されているSorting Algorithmと、ソートに関する複数の情報源へのリンクを参照することもできます。

テストベッドは、異なるサイズのデータ​​セットで異なるデータパターンを使用して異なるアルゴリズムを実行します。あなたがなく、とてもよく数に、それが実行するスワップの数にも、データから選択ソートのスコアを見ることができるように

Number    Filler Sorter  Compares   Swaps    Time 
    10000    Random  Quick   151583   88111 PASS 0.000593 
    10000    Random Bubble  49995000  24895500 PASS 0.143897 
    10000    Random Insertion  24905489  24895500 PASS 0.028966 
    10000    Random Selection  50004999   9986 PASS 0.040409 
    10000   Ascending  Quick   151719   90480 PASS 0.000584 
    10000   Ascending Bubble  49995000  24876354 PASS 0.141219 
    10000   Ascending Insertion  24886345  24876354 PASS 0.022601 
    10000   Ascending Selection  50004999   9988 PASS 0.041173 
    10000   Descending  Quick   119881   74247 PASS 0.000251 
    10000   Descending Bubble  49995000  49995000 PASS 0.081584 
    10000   Descending Insertion  49995000  49995000 PASS 0.055118 
    10000   Descending Selection  50004999   5000 PASS 0.050586 
    10000 Forward Organ Pipe  Quick  25000000  25005000 PASS 0.034033 
    10000 Forward Organ Pipe Bubble  49995000  24995000 PASS 0.070633 
    10000 Forward Organ Pipe Insertion  25004999  24995000 PASS 0.022398 
    10000 Forward Organ Pipe Selection  50004999   9987 PASS 0.048300 
    10000 Reverse Organ Pipe  Quick  25005002  16665004 PASS 0.025632 
    10000 Reverse Organ Pipe Bubble  49995000  24995000 PASS 0.064798 
    10000 Reverse Organ Pipe Insertion  25000000  24995000 PASS 0.022568 
    10000 Reverse Organ Pipe Selection  50004999   9886 PASS 0.053838 
    10000   Uniform  Quick  49995000   19998 PASS 0.030855 
    10000   Uniform Bubble  49995000    0 PASS 0.038719 
    10000   Uniform Insertion   9999    0 PASS 0.000021 
    10000   Uniform Selection  50004999    0 PASS 0.041021 

：出力の一部は、データの10,000行（タイプint）のためであります比較。これは、問題のアルゴリズムが選択ソートではなく、バブルソートであるという私の観察を検証する方法を提供します。