C++の基礎 - ソートのソースを表示

== 概要 ==

<br><br>

== 単純選択法 (選択ソート) ==
単純選択法 (選択ソート) は、未ソートの部分から最小値 (または最大値) を見つけて、それを適切な位置に配置していくアルゴリズムである。<br>
<br>
# まず、データ列の先頭から順に、その位置以降で最小の要素を探索する。
# 最小の要素が見つかった場合、探索を開始した位置の要素と交換する。
# この操作を、配列の最後の要素の手前まで繰り返すことにより、データを昇順 (または降順) に整列することができる。
<br>
例えば、{5, 3, 1, 4, 2}という配列をソートする場合、<br>
まず最初の位置から開始して、全体から最小値 (この場合では1) を見つけて、最初の位置 (この場合では5) と交換する。<br>
次に、2番目の位置 (この場合では3) から開始して残りの要素から次の最小値の2を見つけて、3と交換する。<br>
この処理を順々に繰り返す。<br>
<br>
単純選択法のアルゴリズムの特徴として、データの並びに関係なく常に一定の比較回数が必要となるため、効率は悪い。<br>
配列の長さをnとすると、計算量は <math>O(n^2)</math> となる。<br>
また、既にある程度ソートされているデータに対しても、完全にランダムなデータと同じ処理時間が掛かるという特徴がある。<br>
ただし、必要な追加のメモリ容量が少ないというメリットがある。<br>
<br>
 <syntaxhighlight lang="c++">
 #include <iostream>
 
 using namespace std;
 
 int main()
 {
    // 配列 (要素数8) を初期化
    int arr[8] = {64, 34, 25, 12, 22, 11, 90, 50};
    int n = 8;  // 配列のサイズ
 
    cout << "ソート前の配列: ";
    for (int i = 0; i < n; i++) {
       cout << arr[i] << " ";
    }
    cout << endl;
 
    // 選択ソートのアルゴリズム
    for (int i = 0; i < n - 1; i++) {
       // 未ソート部分から最小値を探す
       int min_idx = i;
       for (int j = i + 1; j < n; j++) {
          if (arr[j] < arr[min_idx]) {
             min_idx = j;
          }
       }
 
       // 最小値を見つけたら、現在の位置と交換
       if (min_idx != i) {
          int temp     = arr[i];
          arr[i]       = arr[min_idx];
          arr[min_idx] = temp;
       }
 
       // 各ステップでの配列の状態を表示
       cout << "ステップ " << i+1 << ": ";
       for (int k = 0; k < n; k++) {
          cout << arr[k] << " ";
       }
       cout << endl;
    }
 
    cout << "ソート後の配列: ";
    for (int i = 0; i < n; i++) {
       cout << arr[i] << " ";
    }
    cout << endl;
 
    return 0;
 }
 </syntaxhighlight>
<br>
 # 出力例:
 ソート前の配列: 64 34 25 12 22 11 90 50
 
 ステップ 1: 11 34 25 12 22 64 90 50
 ステップ 2: 11 12 25 34 22 64 90 50
 ステップ 3: 11 12 22 34 25 64 90 50
 ステップ 4: 11 12 22 25 34 64 90 50
 ステップ 5: 11 12 22 25 34 64 90 50
 ステップ 6: 11 12 22 25 34 50 90 64
 ステップ 7: 11 12 22 25 34 50 64 90
 
 ソート後の配列: 11 12 22 25 34 50 64 90
<br><br>


{{#seo:
|title={{PAGENAME}} : Exploring Electronics and SUSE Linux | MochiuWiki
|keywords=MochiuWiki,Mochiu,Wiki,Mochiu Wiki,Electric Circuit,Electric,pcb,Mathematics,AVR,TI,STMicro,AVR,ATmega,MSP430,STM,Arduino,Xilinx,FPGA,Verilog,HDL,PinePhone,Pine Phone,Raspberry,Raspberry Pi,C,C++,C#,Qt,Qml,MFC,Shell,Bash,Zsh,Fish,SUSE,SLE,Suse Enterprise,Suse Linux,openSUSE,open SUSE,Leap,Linux,uCLnux,Podman,電気回路,電子回路,基板,プリント基板
|description={{PAGENAME}} - 電子回路とSUSE Linuxに関する情報 | This page is {{PAGENAME}} in our wiki about electronic circuits and SUSE Linux
|image=/resources/assets/MochiuLogo_Single_Blue.png
}}

__FORCETOC__
[[カテゴリ:C++]]