선택 정렬

문제 . N개 숫자가 입력되면 오름차순으로 선택정렬하시오.

 

입력 예시

6
13 5 11 7 23 15

 

답 : 

5 7 11 13 15 23

 

 

나의 답변

import java.util.Scanner;

public class Main {	
	
	public int[] solution(int n, int[] arr) {
		for( int i=0; i<n-1; i++) {
			int idx = i; 
			for( int j=i+1; j<n; j++) {
				if(arr[j]<arr[idx]){
					idx=j; 
				}
			}
			int temp = arr[i];
			arr[i] = arr[idx];
			arr[idx] = temp;
		}
		return arr;
	}
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n]; 
		for( int i=0; i<n; i++ ) {
			arr[i] = sc.nextInt();
		}
		for( int x : T.solution(n, arr)) {
			System.out.print(x + " ");
		}
	}
}

 

 

---

 

선택정렬

 

배열의 왼쪽부터 오른쪽으로 가면서 확인해가며 어떤 값이 최소값인지 그 값의 인덱스를 변수에 저장한다.

패스스루를 돌때마다 그 회차의 최소값으로 차례대로 배열된다.

 

원소 N개가 있을 때

비교횟수는 (N - 1) + (N - 2) + (N - 3) + ... + 1번의 비교이다. 

교환횟수는 한 패스스루 당 1번이다. 

최대횟수는 배열이 역순으로 이뤄졌을 때 일어난다.

ex )  원소가 54개 있을 때 45번의 비교 + 9번의 교환이 일어난다. 

선택정렬은 n^2 /2 단계이며 시간 복잡도가 O(n^2)이다.