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+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)
문제에서 주어진 배열의 길이 N이 10일 때
내부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)が受け入れられる
Reference
この問題について(21強選択ソート), 我々は、より多くの情報をここで見つけました https://velog.io/@jhjcoding/21강-선택-정렬テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol