선택 정렬 - 자바[JAVA]

[유튜브 동빈나님 알고리즘 강의를 듣고 정리하는 글]

선택 정렬은 숫자중에 가장 작은 값을 찾고 위치를 바꾸고, 그 다음으로 가장 작은 값을 찾고 위치를 바꾸는 걸 반복한다.

선택 정렬 예시

이를 코드로 표현하면 다음과 같다.

	public static void main(String[] args) throws IOException {
		
		// 가장 작은 숫자를 선택해서 앞으로 보낸다. > min이 필요
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int numbers[] = new int[n];
		
		int min, tmp;
		
		// 수 입력받기
		for(int i=0; i<n; i++) {
			numbers[i] = Integer.parseInt(br.readLine());
		}
		
		for(int i=0; i<n; i++) {
			min = i;
			
			for(int j=(i+1); j<n; j++)
				if(numbers[min] > numbers[j])
					min = j;
			
			tmp = numbers[i];
			numbers[i] = numbers[min];
			numbers[min] = tmp; //여기에 tmp말고 number[i]넣어놓고 30분동안 헤맸다..ㅎ
		}
		
		for(int item : numbers) {
			System.out.println(item);
		}
	}

선택 정렬은 입력 받은 숫자의 개수가 10개일 때 처음부터 끝까지 반복문을 돌아서 min 값을 찾는다.

다음으로는 9번 다음은 8번 이렇게 10 + 9 + 8 + 7 + ... + 1 = 55로 총 55번 반복한다.

이를 수식으로 나타내면 (10 + 1) * 10 / 2 이며 10을 n으로 하면 (n + 1) * n / 2이다.

여기서 더하기와 / 2를 무시하면 n * n이 되며 시간 복잡도는 O(n^2)가 된다.