내일은 알고리즘

순열은 어떤 집합의 원소들을 중복없이 뽑아 순서에 상관있게 나열하는것입니다.

n개의 원소를 가진 집합에서 r개를 뽑아 순열을 만든다고 하면 nPr 과 같이 나타냅니다.

원소를 넣을지 말지를 정했던 부분집합과 달리 순열은 이 위치에 이 원소를 넣을지 말지를 나누어서 진행됩니다.

{1,2,3,4}로 4개의 원소를 가진 집합에서 4개를 뽑아 만들 수 있는 순열을 모두 구한다고 해봅시다. = 4P4

우선 첫번째 위치에 1이 들어갑니다.

이 과정에서 우리는 1로 시작하는 모든 순열을 구하게 됩니다. (1로 만들수 있는 경우)

중복이 허용되지 않기 때문에 이미 사용된 1을 제외한 나머지 원소들 중에서 두번째 자리에 들어갈 것을 정해야합니다.

순서대로 2를 넣어줍니다. (1-2로 만들수 있는 경우)

같은 방식으로 중복이 되지 않게 다음 자리에 넣어질 수를 구해봅시다.

이때 재귀 호출된 함수는 이런 상태입니다. 

가장 위쪽에서부터 하나씩 숫자를 선택하며 4번째 같은 함수를 호출했습니다.

원했던 4개의 원소를 뽑았으므로 1-2-3-4 순열이 완성됩니다. (1-2-3 으로 만들수 있는 경우)

이제 4번째 함수는 종료되고 세번째 함수로 돌아갑니다. (1-2로 만들수 있는 경우)

세번째 자리에 3을 넣은 경우는 앞에서 시행했으므로 이번엔 4가 들어갑니다.

같은 방식으로 진행해서 이번엔 1-2-4-3 이라는 순열을 완성했습니다. (1-2-4 로 만들수 있는 경우)

순열은 구성한 원소가 같더라도 순서가 다르면 다른 것으로 보기때문에 1-2-3-4와 1-2-4-3은 다른 순열입니다.

첫 자리와 두번째 자리가 각각 1, 2인 경우는 모두 탐색되었습니다.

이제 두번째 자리가 달라지는 경우를 찾습니다.

두번째 자리에 3이 들어가는 경우가 시작됩니다.

위와 같은 방식으로 진행해서 1-3-2-4 순열을 얻었습니다.

같은 방식으로 진행하면 위와 같은 순서로 24개의 순열을 얻습니다.

처음 시작할때 원소들이 오름차순 정렬된 상태였으므로 결과들도 오름차순으로 정렬된 순서로 나옵니다.

아래는 위 아이디어를 구현한 Java와 Python코드입니다.

size 변수를 number배열의 원소 갯수보다 작게 조절하면 부분순열이 됩니다.

순열을 만드는 방법은 아래와 같이 재귀를 이용한 것과 반복문을 이용한 nextPermutation이란것이 있는데 후자는 다른 포스팅에서 얘기해보도록 하겠습니다.

public class algo_02_permutation {
	static int[] number = { 1, 2, 3, 4, 5, 6 };
	static int size = 6;

	public static void main(String[] args) {
		makePermutation(0, new int[size], new boolean[number.length]);
	}

	public static void makePermutation(int count, int[] picked, boolean[] used) {
		if (count == size) {
			printPermutation(picked);
			return;
		}
		
		for(int i = 0; i < number.length; i++) {
			if(!used[i]) {
				picked[count] = number[i];
				used[i] = true;
				makePermutation(count+1, picked, used);
				used[i] = false;
			}
		}
		
	}

	public static void printPermutation(int[] picked) {
		StringBuilder sb = new StringBuilder();
		sb.append("{ ");
		for (int i = 0; i < size; i++) {
			sb.append(picked[i]).append(" ");
			}
		sb.append("}");
		System.out.println(sb.toString());
	}
}

def makePermutation(count, picked, used):
    global size
    global number

    if(count == size):
        printPermutation(picked)
        return
    
    for i in range(0, len(number)):
        if(not used[i]):
            picked[count] = number[i]
            used[i] = True
            makePermutation(count+1, picked, used)
            used[i] = False
    

def printPermutation(picked):
    global size
    msg = "{ "
    for i in range(0,size):
            msg += str(picked[i])
            msg += " "
    msg += "}"
    print(msg)

number = [1,2,3,4,5,6]
size = 6

makePermutation(0, [0]*size, [False]*len(number))

오랜만에 다시 쓰는 알고리즘 글입니다.

오늘은 부분집합을 만드는 법에 대해 알아보겠습니다.

제가 수학 전공은 아니기 때문에 집합, 부분집합에 관한 기본적인 수학적 지식은 넘기고 설명을 하겠습니다.

부분집합은 어떤 집합에 속한 원소들로만 이루어진 집합입니다.

멱집합은 어떤 집합에서 만들 수 있는 모든 부분집합들을 모은 집합입니다.

보통 부분집합을 응용하는 PS는 이런 멱집합을 구하고 풀이하는 경우가 많습니다.

N개의 원소를 가진 집합의 부분집합의 개수는 2^N개입니다.

부분집합을 만들 때 집합의 어떤 원소를 넣던가 넣지 않던가 두 가지 선택이 가능하고 이런 원소가 N개 있으므로 2^N개의 부분집합이 생기는 것도 당연할 겁니다.

멱집합을 만드는 코드도 이 아이디어를 이용해서 진행합니다.

1~6까지의 숫자를 가진 집합이 있다고 생각해 봅시다.

이 집합의 부분집합으로 하나의 원소를 가진 부분집합 {1}, 여러 원소를 가진 부분집합 {1,2,3}, 공집합 { }, 집합 전체와 같은  {1,2,3,4,5,6}등 여러 종류가 있을 겁니다.

위에서 얻은 아이디어대로 하나의 원소를 넣고 빼는 두 가지 경우를 체크하며 부분집합을 만들어 봅시다.

6개의 원소가 있는 집합이지만 첫 번째 원소 1만 가졌다고 생각해 봅시다.

이 집합의 부분집합은 1이 들어있거나 안 들어있는 두 가지 경우로 나뉩니다.

이 두가지 경우에 대해 우리는 {1}과 { }라는 두 개의 부분집합을 만들 수 있습니다.

두 번째 원소 2를 더해 생각해볼까요?

1과 2 두 개의 원소를 가진 집합의 부분집합은 앞에서 구한 부분집합들에 2가 들어가거나 안 들어가는 두 가지 경우로 생각할 수 있습니다.

즉 우리는 {1,2} {1}, {2}, { }라는 4개의 부분집합을 얻을 수 있습니다.

집합의 원소가 늘어날 때마다 부분집합의 개수는 2배로 늘어나는 것이죠.

3을 포함시켜 {1,2,3}이라는 집합의 부분집합을 구해본다면 앞에서 구한 {1,2} {1}, {2}, { } 4개의 부분집합에 3이 들어가거나 안 들어가는 두 가지 경우로 {1,2,3} {1,3}, {2,3}, {3}, {1,2} {1}, {2}, { } 8개의 부분집합을 만들 수 있을 겁니다.

이렇게 구한 모든 부분집합의 집합을 멱집합이라고 부릅니다.

이 진행과정을 Java와 Python 두 개로 구현해 보았습니다.

부분집합, 조합, 순열 등의 개념을 응용하는 문제는 무척 많기 때문에 익숙해지시면 유용하게 쓰실 수 있습니다.

Java

public class algo_01_subset {
	static int[] number = {1,2,3,4,5,6};
	static int size = 6;
	public static void main(String[] args) {
		makeSubset(0, new boolean[size]);
	}
	
	public static void makeSubset(int idx, boolean[] used) {
		if(idx == size) {
			printSubset(used);
			return;
		}
		
		used[idx] = false;
		makeSubset(idx+1, used);
		used[idx] = true;
		makeSubset(idx+1, used);
	}
	
	public static void printSubset(boolean[] used) {
		StringBuilder sb = new StringBuilder();
		sb.append("{ ");
		for(int i = 0; i < size; i++) {
			if(used[i]) {
				sb.append(number[i]).append(" ");
			}
		}
		sb.append("}");
		
		System.out.println(sb.toString());
	}
}

Python

def makeSubset(idx, used):
    global size
    if(idx == size):
        printSubset(used)
        return
    
    used[idx] = False
    makeSubset(idx+1, used)
    used[idx] = True
    makeSubset(idx+1, used)

def printSubset(used):
    global size
    global number
    msg = "{ "
    for i in range(0,size):
        if(used[i]):
            msg += str(number[i])
            msg += " "
    msg += "}"
    print(msg)

number = [1,2,3,4,5,6]
size = 6

makeSubset(0, [False]*size)

카운팅 소~트 밤 하늘의 퍼얼~ 

오늘은 여섯 번째 정렬 알고리즘이자, 시간 복잡도가 O(N+K)인 특이한 정렬 알고리즘.
계수정렬(Counting sort)에 대해 알아보겠습니다.

1. 데이터의 범위를 전부 표현가능한 자료구조(배열,리스트 whatever)를 준비한다.
2. 데이터를 한 번 순회하면서 각 값의 갯수를 세어준다.
3. 알게 된 갯수만큼 데이터를 저장하거나 출력하면 정렬이 끝!

기존의 정렬들과는 달리 딱 한 번만 데이터를 순회하면 정렬이 완료됩니다.

그림과 함께 정렬의 순서를 확인 해보겠습니다.

1~5 범위의 데이터가 무작위로 준비되어 있습니다.

데이터를 전부 표현 가능한 5 사이즈의 배열을 준비했습니다.

정렬되지 않은 첫 데이터의 값은 3입니다.

값을 셀 배열에서 3의 값을 의미하는 위치의 값을 1 증가시킵니다.

두번째 데이터의 값은 2입니다.

마찬가지로 배열에서 2의 위치의 값을 1 증가시킵니다.

이런 방법으로 데이터를 한 번 순회하면...

위 처럼 정렬되지 않은 데이터가 몇개의 값으로 이루어진지 알 수 있습니다.

이제 값을 센 결과를 통해 정렬된 데이터를 만들어 봅시다.

1의 값을 가진 데이터가 2개이니 2개를 출력(혹은 정렬 후의 배열에 저장)

2의 값을 가진 데이터의 갯수도 2개이니 똑같이 출력

같은 작업을 끝까지 해주면 짠! 하고 정렬된 데이터를 얻게 됩니다.

이해하기도 쉽고 구현도 쉽고 시간복잡도까지 빠른 정렬 알고리즘입니다.

하지만 계수정렬은 특정 상황에서만 유용하게 쓰입니다.

시간복잡도 O(N+K)에서 알 수 있듯, K값인 데이터의 범위에 따라 그 효율성이 크게 달라지기 때문입니다.

예를 들어, 100명이 100점 만점의 시험을 본 점수결과 데이터를 정렬한다고 해봅시다.

K값은 100이고 이 데이터를 정렬하는데엔 대략 200번의 연산이면 충분할겁니다.

반면 100명의 연봉 데이터를 정렬한다고 해봅시다.

100명중에 능력있는 프로그래머가 한 명 있어서 최댓값이 1억이라고 생각해보면 K값은 1억이 되고 이 데이터를 정렬하는데엔 약 1억번의 연산이 필요합니다!

같은 100개의 데이터를 정렬하는데 효율성이 엄청나게 차이가 나죠.

따라서 계수정렬은 특정 상황에서만 유용하게 쓸 수 있는 정렬알고리즘입니다. 

아래는 간단하게 계수정렬을 구현한 JAVA코드 입니다.

디버깅 해보시며 정렬의 흐름을 따라해보시길 바랍니다.

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

public class sort_06_counting {
	static int size = 50;
	static int bound = 10;
	static int count = 0;
	// 데이터의 갯수와 범위 설정

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

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

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

		//////////////// 계수정렬 구현코드는 하단으로 /////////////////
		countingSort(data, bound);
		//////////////////////////////////////////////////////

		System.out.println(Arrays.toString(data));
		System.out.println("비교횟수 : " + count);
	}

	private static void countingSort(int[] data, int bound) {
		int[] countingsort = new int[bound + 1];
		int idx = 0;

		for (int i = 0; i < data.length; i++) {
			countingsort[data[i]]++;
			count++;
		}
		
		for (int i = 0; i < bound; i++) {
			count++;
			for(int j = 0; j < countingsort[i]; j++) {
				data[idx++] = i;
			}
		}

	}
}

오랜만에 다섯번째 정렬 알고리즘이자, 시간 복잡도가 O(NlogN)인 정렬 알고리즘.
퀵 정렬에 대해 알아보겠습니다.

1. 데이터 중에서 피봇(pivot)을 뽑습니다.
2. 피봇을 제외한 데이터들을 피봇보다 작은 데이터, 큰 데이터로 분류합니다.
3. 이렇게 두 그룹으로 나뉜 데이터에서 같은 동작을 반복하여 정렬 될 때까지 실행합니다.

퀵 정렬은 설명만 들으면 이해가 되지만 어떻게 이 정렬이 NlogN시간에 정렬이 되는지,

그리고 코드로는 어떻게 작성할지 생각이 막막한 정렬법입니다.

그림과 함께 천천히 알아보도록 하겠습니다.

퀵정렬을 위해 피봇을 정해야합니다.

이번엔 데이터의 정렬되지 않은 그룹의 가장 앞 수를 피봇으로 정해보도록 하겠습니다.

피봇을 정하고 데이터를 순회하면서 피봇보다 작은 수와 큰 수로 나누어줍니다.

계속해서 그룹을 배치해주면...

한 번의 순회가 끝나면, 피봇은 자신의 정렬된 위치에 자리하게 됩니다.

예시 데이터에서 다섯번째로 작은 5는 자신 앞에 위치하는 자기보다 작은 수가 4개임이 당연하므로 자연스럽게 다섯번째 위치에 자리잡게 됩니다.

다음은 피봇으로 나누어진 그룹의 한 쪽에서 다시 한 번 피봇을 정해줍니다.

처음에 약속한대로 가장 앞의 데이터 3을 피봇으로 정합니다.

피봇보다 작은지 큰지에 따라 재배치하면 이런 모양이 됩니다.

5의 경우처럼, 이 그룹에서 세번째에 위치해야하는 3은 자신의 정렬된 위치에 도달한 것을 알 수 있습니다.

5보다 큰 쪽의 그룹도 피봇을 정하고 똑같이 재배치합니다.

두번째 순회가 끝났습니다.

같은 방식으로 1을 피봇으로 잡으면 현 상태 그대로 머물게 되고, 이후 2,4,6,8 하나씩이 남게 된 그룹은 그대로 정렬된 상태가 됩니다.

보시다시피 피봇을 한 번 정할때마다 데이터가 두개로 나뉘고, 전체 데이터를 한 번 순회하면 2^N-1개의 데이터가 정렬되면서 logN번의 순회를 마치면 정렬이 완료되게 됩니다.

한 번 순회할때 데이터를 N개씩 비교하므로 시간복잡도는 NlogN이 됩니다.

(실제로는 매 순회마다 일부 데이터가 완벽히 정렬되므로 비교하는 데이터는 N개보다 적습니다.)

퀵정렬이라는 이름처럼 빠르게 정렬이 완료되는것이죠.

하지만 이런 퀵 정렬에도 예외적인 상황이 있습니다.

이렇게 역순으로 정렬된 데이터를 퀵정렬한다고 생각해 봅시다.

피봇을 가장 앞의 수로 정하고, 순회해서 작은 수의 그룹을 만들었더니... 

마치 버블정렬을 돌렸을 때처럼 피봇을 제외한 모든 수가 되었습니다!

같은 방식으로 피봇을 또 뽑게 되면 또다시 하나의 데이터만 정렬되게 되고, N-1번의 순회가 필요합니다.

그럼 피봇을 다른 방식으로 뽑는다면 어떨까요?

가장 앞의 수 대신 중앙의 수를 골라 피봇으로 선택했습니다.

비교 후엔 우리가 아까 테스트했던 퀵 정렬 처럼 두개의 그룹으로 나뉘며 정렬이 진행되는것을 볼 수 있습니다.

라이브러리에 구현되어 있는 퀵 소트는 이렇듯 피봇이 불리하게 뽑히는 것을 막기 위해 무작위 수로 피봇을 정하는 식으로 예외적인 상황을 회피한다고 합니다.

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

이건 이해를 돕기 위한 예시일 뿐 실제 코드와 프로그램에선 재귀적으로 파고들어 가며 정렬이 진행되기 때문에 동작 흐름은 다릅니다.

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

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

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

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

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

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

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

		//////////////// 퀵정렬 구현코드는 하단으로 /////////////////
		quickSort(data, 0, data.length - 1);
		//////////////////////////////////////////////////////

		System.out.println(Arrays.toString(data));
		System.out.println("비교횟수 : " + count);
	}

	private static void quickSort(int[] data, int left, int right) {

		if (left < right) {
			int i = left;
			int j = right;
			int pivot = data[(left + right) / 2];

			while (i < j) {
				while (j >= 0 && data[j] > pivot) {
					j--;
				}
				while (i < j && data[i] < pivot) {
					i++;
				}

				int tmp = data[i];
				data[i] = data[j];
				data[j] = tmp;
				count++;
			}
			// 정렬 과정
			quickSort(data, left, i - 1);
			quickSort(data, i + 1, right);
		}

	}
}

오늘은 네 번째 정렬 알고리즘이자, 시간 복잡도가 O(NlogN)인 첫 번째 정렬 알고리즘.

병합정렬에 대해 알아보겠습니다.

1. 데이터들이 한 개씩 쪼개어질 때까지 주어진 데이터를 두 개의 그룹으로 나누는 작업을 반복한다.

2. 하나씩 쪼개어진 데이터는 정렬된 상태가 된다.

3. 정렬된 데이터들을 쪼갠 역순으로 병합하면서 정렬하면 정렬된 상태의 전체 데이터를 구할 수 있다.

처음 병합정렬의 설명을 말로만 들으면 머릿속으로 정렬 과정을 그리기 쉽지 않을 텐데요.

그림을 통해 실제로 정렬이 이루어지는 과정을 보면서 설명하고 정리해드리도록 하겠습니다.

언제나처럼 정렬되지 않은 데이터가 있습니다.

3, 5, 7, 4, 2, 6, 8, 1의 여덟 데이터를 정렬해보도록 하겠습니다.

우선 데이터들을 두 개의 그룹으로 나누는 과정을 반복하여, 하나씩 쪼개어줍니다.

이번 예시의 경우엔 데이터의 개수가 2^3인 8개이므로 3번의 단계를 거쳐서 쪼개어집니다.

이렇게 최종적으로 쪼개어진 밑단의 데이터들은 자연스럽게 정렬된 상태가 됩니다!

(데이터가 하나이기 때문에 당연히 정렬된 상태입니다.)

이제 부분적으로 정렬된 데이터들을 병합하는 첫번째 단계가 시작됩니다.

각각 정렬된 상태인 3과 5를 비교하여 병합합니다.

(두 데이터 그룹이 부분적으로 정렬된 상태이기때문에 앞에서부터 읽어들이면 됩니다.)

같은 방법으로 7과 4를 병합합니다.

이렇게 첫번째 병합이 완료되었습니다.

두번째 단계부턴 두개의 그룹이 병합되는 과정을 설명해보겠습니다.

우리는 이미 부분적으로 정렬된 3,5 그리고 4,7의 그룹을 가지고 있습니다.

각 그룹이 이미 정렬된 상태기 때문에 전체를 탐색할 필요 없이 두 그룹의 가장 앞의 수를 보고 더 작은 수를 고르면 됩니다.

3과 4를 비교해 3을, 5와 4를 비교해 4를, 5와 7을 비교해 5, 마지막으로 남은 7을 골라줍니다.

자연스럽게 두개의 그룹이 정렬된 상태로 합쳐집니다.

그리고 두개의 그룹을 합칠 때 비교횟수는 전체 데이터의 갯수만큼이면 충분합니다!

(한 번의 비교에서 한개의 데이터가 골라집니다.)

같은 방법으로 나머지 그룹도 병합을 진행시켜줍니다.

이제 마지막, 세번째 병합을 똑같이 진행해줍니다.

두개의 그룹이 각각 부분적으로 정렬된 상태이기 때문에 앞에서부터 비교해가면서 합쳐주면 됩니다.

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

이건 이해를 돕기 위한 예시일 뿐 실제 코드와 프로그램에선 재귀적으로 파고들어 가며 정렬이 진행되기 때문에 동작 흐름은 다릅니다.

병합정렬의 시간 복잡도가 왜 NlogN인지 간단하게 설명해보겠습니다.

앞서 배운 정렬들에서 우리는 각 단계마다 비교를 N, N-1, N-2... 번씩 수행하였고 N^2번의 비교가 필요함을 알았습니다.

병합정렬의 경우에는 각 단계별로 N번의 비교가 이루어집니다. 

하지만 이 단계는 N번 반복되는 것이 아니라, N의 Log2값을 취한 만큼 이루어집니다.

데이터가 2^10개인 1024개라고 생각해봅시다.

처음 분할 단계에서 데이터는 2개의 그룹으로 나뉘는 일을 10번 반복하여 1개씩 1024개로 쪼개집니다.

그리고 이 데이터들은 10번의 단계를 거쳐 정렬된 1024개의 데이터가 됩니다.

10 * 1024 = 10,240번의 비교를 통해 정렬이 완료되는 겁니다.

버블정렬의 경우 같은 데이터에 대해 523,776번의 비교가 필요한 걸 생각하면, 또 데이터의 개수가 늘어날수록 이 차이가 더 커질 거란 걸 생각하면 NlogN정렬 알고리즘들이 더 효율적인걸 알 수 있습니다.

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

ArrayList 자료구조를 이용해 만들어봤는데요, 제가 적당히 작성한 코드라 실제 효율적인 부분에선 좋지 않을 것 같습니다!

병합정렬의 작동원리를 이해한다 정도로만 봐주시면 감사하겠습니다!

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

import java.util.ArrayList;
import java.util.Random;

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

	public static void main(String[] args) {
		ArrayList<Integer> data = new ArrayList<Integer>();
		Random random = new Random();

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

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

		//////////////// 병합정렬 구현코드는 하단으로 /////////////////
		data = mergeSort(data);
		//////////////////////////////////////////////////////

		System.out.println(data.toString());
		System.out.println("비교횟수 : " + count);
	}

	private static ArrayList<Integer> mergeSort(ArrayList<Integer> list) {
		int size = list.size();
		ArrayList<Integer> mergeList = new ArrayList<>();

		if (size <= 1) {
			return list;
		} else {
			ArrayList<Integer> left = new ArrayList<>();
			ArrayList<Integer> right = new ArrayList<>();

			for (int i = 0; i < (size / 2); i++) {
				left.add(list.get(i));
			}
			for (int i = (size / 2); i < size; i++) {
				right.add(list.get(i));
			}

			left = mergeSort(left);
			right = mergeSort(right);

			//System.out.println("left : " + left.toString());
			//System.out.println("right : " + right.toString());

			for (int i = 0, l = 0, r = 0; i < size; i++) {
				if (r == right.size() || (l != left.size() && left.get(l) <= right.get(r))) {
					mergeList.add(left.get(l));
					l++;
				} else {
					mergeList.add(right.get(r));
					r++;
				}
				count++;
			}
			//System.out.println("merge : " + mergeList.toString());
			return mergeList;
		}
	}
}

시간 복잡도가 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로 구현한 간단한 선택정렬 코드와 테스트입니다!

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

버블 정렬에 이어서 선택 정렬에 대해 알아보겠습니다.

선택 정렬의 아이디어도 간단합니다.

1. 첫 번째 데이터부터 탐색해 가장 작은 수를 찾아 첫 번째 위치로 옮긴다. (오름, 내림차순에 따라 다릅니다.)

2. 이제 첫 번째 위치는 정렬되었으니, 두 번째 데이터부터 탐색한다.

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

선택 정렬도 한 번 비교가 이루어질 때마다 데이터가 1개씩 정렬되므로 N-1, N-2, N-3 ... 2, 1 번 비교를 해야 합니다.

전체적인 비교의 횟수는 (N*(N-1))/2가 되고, 시간 복잡도는 O(N^2)와 같이 나타냅니다.

다만, 매 번 데이터의 교체가 필요한 버블정렬과 달리 선택 정렬은 위치를 찾은 뒤 마지막에 한 번만 교체하면 되니 버블 정렬보다는 빠르게 정렬이 이루어집니다.

대신 선택정렬의 경우는 stable하지 않은 불안정 정렬인데, 이 내용은 차후에 다루도록 하겠습니다.

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

그림에선 8칸의 배열에 각각 3,2,5,7,6,8,1,4의 값이 들어있습니다.

이제 이 배열을 선택 정렬을 통해 정렬해 보겠습니다.

우선 우리가 찾아야 할 데이터의 위치는 첫 번째, 즉 가장 작은 수를 찾아야 합니다.

반복 시행의 첫 시점에서 우리가 알고 있는 정보는 현 위치뿐이므로 가장 작은 수는 3이고 이 수의 위치는 0번 인덱스입니다.

다음 수로 진행하면서 전체를 탐색해 가장 작은 수를 찾아봅시다.

뒤의 수인 7,6,8도 2보다 크므로 계속 진행되다가 일곱번째 수인 1에서 최솟값이 갱신됩니다.

이제 첫번째 시행이 끝났습니다!

우리가 찾는 수는 첫 번째 위치에 올 수, 가장 작은 수이며 그 수의 위치는 6번째 인덱스입니다.

이제 0번과 6번 인덱스의 수를 바꿉니다.

첫 번째 수의 정렬이 완료되었습니다! 

이제 우리는 두 번째 자리에 위치할 수, 즉 일곱 개의 데이터 중에서 가장 작은 수를 찾으려 합니다.

시행을 마쳤습니다!

두 번째 위치, 인덱스 1에 들어있는 2가 현재 정렬되지 않은 가장 작은 수였습니다.

교환은 일어나지 않고, 우리는 두 개의 수를 정렬시켰습니다.

같은 방법으로 세 번째 시행도 진행시켜 봅시다.

이로서 우리는 1,2,3 세 개의 수를 정렬시켰습니다.

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

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

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

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

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

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

public class sort_02_selection {
	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 find = 0; find < size; find++) {
			int minIdx = find;
			for (int now = find; now < size; now++) {
				if(data[now] < data[minIdx]) {
					minIdx = now;
				}
				count++;
			}
			int save = data[find];
			data[find] = data[minIdx];
			data[minIdx] = save;
		}
		//////////////////////////////////////////////////////

		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 find = 0; find < 15; find++) {
			int minIdx = find;
			for (int now = find; now < 15; now++) {
				if(data2[now][0] < data2[minIdx][0]) {
					minIdx = now;
				}
				count++;
			}
			int[] save = data2[find].clone();
			data2[find] = data2[minIdx].clone();
			data2[minIdx] = save.clone();
		}

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

알고리즘 공부를 하며 배운 여러 자료구조, 알고리즘 등을 정리해보려고 합니다.

정렬 알고리즘들은 기본적인 알고리즘이자 정말 많이 활용되는 알고리즘입니다.

보통 언어의 기본 라이브러리 안에서 구현이 되어있어 호출로 간단히 사용할 수 있지만 직접 구현해야 하는 경우도 있고 무엇보다 어떤 식으로 돌아가는지를 알아야 다른 방법으로도 활용할 수 있습니다.

오늘은 정렬 중에서도 가장 쉽게 구현 가능한 버블정렬에 대해 알아보겠습니다.

버블정렬의 아이디어는 간단합니다. 

1. N개의 데이터가 있을 때, N-1번의 비교를 통해 가장 뒤에 (방향에 따라 달라집니다.) 위치할 데이터를 알아내자. 

2. 이제 하나의 데이터는 자기 자리에 있으니 나머지 N-1개의 데이터를 가지고 비교를 해보자.

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

그럼 한 번 비교가 이루어질때마다 1개씩 정렬되므로 N-1, N-2, N-3 ... 2,1 번 비교를 해야 합니다.

전체적인 비교의 횟수는 (N*(N-1))/2가 되는데, 시간 복잡도를 말할 때는 보통 작은 차수나 계수를 지우고 표현하기 때문에 O(N^2)와 같이 나타냅니다.

예를 들어 시간 복잡도가 2N인 프로그램과 3N인 프로그램, N^2번인 프로그램이 있다고 생각해봅시다.
데이터의 개수 N이 5개이고 하나를 처리할 때 1초가 걸린다고 가정하면 각각의 프로그램은 실행되는데 10초, 15초, 25초가 걸리게 됩니다. 이렇게 보면 계수의 차이가 유의미해 보이지만 보통 처리해야 할 데이터의 개수는 적게는 수백 개에서 수십억 개까지 늘어납니다.
1만 개의 데이터를 처리한다고 생각해봐도 첫 번째 프로그램은 2만 초로 실행에 대략 5시간이 걸리고 두 번째 프로그램은 3만 초, 약 8시간이 걸립니다.
하지만 세 번째 프로그램은 2만 7천 시간, 1157일이 필요합니다. 
자잘한 계수의 비교는 크게 의미가 없는 것이죠.

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

그림에선 8칸짜리 배열에 8,5,3,2,1,6,4,7의 값이 들어 있습니다.

버블정렬을 통해 이 배열의 데이터들을 오름차순으로 정렬해 보겠습니다.

8개의 데이터가 있으므로 첫 반복에서 우리는 N-1번, 즉 7번의 비교를 해야 합니다. 

지금 보고 있는 데이터와 다음 데이터를 비교해 더 크다면 위치를 바꿔줍니다.

첫 번째 데이터인 8이 두번째 데이터인 5보다 크기 때문에 8과 5의 위치를 바꿔줍시다.

이제 5와 8의 위치가 바뀌어 8이 두번째 데이터가 되었습니다.

두번째 데이터인 8과 다음 데이터 3을 비교해 더 크다면 둘의 위치를 바꿔줍시다.

같은 방식으로 계속 비교를 해주고 위치를 바꿔주었더니 8이 가장 뒤에 위치하게 되었습니다.

첫번째 시행에서 우리는 N번째로 큰 수를 찾아서 N번 위치에 놓았습니다.

이로서 하나의 데이터가 자기 위치를 찾아 정렬되었고, N-1개의 정렬할 데이터가 남았습니다.

8은 이미 정렬되었으므로 5,3,2,1,6,4,7의 7개 데이터를 정렬해봅시다.

방법은 위와 똑같이 지금 보고 있는 수가 다음 수보다 크다면 자리를 바꿔줍니다.

비교를 진행하다 보니, 뒤의 수가 더 큰 경우가 나왔습니다.

지금 보고 있는 수 5보다 다음 수 6이 크다면 둘의 위치를 바꿔주지 않습니다.

위치를 바꾸지 않는다면, 다음 비교에서 우리는 자연스럽게 5보다 더 큰 수인 6을 기준으로 비교를 하게 됩니다.

5를 대신해 6이 자기보다 큰 수가 나타날 때까지 계속해서 위치를 바꾸게 됩니다.

마지막 비교에서 6보다 7이 크므로 둘의 위치는 바뀌지 않습니다.

이로서 두 번째 시행의 시작인 5,3,2,1,6,4,7중 가장 큰 수인 7을 찾았고 자신의 위치인 7번 자리에 7이 위치하게 됩니다.

이제 두 개의 수가 정렬되었고 우리는 N-2개의 수를 대상으로 다시 비교를 시작합니다.

이다음 시행은 과정을 기록하지 않겠습니다.

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

네 번째 시행이 끝나고 나서 우리 눈으로 보기엔 정렬된 데이터가 완성되었습니다.

하지만 컴퓨터의 입장에선, 5 6 7 8 네 개의 데이터만 정렬되었다고 인식하므로 1,2,3,4에 대해서도 같은 시행을 반복하게 됩니다.

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

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

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

public class 01_sort_01_bubble {
	static int size = 100;
	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 find = size - 1; find >= 0; find--) {
			for (int now = 0; now < find; now++) {
				int next = now + 1;
				if (data[now] > data[next]) {
					int save = data[now];
					data[now] = data[next];
					data[next] = save;
				}
				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 find = 14; find >= 0; find--) {
			for (int now = 0; now < find; now++) {
				int next = now + 1;
				if (data2[now][0] > data2[next][0]) {
					int[] save = data2[now].clone();
					data2[now] = data2[next].clone();
					data2[next] = save.clone();
				}
			}
		}

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