sorting => 選択

備考

コンピュータサイエンスでは、選択ソートはソートアルゴリズム、特にインプレース比較ソートです。それはO（n ² ）時間の複雑さを有し、大きなリストでは非効率であり、一般的に同様の挿入分類より悪い。選択ソートはそのシンプルさから注目されており、特に補助メモリが限られている状況では、より複雑なアルゴリズムよりもパフォーマンス上の利点があります。

下の図は、選択ソートの仕組みを示しています。

擬似コードの下では、プログラムの作成（どの言語でも）や選択ソートの理解に役立ちます。

procedure selection sort 
list  : array of items
n     : size of list

for i = 1 to n - 1
/* set current element as minimum*/
  min = i    

  /* check the element to be minimum */

  for j = i+1 to n 
     if list[j] < list[min] then
        min = j;
     end if
  end for

  /* swap the minimum element with the current element*/
  if indexMin != i  then
     swap list[min] and list[i]
  end if

end for

end procedure

利点：

それは理解するのが簡単すぎる
それは小さなリストでうまくいく
元のリストを保持するために必要なものを超える追加の一時的なストレージは必要ありません

画像参照：RMIT大学

選択ソート（Python）

選択ソートの仕組みを示すアニメーション

以下の例は、Pythonでの選択ソートを示しています

def sort_selection(my_list):

for pos_upper in xrange( len(my_list)-1, 0, -1):
    max_pos = 0
    for i in xrange(1, pos_upper + 1):
        if(my_list[i] > my_list[max_pos]):
            max_pos = i
            print "resetting max_pos = " + str(max_pos)

    my_list[pos_upper], my_list[max_pos] = my_list[max_pos], my_list[pos_upper]
    print "pos_upper: " + str(pos_upper) + " max_pos: " + str(max_pos) + " my_list: " + str(my_list)

return my_list


if __name__ == "__main__":

    my_list = [54,26,93,17,77,31,44,55,20]
    print "my_list: " + str(my_list)
    print sort_selection(my_list)

プログラムの出力：

my_list: [54, 26, 93, 17, 77, 31, 44, 55, 20]
resetting max_pos = 2
pos_upper: 8 max_pos: 2 my_list: [54, 26, 20, 17, 77, 31, 44, 55, 93]
resetting max_pos = 4
pos_upper: 7 max_pos: 4 my_list: [54, 26, 20, 17, 55, 31, 44, 77, 93]
resetting max_pos = 4
pos_upper: 6 max_pos: 4 my_list: [54, 26, 20, 17, 44, 31, 55, 77, 93]
pos_upper: 5 max_pos: 0 my_list: [31, 26, 20, 17, 44, 54, 55, 77, 93]
resetting max_pos = 4
pos_upper: 4 max_pos: 4 my_list: [31, 26, 20, 17, 44, 54, 55, 77, 93]
pos_upper: 3 max_pos: 0 my_list: [17, 26, 20, 31, 44, 54, 55, 77, 93]
resetting max_pos = 1
pos_upper: 2 max_pos: 1 my_list: [17, 20, 26, 31, 44, 54, 55, 77, 93]
resetting max_pos = 1
pos_upper: 1 max_pos: 1 my_list: [17, 20, 26, 31, 44, 54, 55, 77, 93]
[17, 20, 26, 31, 44, 54, 55, 77, 93]

画像参照：海賊学習者

選択ソート（Java）

選択ソートの仕組みを示すアニメーション

下の例は、選択の昇順でのソートを示しています。

public class MySelectionSort {
 
    public static int[] doSelectionSort(int[] arr){
         
        for (int i = 0; i < arr.length - 1; i++)
        {
            int index = i;
            for (int j = i + 1; j < arr.length; j++)
                if (arr[j] < arr[index]) 
                    index = j;
      
            int smallerNumber = arr[index];  
            arr[index] = arr[i];
            arr[i] = smallerNumber;
        }
        return arr;
    }

選択ソートの出力を表示するサンプルのmain()メソッドを書いた：

    public static void main(String a[]){
         
        int[] arr1 = {10,34,2,56,7,67,88,42};
        int[] arr2 = doSelectionSort(arr1);
        for(int i:arr2){
            System.out.print(i);
            System.out.print(", ");
        }
    }
}

プログラムの出力：

2, 7, 10, 34, 42, 56, 67, 88

下の例は、降順での選択ソートを示しています。

public static void doDescendingSelectionSort ( int [ ] num )
{
     int i, j, first, temp;  
     for ( i = num.length - 1; i > 0; i - - )  
     {
          first = 0;   //initialize to subscript of first element
          for(j = 1; j <= i; j ++)   //locate smallest element between positions 1 and i.
          {
               if( num[ j ] < num[ first ] )         
                 first = j;
          }
          temp = num[ first ];   //swap smallest found with element in position i.
          num[ first ] = num[ i ];
          num[ i ] = temp; 
      }           
}

画像参照：ウィキペディア

Modified text is an extract of the original Stack Overflow Documentation

ライセンスを受けた CC BY-SA 3.0

所属していない Stack Overflow

sorting
選択

サーチ…

備考

選択ソート（Python）

選択ソート（Java）