내일은 알고리즘

시간 복잡도가 N^2인 세 번째 정렬방법, 삽입정렬에 대해 알아보겠습니다.

삽입정렬은 간단히 말해서 우리가 실생활에서 쓰는 정렬법입니다.

도둑잡기나 원카드 같은 카드게임을 할 때, 카드를 뽑아서 자기 자리에 끼우면서 정렬하는 그 방식을 생각하시면 됩니다.

1. 정렬되지 않은 데이터 중에 하나를 고른다.

2. 선택한 데이터를 정렬된 데이터와 비교해서 들어갈 위치를 찾는다. 

3. 정렬이 완료될 때까지 계속 반복한다!

삽입정렬은 앞서 배웠던 버블정렬, 선택정렬보다 조금 속도가 빠르다고 합니다.

버블정렬, 선택정렬은 정렬되지 않은 모든 데이터와 비교를 해서 정렬 횟수가 고정되어있는 반면, 삽입 정렬은 정렬된 데이터와 비교를 하기 때문에 자신의 위치를 찾을 때까지만 비교합니다.

물론 최악의 경우(역순으로 정렬된 상태)에는 버블, 선택정렬과 똑같은 수를 비교합니다.

또한 데이터가 들어갈 위치를 찾는 방법, 데이터들을 shift 하는 방법에 따라 효율이 조금씩 달라진다고 합니다.

그럼 그림을 통해 삽입정렬의 진행을 알아보도록 하겠습니다.

그림에선 초기에 5,7,3,6,8,4,2,1 8개의 데이터가 정렬되지 않은 상태로 있습니다.

우선 정렬되지 않은 수 중에서 하나를 고릅니다.

그리고 정렬된 수들에서 5가 위치할 곳을 찾습니다.

지금은 정렬된 수가 없으므로 5는 그대로 위치하게 되고 정렬된 상태가 됩니다. 

다음으로 정렬할 수를 고릅니다. 

정렬된 수 사이에 들어갈 7의 위치를 찾는데 7이 5보다 크므로 그대로 유지됩니다.

이제 5와 7 두 개의 숫자가 정렬되었습니다.

다음으로 정렬할 수를 고릅니다.

정렬된 수 사이 3이 위치할 곳을 찾습니다. 

3이 7보다 작으므로 교체가 일어나고,

5와의 비교에서도 교체가 일어납니다.

3이 자신의 정렬된 위치를 찾아 이동했고, 이제 3,5,7 세 개의 수가 정렬된 상태가 되었습니다.

한 번만 더 시행을 반복해 보도록 하겠습니다.

네 번째 시행에서 6을 정렬합니다.

6이 7보다 작으므로 교체가 일어나고 5보단 크므로 그곳이 6이 위치할 자리입니다.

이렇게 4개의 수가 정렬되었습니다.

남은 4번의 시행도 같은 방식으로 진행하면 되지만 과정을 기록하지 않겠습니다.

머릿속으로 테스트를 해보시고 정렬 후의 모습과 비교해보시기 바랍니다.

이렇게 삽입정렬을 통한 정렬이 완료되었습니다!

아래는 JAVA로 구현한 간단한 삽입정렬 코드와 테스트입니다!

이것저것 바꿔보고 디버깅하면서 흐름이 이해되시길 바랍니다.

import java.util.Arrays;
import java.util.Random;

public class sort_03_insertion {
	static int size = 10;
	static int bound = 1000;
	// 데이터의 갯수와 범위 설정

	public static void main(String[] args) {
		int[] data = new int[size];
		Random random = new Random();
		int count = 0;

		for (int i = 0; i < size; i++) {
			data[i] = random.nextInt(bound);
		}
		// 랜덤 값 넣어주기

		System.out.println(Arrays.toString(data));
		// 랜덤하게 들어간 데이터 확인

		/////////////////////// 삽입정렬 구현////////////////////////////
		for (int s = 0; s < size; s++) {
			int now = s;
			while (now > 0) {
				if(data[now] < data[now-1]) {
					int save = data[now];
					data[now] = data[now-1];
					data[now-1] = save;
				}else {
					break;
				}
				now--;
				count++;
			}
		}
		//////////////////////////////////////////////////////

		System.out.println(Arrays.toString(data));
		System.out.println("비교횟수 : " + count);
		// 정렬 후 데이터와 비교횟수 확인

		int[][] data2 = { { 1, 1 }, { 3, 1 }, { 5, 1 }, { 7, 1 }, { 9, 1 }, { 1, 2 }, { 2, 2 }, { 4, 2 }, { 1, 3 },
				{ 7, 2 }, { 9, 3 }, { 3, 3 }, { 4, 3 }, { 8, 3 }, { 6, 3 } };
		
		for (int s = 0; s < 15; s++) {
			int now = s;
			while (now > 0) {
				if(data2[now][0] < data2[now-1][0]) {
					int[] save = data2[now].clone();
					data2[now] = data2[now-1].clone();;
					data2[now-1] = save;
				}else {
					break;
				}
				now--;
				count++;
			}
		}

		for (int i = 0; i < 15; i++) {
			System.out.printf("정렬된 수 : %d, stable: %d\n", data2[i][0], data2[i][1]);
		}
		// stable 정렬이 아님!
	}
}

아래는 JAVA로 구현한 간단한 선택정렬 코드와 테스트입니다!

이것저것 바꿔보고 디버깅하면서 흐름이 이해되시길 바랍니다.