整列選択(Selection Sort)

5年前、私は大学生の時、資料の口述の授業を聞きながら、並べ替えの技術を勉強しました.当時勉強していた内容をこのブログに書き直したいと思います.
今日整理する内容はソートを選択することです.選択ソート(Selection Sort)は、基準要素を決定した後、要素全体の最小要素を検索することによって位置を交換する方法です.
次に、選択ソートを実行する手順を示します.
step 1.
最初の位置を基準位置に設定し、要素値全体から最小値を選択して、基準位置の要素と位置を置き換えます.
Step 1[基準(50),20,30,小元素(5),18,9,35,26]
ステップ1[標準(5),20,30,50,18,9,35,26]
step 2.
2番目の位置をデータム位置に設定し、残りの要素値から最小の要素値を選択して、データム位置の要素と位置を置き換えます.
ステップ2[5,基準(20),30,50,18,小元素(9),35,26]
ステップ2[5,規格(9),30,50,18,20,35,26]
step 3.
このようにして最後の要素(n−1)に進めばよい.
以下に、選択ソートを実現したコードを示します.

public void selectionSort(int[] list, int length) {

	int temp;
	int min;
	for (int i = 0; i < length; i++) {
		min = i;
		for (int j = i + 1; j < length; j++) {
			if (list[j] < list[min]) {
				min = j;
			}
		}
		temp = list[i];
        list[i] = list[min];
        list[min] = temp;
	}
}
    
public void print(int[] list) {

	for (int element : list) {
		System.out.printf("%d ", element);
	}
}


@Test
public void should_Calculation_When_Input() {

	int[] list = {50, 20, 30, 5, 18, 9, 35, 26};
	int length = list.length;
	selectionSort(list, length);
	print(list);

}

この方法を用いて、各ステップはiの第1の要素に基づいてn−1の要素を比較し、総比較回数は以下のように表すことができる.

時間複雑度:O(N^2)