選択の位置合わせ、挿入の位置合わせ

15261 ワード
アルゴリズム概念 テキストリンク

1.ソート選択


この順序で要素を配置する位置が決定され、どの要素を配置するかを選択するアルゴリズム

1.1並べ替えプロセス

  • で指定された配列で最小値を探します.
    • 値
  • を一番前の値に置き換えます.(pass)
  • は、第1の位置を除いた残りの配列を同様の方法で置換する.

    • 1.2コード


    1.2.1 Java

    void selectionSort(int[] arr) {
    int indexMin, temp;
    for (int i = 0; i < arr.length-1; i++) {        // 1.
        indexMin = i;
        for (int j = i + 1; j < arr.length; j++) {  // 2.
            if (arr[j] < arr[indexMin]) {           // 3.
                indexMin = j;
            }
        }
        // 4. swap(arr[indexMin], arr[i])
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
  }
  System.out.println(Arrays.toString(arr));
}

    1.2.2 Python

    def selection_sort(a):
    size = len(a)
    for i in range(size):
        minidx = i
        for j in range(i+1,size):
            if(a[minidx]>a[j]):
                minidx=j
        a[minidx],a[i] = a[i],a[minidx]
arr = [9,1,22,4,0,-1,1,22,100,10]
selection_sort( arr )
print( arr )
# [-1, 0, 1, 1, 4, 9, 10, 22, 22, 100]

    1.3複雑度


    1.3.1時間の複雑さ


    n個のデータがある場合、

  • 1回目の回転の比較回数:1~(n-1)=>n-1

  • 2回目の回転の比較回数:2~(n-1)=>n-2
    ...
  • (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2
    • 従って,最適,平均,最悪の場合,時間複雑度はO(n^2)である.

    1.3.2空間複雑度


    与えられた配列では,交換(swap)により並べ替えられ,O(n)となる.

    1.4メリットとデメリット


  • 長所

  • Bubble sortと同様にアルゴリズムは非常に簡単です

  • Bubble Sortと同様に、ソートする配列で交換され、他のメモリ領域は必要ありません.
    =>その場でソート

  • 短所
  • 不安定な順序付け(Unstable Sort)

    • 2.整列挿入


    すべての要素を並べ替えられた配列部分と順番に比較し、それらの位置を検索して挿入することによって並べ替えを完了するアルゴリズム.

    2.1並べ替えプロセス

  • ソートは、2番目の位置(インデックス)の値をtempに格納する.
  • tempを前の要素と比較して挿入します.
  • 「1」号を返し、次の場所(インデックス)の値をtempに保存し、繰り返します.

    • 2.2コード


    2.2.1 Java

    void insertionSort(int[] arr)
{
   for(int index = 1 ; index < arr.length ; index++){ // 1.
      int temp = arr[index];
      int prev = index - 1;
      while( (prev >= 0) && (arr[prev] > temp) ) {    // 2.
         arr[prev+1] = arr[prev];
         prev--;
      }
      arr[prev + 1] = temp;                           // 3.
   }
   System.out.println(Arrays.toString(arr));
}

    2.2.2 Python

    def insertion_sort(arr):
    for i in range(1, len(arr)) :
        j = i-1
        temp = arr[i]
        while j>=0 and arr[j]>temp :
            arr[j+1] = arr[j]
            j-=1
        arr[j+1] = temp
        
arr = [9,1,22,4,0,-1,1,22,100,10]
insertion_sort(arr)
print( arr )
# [-1, 0, 1, 1, 4, 9, 10, 22, 22, 100]

    2.3複雑度


    2.3.1時間複雑度


  • 最悪の場合
  • (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2
  • すなわちO(n^2)

  • 最良の場合
  • 並べ替えられた
  • を1回だけ比較するのでO(n)

    • 2.3.2空間複雑度


    与えられた配列では,交換(swap)により並べ替えられ,O(n)となる.

    2.4メリットとデメリット


  • 長所

  • ほとんどの要素が整列されている場合、非常に効率的です.

  • ソートする配列でスワップする方法なので、他のメモリ領域は必要ありません.=>その場でソート

  • 安定した順序付け.

  • ソートや泡ソートなどのO(n^2)を選択しますが、比較的速いです.

  • k+1個の要素を配置するのに必要な任意の数の要素のみを参照するため、ソートを挿入する方が効率的です.
    ソートを選択するには、k+1要素を検索するために残りのすべての要素をナビゲートする必要があります.

  • 短所
  • O(n^2)、遅い
    • bootstrapの概要
    [白駿2941 Python]-クロアチア文字