ソート[アルゴリズムc++]選択

選択ソートアルゴリズムは、最小の数字を一番前に入力し、入力した数字の一番前の数字と配列中の数字を交換する昇順、降順で並べられたアルゴリズムです.

#include <stdio.h>

int main(void) {
  int i, j, min, index, temp;
  int array[10] = {10,1,5,8,7,6,4,3,2,9};
  for(i=0; i<10; i++){
     min = 9999;
     for(j=i; j< 10; j++){
     if(min > array[j]){
        min= array[j];
        index = j;
     }
     }
     temp = array[i];
     array[i] = array[index];
     array[index] = temp;
  }
  
  
  for(i = 0; i< 10;i++){
     printf("%d ", array[i]);
  }
  
  return 0;
}

上記の例のように、選択ソートアルゴリズムを使用して長さ10の配列をソートします.
等差数列で表し、以下のようになります.
10 + 9 + 8 + ... + 1
55回の参照が発生します.
10 * (10 + 1)/2
N * (N + 1)/2
時間複雑度を判断するbigoマーキング法では,+1または/2などの小数を省略する.
O(N*N)式が表示されます.
選択ソートの時間的複雑度はO(N^2)である.
つまり配列の長さが10000であれば1000*10000,000,000=1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000の参照が発生し,非常に非効率なアルゴリズムといえる^^;
ビオマーク
:アルゴリズムでは大文字Oを用いて時間の複雑さを表す記号.O(n)、O(2)などと表す.
注意:https://ndb796.tistory.com/