정렬 알고리즘) 값 교환, 순차 정렬, 선택 정렬

안녕하세요, 코린이의 코딩 학습기 채니 입니다.

 

개인 포스팅용으로 내용에 오류 및 잘못된 정보가 있을 수 있습니다.

---

정렬 알고리즘 종류

- 순차정렬

- 선택정렬

- 버블정렬

- 삽입정렬

- 퀵정렬

- 합병정렬

...

 

그 중 순차 정렬과 선택 정렬에 대해서 알아보기 전에 값 교환의 원리부터 알아보겠습니다.

---

☞ 변수의 값 교환

public void test1() {
		int m = 10;
		int n = 20;
        
		System.out.println("m = " + m + ", n = " + n);
}

@콘솔출력값
m = 10, n = 20

m과 n을 각각 10, 20으로 값을 초기화 해주었습니다.

그 후 m과 n의 값을 서로 바꾸고 싶어졌는데요, 즉 m에는 n의 값인 20을, n에는 m의 값인 10을 서로의 값을 변경하고 싶었습니다.

 

정말 단순하게 생각하여 아래와 같은 코드를 짠다고 가정해보겠습니다.

public void test1() {
	int m = 10;
	int n = 20;
		
	m = n;
	n = m;
		
	System.out.println("m = " + m + ", n = " + n);
}

@콘솔출력값
m = 20, n = 20

하지만 결과는 20, 20으로 출력이 되었습니다.

그 이유는 변수에는 단 하나의 값만 입력할 수 있기 때문입니다.

m에 n의 값을 대입하니 기존의 값인 10은 지워버리고 20으로 덮어씌워졌고, 그 값을 다시 n에 대입하려니 덮어씌워진 20의 값을 가져온 것이죠.

 

그렇다면 원하는 대로 두 값을 서로 바꾸기 위해선 어떻게 해야할까요? 값을 저장할 공간을 만들고 복사해줍니다.

public void test1() {
	int m = 10;
	int n = 20;
		
	int temp = m;	//m의 값을 temp에 복사
	m = n;
	n = temp;
		
	System.out.println("m = " + m + ", n = " + n);
}

@콘솔출력값
m = 20, n = 10

이렇게 되면 temp에는 m의 값인 10이 복사가 된 상태이고, m에 n의 값 20을 대입

그 후 n에 복사해둔 m의 값을 가진 temp를 대입해주면 값 교환이 일어나게 되는 것입니다.

 

☞ 배열의 값 교환

int[] arr = {2, 1, 3};
		
int temp = arr[0];	//arr[0]의 값을 temp에 복사
arr[0] = arr[1];
arr[1] = temp;
		
System.out.println(Arrays.toString(arr));

@콘솔출력값
[1, 2, 3]

배열의 값 교환도 변수의 값 교환과 동일하게 진행합니다.

temp라는 변수(변수명은 마음대로)에 arr[0]의 값인 2를 복사해두고, arr[0]에는 arr[1]의 값인 1을 대입해줍니다.

(값은 1, 1, 3이 되겠죠)그 후 arr[1]에 arr[0]의 값을 가진 temp를 대입하면 원하는 대로 값 교환이 이루어지게 됩니다.

 

값 교환을 하는 코드를 메소드로 따로 만들어서 매개인자, 매개변수를 이용해 동일한 코드를 짜보았습니다.

public void test1() {
    int[] arr = {2, 1, 3};
	
//	int temp = arr[0];
//	arr[0] = arr[1];
//	arr[1] = temp;
		
	swap(arr, 0, 1);	//매개인자 전달
		
	System.out.println(Arrays.toString(arr));
}
	
public void swap(int[] arr, int i , int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

@콘솔출력값
[1, 2, 3]

arr의 0번지와 arr의 1번지의 값 교환이 필요하기 때문에 매개변수로 int i, int j 각각 0과 1을 받아 두 번지 사이의 값 교환이 이루어지게 만들었고, swap메소드가 끝난 후 호출부로 리턴하여 arr을 출력하게 됩니다.

역시 결과는 동일합니다.

 

test1에서 매개인자로 넘겨준 arr은 참조형이므로 주소값을 갖고 있습니다.

따라서 swap에서 매개변수 arr은 test1의 arr 주소값을 넘겨받은 것이죠.

 

그렇기 때문에 test1와 swap메소드에서 가리키는 int[] arr은 동일한 객체이므로 swap메소드에서 변경 후 test1에서는 변경된 값을 출력하게 되는 것입니다. (얕은 복사)

---

값 교환의 원리를 파악했다면, 순차 정렬에 대해 알아보겠습니다.

 

☞ 순차 정렬

- 0번지부터 해당 인덱스에 알맞은 수를 찾아 정렬

- 한 회차가 끝나면 해당 인덱스는 정렬이 끝나있다.

public void test2() {
	int[] arr = new int[] {5, 4, 1, 3, 2};
		
	for(int i = 0; i < arr.length-1; i++) {
		for(int j = i+1; j < arr.length; j++) {
			if(arr[i] > arr[j]) {
				swap(arr, i, j);
			}
		}
	}
	System.out.println(Arrays.toString(arr));
}
	
public void swap(int[] arr, int i , int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

@콘솔출력값
[1, 2, 3, 4, 5]

숫자들이 모두 오름차순으로 잘 정렬이 되는 것을 확인할 수 있습니다.

값 교환의 원리를 적용하여 만약 0번째에 있는 수가 1번째에 있는 수보다 크다면 두 수의 자리를 swap해줘야 합니다.

 

*외부 for문의 i는 0번부터 3번(길이-1)까지의 값을 비교하게 됩니다.

(길이-1의 이유는 0~3까지의 자리가 맞춰진다면 자연스럽게 마지막 자리는 올바른 수가 들어가기 때문!!)

* 내부 for문의 j는 1번(i+1)부터 4번까지의 값을 비교하게 됩니다.

(i+1의 이유는 i가 0이라면 j는 1이 되므로 앞/뒤 수를 비교하기 위해서!)

 

만약 arr[i]가 arr[j]보다 크다면 두 수는 앞/뒤 자리가 바뀌어야 합니다.

예를 들어 i가 0이라면, j는 1인 상태에서 for문이 돌 것입니다. 그렇다면 arr의 0번지와 arr의 1번지의 수를 비교하게 될 것입니다.

arr의 0번지의 수가 arr의 1번지의 수보다 크면 두 수는 교환 되어야 하므로 swap메소드가 실행 될 것이고, 

arr의 0번지의 수가 arr의 1번지의 수보다 작다면 if문은 실행 되지 않고 넘어갈 것입니다.

 

따라서

i가 0일 때는 j는 1 2 3 4 이므로 0번지와 1, 2, 3, 4번지를 비교

i가 1일 때는 j는 2 3 4 → 1번지와 2, 3, 4번지를 비교

i가 2일 때는 j는 3 4 → 2번지와 3, 4번지를 비교

i가 3일 때는 j는 4 → 3번지와 4번지를 비교

이렇게 for문이 돌아갈 것이며 그에 따라 swap이 일어나게 될 것입니다.

 

swap 과정 확인하기

public void test2() {
	int[] arr = new int[] {5, 4, 1, 3, 2};
	System.out.println(Arrays.toString(arr));
    
	for(int i = 0; i < arr.length-1; i++) {
		for(int j = i+1; j < arr.length; j++) {
			if(arr[i] > arr[j]) {
				swap(arr, i, j);
			}
			System.out.printf("i=%d j=%d : %s\n", i, j, Arrays.toString(arr));
		}
	}
	System.out.println(Arrays.toString(arr));
}
	
public void swap(int[] arr, int i , int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

@콘솔출력값
[5, 4, 1, 3, 2]
i=0 j=1 : [4, 5, 1, 3, 2]
i=0 j=2 : [1, 5, 4, 3, 2]
i=0 j=3 : [1, 5, 4, 3, 2]
i=0 j=4 : [1, 5, 4, 3, 2]
i=1 j=2 : [1, 4, 5, 3, 2]
i=1 j=3 : [1, 3, 5, 4, 2]
i=1 j=4 : [1, 2, 5, 4, 3]
i=2 j=3 : [1, 2, 4, 5, 3]
i=2 j=4 : [1, 2, 3, 5, 4]
i=3 j=4 : [1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

과정을 하나하나 살펴보면 이해가 쉽습니다.

 

첫번째 for문(외부 for문 기준)

0번째 인덱스와 1번째 인덱스의 값 비교 5 > 4 이므로 두 값 swap → [4, 5, 1, 3, 2] 출력

0번째 인덱스와 2번째 인덱스의 값 비교 4 > 1 이므로 두 값 swap → [1, 5, 4, 3, 2] 출력

0번째 인덱스와 3번째 인덱스의 값 비교 1 > 4 이므로 자리 유지 → [1, 5, 4, 3, 2] 출력

0번째 인덱스와 4번째 인덱스의 값 비교 1 > 2 이므로 자리 유지 → [1, 5, 4, 3, 2] 출력

 

두번째 for문

1번째 인덱스와 2번째 인덱스의 값 비교 5 > 4 이므로 두 값 swap → [1, 4, 5, 3, 2] 출력

1번째 인덱스와 3번째 인덱스의 값 비교 4 > 3 이므로 두 값 swap → [1, 3, 5, 4, 2] 출력

1번째 인덱스와 4번째 인덱스의 값 비교 3 > 2 이므로 두 값 swap → [1, 2, 4, 5, 3] 출력

 

세번째 for문

2번째 인덱스와 3번째 인덱스의 값 비교 4 > 5 이므로 자리 유지 → [1, 2, 4, 5, 3] 출력

2번째 인덱스와 4번째 인덱스의 값 비교 4 > 3 이므로 두 값 swap → [1, 2, 3, 5, 4] 출력

 

네번째 for문 

3번째 인덱스와 4번째 인덱스의 값 비교 5 > 4 이므로 두 값 swap → [1, 2, 3, 4, 5] 출력

 

 

☞ 선택 정렬

- 한 회차에 최소값을 찾고, 마지막에 한 번만 자리 교환

public void test3() {
	int[] arr = new int[] {5, 4, 1, 3, 2};
		
	for(int i = 0; i < arr.length-1; i++) {
		int min = i;
		for(int j = i+1; j < arr.length; j++) {
			if(arr[min] > arr[j]) 
				min = j;
		}
		swap(arr, min, i);
	}
	System.out.println(Arrays.toString(arr));
}
	
public void swap(int[] arr, int i , int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

@콘솔출력값
[1, 2, 3, 4, 5]

min이라는 최소값을 가리키는 변수를 선언을 하였습니다.

min = i 이므로, 외부 for문이 돌 때마다 min의 값은 변경이 될 것입니다.

 

i = 0일 때 m = 0일 것이며, 내부 for문이 돌고 j = 1입니다.

만약 arr[0] > arr[1] 이다면 min에는 j의 인덱스 번호를 대입하게 됩니다.

(min의 인덱스 번호에 있는 숫자보다 j의 인덱스 번호에 있는 숫자가 작다면 그것은 최소값이기 때문이죠.)

이 과정을 arr.length만큼 반복하게 되고 내부 for문이 다 돌게 되면 min에는 최소값이 담기게 됩니다.

 

그 때 swap을 통해 i = 0 즉 첫번째 자리에 최소값이 들어가게 되는 것입니다. (i가 0인 경우)

따라서 각각 최소값이 0, 1, 2, 3 인덱스 번호에 차례대로 오름차순 정렬이 되는 것이죠.

 

swap 과정 확인하기

public void test3() {
	int[] arr = new int[] {5, 4, 1, 3, 2};
	System.out.println(Arrays.toString(arr));
		
	for(int i = 0; i < arr.length-1; i++) {
		int min = i;
		for(int j = i+1; j < arr.length; j++) {
			if(arr[min] > arr[j]) 
				min = j;
			System.out.printf("i=%d j=%d : %s\n", i, j, Arrays.toString(arr));
		}
		swap(arr, min, i);
	}
	System.out.println(Arrays.toString(arr));
}
	
public void swap(int[] arr, int i , int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

@콘솔출력값
[5, 4, 1, 3, 2]
i=0 j=1 : [5, 4, 1, 3, 2]
i=0 j=2 : [5, 4, 1, 3, 2]
i=0 j=3 : [5, 4, 1, 3, 2]
i=0 j=4 : [5, 4, 1, 3, 2]
i=1 j=2 : [1, 4, 5, 3, 2]
i=1 j=3 : [1, 4, 5, 3, 2]
i=1 j=4 : [1, 4, 5, 3, 2]
i=2 j=3 : [1, 2, 5, 3, 4]
i=2 j=4 : [1, 2, 5, 3, 4]
i=3 j=4 : [1, 2, 3, 5, 4]
[1, 2, 3, 4, 5]

마찬가지로 과정을 하나하나 살펴보겠습니다. (순차정렬과 다르게 마지막 한 번만 값 변경이 일어납니다.)

 

첫번째 for문(외부 for문 기준) i = 0 / min = 0

0번째 인덱스(min = 0)와 1번째 인덱스(j = 1) 값 비교 5 > 4 이므로 min = 1 변경

1번째 인덱스(min = 1)와 2번째 인덱스(j = 2) 값 비교 4 > 1 이므로 min = 2 변경

2번째 인덱스(min = 2)와 3번째 인덱스(j = 3) 값 비교 1 > 3 이므로 min = 2 유지

2번째 인덱스(min = 2)와 4번째 인덱스(j = 4) 값 비교 1 > 2 이므로 min = 2 유지

2번째 인덱스(min = 2)와 0번째 인덱스(i = 0) swap → [1, 4, 5, 3, 2] 출력

 

두번째 for문 i  = 1 / min = 1

1번째 인덱스(min = 1)와 2번째 인덱스(j = 2) 값 비교 4 > 5 이므로 min = 1 유지

1번째 인덱스(min = 1)와 3번째 인덱스(j = 3) 값 비교 4 > 3 이므로 min = 3 변경

3번째 인덱스(min = 3)와 4번째 인덱스(j = 4) 값 비교 4 > 2 이므로 min = 4 변경

4번째 인덱스(min = 4)와 1번째 인덱스(i = 1) swap → [1, 2, 5, 3, 4] 출력

 

세번째 for문 i = 2 / min = 2

2번째 인덱스(min = 2)와 3번째 인덱스(j = 3) 값 비교 5 > 3 이므로 min = 3 변경

3번째 인덱스(min = 3)와 4번째 인덱스(j = 4) 값 비교 3 > 4 이므로 min = 3 유지

3번째 인덱스(min = 3)와 2번째 인덱스(i = 2) swap → [1, 2, 3, 5, 4] 출력

 

네번째 for문 i = 3 / min = 3

3번째 인덱스(min = 3)와 4번째 인덱스(j = 4) 값 비교 5 > 4 이므로 min = 4 변경

4번째 인덱스(min = 4)와 3번째 인덱스(i = 3) swap → [1, 2, 3, 4, 5] 출력

 

 

만일 내림차순으로 정렬하고 싶다면 if문의 부등호를 변경하면 되겠죠?