[내가 몰라서 정리하는 알고리즘] 1. 선택정렬

선택정렬

---

(본 공부는 전부 자바를 기반으로 합니다.)

 

입력된 값 중에서 가장 작은 값을 선택해서 계속해서 앞으로 보내는 방식으로 정렬된다.

0부터 시작하여 끝까지 돌아보면서 제일 작은 값을 선택한 후, 그것을 [0] 값에 넣는다.

그 다음 [0] 값을 제외하고 [1]부터 시작하여 끝까지 돌아보면서 제일 작은 값을 선택한 후 , 그것을 [1] 값에 넣는다.

[2]부터 시작하여 끝까지 돌아보면서 제일 작은 값을 선택한 후, 그것을 [2] 값에 넣는다.

그리고 이것을 입력된 값이 끝날때까지 반복하는 형태로 정렬하는 방법이다!

 

Q) 1 10 5 8 7 6 4 3 2 9

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

1   10  5  8   7   6   4   3  2   9

A)

1턴 : [0]부터 [9]까지 돌아보면서 가장 작은 값을 선택하고(MIN = [0] = 1) 그 값을 [0] 자리에 삽입한다.

결과 : 1 10 5 8 7 6 4 3 2 9

 

2턴 : [1]부터 [9]까지 돌아보면서 가장 작은 값을 선택하고(MIN = [8] = 2) 그 값을 [1] 자리에 삽입한다.

결과 : 1 2 5 8 7 6 4 3 10 9

 

3턴 : [2]부터 [9]까지 돌아보면서 가장 작은 값을 선택하고(MIN = [7] = 3) 그 값을 [2] 자리에 삽입한다.

결과 : 1 2 3 8 7 6 4 5 10 9

 

.

.

.

 

위와 같은 방법으로 10턴까지 반복하면 총 정렬의 결과는 1 2 3 4 5 6 7 8 9 10 이 된다.

 

 

1턴에서 [0]부터 [9]까지 작은 값을 찾기 위해 10번을 확인해 나간다.

2턴에서 [1]부터 [9]까지 작은 값을 찾기 위해 9번을 확인해 나간다.

3턴에서 [2]부터 [9]까지 작은 값을 찾기 위해 8번을 확인해 나간다.

이렇게 반복해 나가다 보면 10번, 9번, 8번, 7번, 6번, 5번, 4번, 3번, 2번, 1번의 확인을 한다는 것을 알 수 있다.

 

 

따라서 총 확인한 횟수를 전부 더한다면 10 + 9 + 8 + … + 1 이 되고,

이 것은 수학시간에 배웠었던 그.. (..) 아무튼

 

N * (N+1) / 2

 

저 덧셈을 공식으로 하면 10 * (10 + 1) / 2 로 55번이 된다.

 

즉 선택정렬로 정렬을 수행하게 되면 데이터의 개수가 10개라면 최소 55번의 비교연산을 한다는 소리!

 

 

예시는 10개의 숫자를 정렬하는 것이었지만 실제로 정말 많은 데이터를 정렬해야 한다면 ..

N의 크기가 정말 커진다면 '더하기 1'이나 '나누기 2'와 같은 연산은 무시가 될 것이다.

그래서 N의 크기가 커진다면 총 횟수는

 

N * N

 

이 될 것이고, 이것을 빅오(O) 표기법으로 표현한다면

(빅오에 대해서는 자세히 묻지 마세요 아는데 대답을 못하는겁니다

(사실 대답 못하는 거면 모르는거라고 말한다면 할말 X) )

 

O(N*N) = O(N^2)

 

즉 선택정렬은 N의 크기가 커진다면 N*N의 수행횟수를 필요로 한다.

이거는 데이터의 개수가 만개라면 대략 1억번 정도 비교를 하는 것이라고 .. (...)

생각만 해도 굉장히 비효율적인 알고리즘이다 !

하지만 구현하기는 생각보다 쉽다 이해만 한다면 괜찮다 ^^ !

 

 

근데 나는 역시나 이론만 보고는 이해 불가였으므로 직접 코드를 짜보고 코드를 한 줄 씩 뜯어 보았다.

 

 

다들 쉽다고 하는데 나만 이해 못해서 당황하고 내가 똥멍청이인가 생각하는 사람들에게

내가 뜯어 분석한 코드를.. 바칩니다..

모두들 자신감을 가지세요

 

 

import java.io.*;

public class SelectionSort {
	public static void main(String args[]) {
		int i, j;
		int min; //최소값을 반복적으로 넣어주기 위한 변수
		int index = 0; //최소값의 인덱스를 저장하기 위한 변수
		int temp; //최소값과 배열의 값을 바꿔줄때 임시로 사용하는 변수
		int array[] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
		for(i=0;i<10;i++) { //반복해서 탐색
			min = 9999;
			//모든 원소의 값보다 큰 숫자를 넣어준다. 항상 최소값을 넣어줘야 하기 때문에 처음에는 큰 값을 넣어준다.
			for(j=i;j<10;j++) {
				if(min > array[j]) { //만약 배열의 값이 min보다 작으면
					min = array[j]; //최소값인 배열의 값을 min에 넣어준다.
					index = j; //최소값의 인덱스 값인 j를 저장한다.
				}
			} //-> for문이 끝날때마다 가장 작은 값이 선택된다. 그리고 그 가장 작은 값을 맨 앞으로 보내줘야 한다.
		temp = array[i]; //temp에 배열의 가장 맨 앞에 있던 값을 넣어준다.
		array[i] = array[index]; //배열의 가장 맨 앞에 for문에서 찾은 최소값을 넣어준다
		array[index] = temp; //최소값이 있었던 원래 자리에는 맨 앞에 있던 값을 넣어준다.
		}
		
		for(i=0;i<10;i++) {
			System.out.print(array[i]+" ");
		}
	}
}

 

---

 

이렇게 공부한 선택정렬을 쉬운 문제에 적용해보았다.

문제 출처 : JUNGOL (정보 올림피아드 & 알고리즘) http://www.jungol.co.kr/ 1146 : 선택정렬 문제

JUNGOL

 

import java.io.*;
import java.util.Scanner;

public class prac_1146 {
	public static void main(String args[]) throws IOException {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		int array[] = new int[n];
		int i, j, min, index = 0, temp;
		boolean change = false;
		for(i=0;i<n;i++) {
			array[i] = s.nextInt();
		} //input
		
		//Selection Sort
		for(i=0;i<n;i++) {
			min = 101;
			for(j=i;j<n;j++) {
				if(min > array[j]) {
					min = array[j];
					index = j;
				}
			}
			temp = array[i];
			array[i] = array[index];
			array[index] = temp;
			for(int x=0;x<n;x++) {
				if(i != n-1)
					System.out.print(array[x]+" ");
			}
			System.out.println();
		}
	}
}

 

더 자세한 코드는 https://github.com/suhyeong (Simple Mars) 을 참고하세요.