21強選択ソート

8422 ワード

ソートは

  • データは特定の基準に従って
  • 並べ替えられる.
  • は、通常、問題の状況に応じて、対応するソートアルゴリズムを式として使用する.
  • 選択ソートとは


    未処理のデータの中から最小のデータを選択し、一番前のデータとの置換を繰り返します.

    動作原理


    最後の9の範囲は1つしかないので、処理する必要はありません.
    注意:二重繰り返し文を使用して選択ソートを実現
  • を繰り返すたびに探索範囲は縮小する.
  • は線形ナビゲーション(左から右へ順次ナビゲート)を実行し、ナビゲーション範囲内でデータを表示するたびに最小要素
  • を検索する.

    public class Main {
    
        public static void main(String[] args) {
    
            int n = 10;
            int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
    
            // arr[i] : 가장 작은 원소와 위치가 바뀔 인덱스 (탐색 범위 내 가장 앞쪽 인덱스)
            for (int i = 0; i < n; i++) {
            	// 가장 작은 원소의 인덱스 (일단 탐색 범위 내 가장 앞쪽 인덱스로 초기화)
            	int min_index = i; 
            	// 선형 탐색(순차 탐색)으로 i~n까지 중 가장 작은 원소의 인덱스를 찾아 저장한다.
            	// 외부 for문의 마지막 회차(i가 9)에는 내부 for문이 j < n 에 벗어나므로 내부 for문 작동 X
                for (int j = i + 1; j < n; j++) {
                    if (arr[min_index] > arr[j]) {
                        min_index = j;
                    }
                }
                // 스와프
                int temp = arr[i];
                arr[i] = arr[min_index];
                arr[min_index] = temp;
            }
    
            for(int i = 0; i < n; i++) {
                System.out.print(arr[i] + " ");
            }
        }
    }
    

    時間の複雑さ

  • ソートを選択するには、最小のN回(=外部が文)を検索し、最上位の
  • に送信する必要がある.
  • の実施形態によれば、微小な誤差があるかもしれないが、合計算出回数
    n(n+1)/2 => (n^2+n)/2 => O(N^2)
  • [前の例の時間的複雑さ]
    O(N) + O(N^2) => O(N^2)
    -外部for文:0 1 2 3 4 5 6 7 8 9(1番目):O(N)
    -内部for文:9 8 7 6 5 4 3 1 0(繰り返し回数):O(N^2)
    문제에서 주어진 배열의 길이 N10일 때 
    내부for문의 총 반복 횟수(9+8+7+...+2+1)를 구하려면
    (n-1)((n-1)+1)/2 => n(n-1)/2 => O(N^2)
    注意:等差数列式
    n + (n-1) + (n-2) + ... + 2 + 1 => n(n+1)/2
    注意:
    iではなく最大値定数(ex.999999)をmin index変数に入れると、
    10+9+8+7...+2+1を繰り返すと等差数列式(n(n+1)/2)が受け入れられる