정렬 알고리즘 : 선택정렬, 거품정렬, 삽입정렬

목적

• 선택정렬, 거품정렬, 삽입정렬이 무엇인지 이해한다.
• 각각의 정렬이 어떠한 차이를 지니는지 이해한다.
• 각각의 정렬의 시간복잡도를 이해한다.
• 각각의 정렬을 java에서 구현하는 방법을 살펴본다.

 

 

오늘의 준비물

• 정렬되지 않은 정수형 1차원 배열
• 배열을 오름차순으로 정렬하고야 말겠다는 뜨거운 마음

 

 

선택정렬(Selection Sort)

선택정렬은 정렬되지 않은 배열을 한번씩 돌면서 가장 작은값을 앞으로 쌓은 정렬 방법을 의미한다. 간단한 예시를 통해 알아보자.

 

 

메커니즘

정렬되지 않은 1차원 배열 [2, 3, 4, 1]이 있다. 

 

Step 1

1. 배열의 값을 하나하나 점검한다. (2 -> 4 -> 3 -> 1)
2. 가장 작은 값 1을 도출한다.
3. 가장 작은 값 1을 첫 번째 배열 자리로 옮기고, 첫 번째 배열 자리에 있던 숫자 2를 1번이 있던 자리로 옮긴다.

step 1 결과물 : [1, 3, 4, 2]

 

Step 2

1. 이미 정렬된 첫 번째 값을 제외한 나머지를 다시 점검한다. (4 -> 3 -> 2)
2. 가장 작은 값 2를 도출한다.
3. 가장 작은 값 2와 두 번째 배열 자리의 값을 교환한다.

step 2 결과물 : [1, 2, 4, 3]

 

 

Step 3

1. 이미 정렬된 첫 번째, 두 번째 값을 제외한 나머지를 다시 점검한다. (4 -> 3)
2. 가장 작은 값 3을 도출한다.
3. 가장 작은 값 3과 세 번째 배열 자리의 값을 교환한다.

step 3 결과물 : [1, 2, 3, 4]

 

 

 

아래의 영상들은 선택정렬이 무엇인지 보다 명확하게 보여준다.

 

https://www.youtube.com/watch?v=92BfuxHn2XE

 

https://www.youtube.com/watch?v=Ns4TPTC8whw 

 

 

 

시간복잡도

선택정렬은 최선의 경우, 최악의 경우, 평균의 경우 모두 n²의 시간복잡도를 지닌다. 간단하지만 그만큼 비효율적인 정렬방법으로 배열의 길이가 늘어나면 늘어날수록 정렬시간면에서 손해를 볼 수 있다!

 

 

 

Java를 통한 간단한 구현 예시

 

public class SelectionSort2 {
	
	//	호출의 편의를 위해 만든 메소드 (없어도 무방!)
	private static void selectionSort(int[] target) {
		selectionSort(target, 0);
	}
	
	// 재귀함수로 메소드가 호출될 때마다 start가 1씩 증가한다.
	private static void selectionSort(int[] target, int start) {
		
		// start가 배열의 마지막 인덱스보다 작은 경우에만 작동 (메소드의 start가 배열의 마지막 인덱스에 도달할 때 재귀는 끝이 나고 메소드는 종료된다.)
		if (start < target.length - 1) {
			
		 	int k = start;
		 	for (int i = start; i < target.length; i++) {
		 		if (target[i] < target[k]) k = i;
		 	}
		 	
		 	// target의 start 위치(정렬되지 않은 배열의 가장 앞쪽 위치)의 배열 값과 k 위치(가장 작은 값이 있는 위치)의 배열 값을 교환한다.
		 	swap(target, start, k);
		 	
		 	// start에 1을 더하여 다시 메소드를 호출한다.
		 	selectionSort(target, start + 1);
		}
	}
	
	// swap 메소드
	private static void swap(int[] arr, int index1, int index2) {
		int temp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = temp;
	}
	
	private static void printArray(int[] arr) {
		for (int data : arr) {
			System.out.print(data + ", ");
		}
		System.out.println();
	}
    }

 

 

 

거품정렬(Bubble Sort)

 

거품정렬은 배열의 인접한 두 수를 비교해서 더 큰 값을 뒤로 보내는 정렬 방법을 의미한다. 이 방법을 배열의 끝까지 진행하게 되면 배열에서 가장 큰 값이 배열의 마지막 공간에 위치하게 된다. 선택정렬과 마찬가지로 이러한 과정을 배열의 값이 1개가 될 때까지 반복한다.

 

 

메커니즘

정렬되지 않은 1차원 배열 [2, 3, 4, 1]이 있다.

 

 

step 1

1. 배열의 첫 번째 값과 두 번째 값을 비교한다. (2와 3을 비교)
2. 앞의 값 2가 뒤의 값 3보다 작기 때문에 넘어간다.
3. 배열의 두 번째 값과 세 번째 값을 비교한다. (3과 4를 비교)
4. 앞의 값이 뒤의 값보다 작기 때문에 넘어간다.
5. 배열의 세 번째 값과 네 번째 값을 비교한다. (4와 1을 비교)
6. 배열의 세 번째 값 4가 네 번째 값 1보다 크기 때문에 두 값의 위치를 바꾼다.

step1의 결과물 : [2, 3, 1, 4]

 

 

step 2

1. 다시 배열의 첫 번째 값과 두 번째 값을 비교한다. (2와 3)
2. 넘어간다.
3. 두 번째 값과 세 번째 값을 비교한다. (3과 1)
4. 두 번째 값이 세 번째 값보다 크기 때문에 서로의 위치를 바꾼다.

step2의 결과물 : [2, 1, 3, 4]

 

 

step 3

1. 다시 배열의 첫 번째 값과 두 번째 값을 비교한다. (2와 1)
2. 첫 번째 값이 두 번째 값과 크므로 두 값의 위치를 바꾼다.

step3의 결과물 : [1, 2, 3, 4]

 

 

보다 확실한 이해를 위해 아래의 영상을 살펴보자.

 

https://www.youtube.com/watch?v=Cq7SMsQBEUw 

 

https://www.youtube.com/watch?v=lyZQPjUT5B4 

 

 

시간복잡도

선택정렬과 마찬가지로 모든 배열의 값을 일일히 확인해야 하므로 최선의 경우, 최악의 경우, 평균의 경우 모두 n²의 시간복잡도를 지닌다. 

 

 

 

Java를 통한 간단한 구현 예시

 

public class BubbleSort {
	
	// 편의를 위한 메소드. 호출 시 end 값을 명시하지 않아도 되므로 편리하다.
	static void bubbleSort(int[] target) {
		bubbleSort(target, target.length);
	}
	
	// 1차원 배열과 정수 end를 인자로 받는 메소드. end는 메소드가 호출될 때마다 1씩 감소되며 end가 1이 되는 순간 종료되는 재귀함수다.
	static void bubbleSort(int[] target, int end) {
		
		if (end > 1) {
			
			// i를 0이 아닌 1에서 시작한 이유는 인접한 두 값을 비교해야 하기 때문이다. 아래 루프문이 시작될 경우 index 0과 1을 비교하는 것으로 시작해서 end-1과 end를 비교하는 것으로 끝나게 된다.
			for (int i = 1; i < end; i++) {
				
				// 왼쪽 값이 오른쪽 값보다 클 경우, 서로의 위치를 교환한다.
				if (target[i-1] > target[i]) swap(target, i-1, i);
			}
			
			bubbleSort(target, end - 1);
		}
	}
	
	// 배열의 값을 교환하는 메소드
	static void swap(int[] target, int index1, int index2) {
		int temp = target[index1];
		target[index1] = target[index2];
		target[index2] = temp;
	}
    }

 

 

 

삽입 정렬(Insertion Sort)

거품정렬과 비슷하게 인접한 배열의 값을 비교하지만 거품정렬과는 다르게 모든 배열 값을 확인하지 않아도 되는 정렬 방법이다. 손 안에 있는 카드를 정렬하는 것처럼 인접한 값을 비교하며 값이 위치해야 하는 자리를 찾아 삽입하는 방법이다.

 

 

메커니즘

정렬되지 않은 1차원 배열 [4, 2, 3, 1]이 있다.

 

step 1

1. 배열의 두 번째 값을 선택한다. (2)
2. 선택한 값을 배열의 첫 번째 값과 비교한다. (4와 2를 비교)
3. 선택한 값이 첫 번째 값보다 작다.
4. 배열의 첫 번째 값을 두 번째 배열의 위치로 옮긴다.
5. 선택한 값 2를 첫 번째 자리에 위치한다.

 

step1의 결과물 : [2, 4, 3, 1]

 

 

step 2

1. 배열의 세 번째 값을 선택한다. (3)
2. 선택한 값과 배열의 두 번째 값을 비교한다. (4와 3을 비교)
3. 선택한 값이 두 번째 값보다 작다.
4. 배열의 두 번째 값을 세 번째 배열의 위치로 옮긴다.
5. 선택한 값을 배열의 첫 번째 값과 비교한다. (2와 3을 비교)
6. 선택한 값이 첫 번째 값보다 크다.
7. 선택한 값을 배열의 두 번째 자리에 위치한다.

step2의 결과물 : [2, 3, 4, 1]

 

 

step 3

1. 배열의 네 번째 값을 선택한다. (1)
2. 선택한 값과 배열의 세 번째 값을 비교한다. (4와 1을 비교)
3. 선택한 값이 세 번째 값보다 작다.
4. 배열의 세 번째 값을 네 번째 배열의 위치로 옮긴다.
5. 선택한 값을 배열의 두 번째 값과 비교한다. (3과 1을 비교)
6. 선택한 값이 두 번째 값보다 작다.
7. 배열의 두 번째 값을 세 번째 배열의 위치로 옮긴다.
8. ...

step3의 결과물 : [1, 2, 3, 4]

 

 

 

마찬가지로 삽입정렬도 동영상으로 살펴보자.

 

https://www.youtube.com/watch?v=8oJS1BMKE64 

 

https://www.youtube.com/watch?v=ROalU379l3U 

 

 

시간복잡도

위의 예에서는 우연히 최악의 경우가 나오게 되었지만 거품정렬과 선택정렬과는 다르게 삽입정렬은 최선의 경우와 최악의 경우가 서로 다르다. 삽입정렬은 최악의 경우와 평균의 경우 n², 최선의 경우 n의 시간 복잡도를 갖는다.

 

 

 

Java를 통한 간단한 구현 예시

public class InsertionSort {
	
	// 편의를 위한 메소드
	static void insertionSort(int[] target) {
		insertionSort(target, 0);
	}
	
	// 배열 하나와 정수형 start를 인자로 받는 메소드. start가 배열의 끝에 도달할 때까지 반복되는 재귀함수다.
	static void insertionSort(int[] target, int start) {
		
		if (start < target.length - 1) {
			
			// targetNum과 이동위치를 기록할 k를 정의
			int targetNum = target[start + 1];
			int k = start;
			
			// k는 루프가 실행될 때마다 1씩 감소하게 되며 만약 k가 배열의 첫 번째 자리에 위치할 경우 루프가 종료된다.
			// targetNum과 k번째 배열의 값을 비교하게 됨.
			while (k >= 0 && targetNum < target[k]) {
				target[k + 1] = target[k];
				k--;
			}
			
			// 이 영역은 루프문을 돌고 난 이후 실행되는 영역이기 때문에 targetNum이 target[k]보다는 큰 값을, target[k + 2]보다는 작은 값을 가지고 있음을 확신할 수 있다.
			// 따라서 targetNum의 위치는 target[k + 1]이다.
			target[k + 1] = targetNum;
			
			// start 위치를 한 칸 오른쪽으로 이동한 후 메소드를 다시 실행시킨다.
			insertionSort(target, start + 1);
		}
	}
    }