알고리즘

Merge Sort 번역하기에 따라 병합 정렬 혹은 합병 정렬이라고 불린다. 분할 정복 알고리즘의 하나로 배열을 잘게 쪼개서 정렬을 하고 이를 합치는 방식이다. 말로 설명하기보다 그림으로 이해하는 것이 더 편하다. 아래와 같은 7size의 배열이 있다고 가정하자. 이를 4size의 배열과 3size의 배열로 나눈다. 다시 4size배열을 2size의 배열 두개로 나누고,... size가 하나가 될때까지 반복한다. 이후 각각을 비교해서 합치면서 정렬된 7size의 배열로 만들어준다. Merge Sort의 시간 복잡도는 O(nlogn)가 된다. public class merge { public static void mergeSort(int[] a,int p,int r) { int q = (int)Math.f..

삽입 정렬을 설명할때 보통 카드 게임에서 카드를 정렬하는 방식과 같다고 말한다. 0번 인덱스와 1번 인덱스를 비교하여 정렬한다. 이후 0,1,2를 비교해서 자리를 찾는다. 그 다음은 3번 인덱스가 들어갈 자리를 찾고 이런 식으로 끝까지 비교한다. 정렬된 배열에서 지정한 자리에 자료를 삽입하여 정렬하므로 삽입 정렬이라고 부른다. 단 초기 Key값을 0번 인덱스의 값이 아닌 1번 인덱스의 값으로 지정한다. 삽입 정렬의 시간 복잡도 또한 O(n2)로 버블,선택 정렬과 동일하다. 이 과정을 자바 코드로 표현하면 아래와 같다. public class insert { public static void insertSort(int[] a){ int N = a.length; int key; int i,j; for (i ..

선택 정렬은 0번 인덱스를 마지막번 인덱스까지 차례대로 비교해 가장 작은 값을 찾아 0번에 놓고, 1번 인덱스를 차례대로 비교해 그 중 가장 작은 값을 찾아 1번에 놓는 과정을 반복하며 정렬을 수행한다. 1회전을 수행하고 나면 최소값이 맨 앞에 오게 되므로 2회전에서는 맨 앞인 0번 인덱스를 빼고 정렬을 진행하면 된다. 선택 정렬의 성능 분석 공식은 T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)로 버블정렬과 동일하다. 5 3 1 4 2를 가지고 선택 정렬을 수행하는 과정은 위의 이미지와 같다. 최소값을 담아둘 임의의 변수 min값이 필요함을 알 수 있다. 자바로 작성하면 다음과 같다. public class Selection { public static v..

버블 정렬은 배열의 0번 인덱스와 1번 인덱스를 비교하고 1번 인덱스와 2번 인덱스를 비교하는 과정을 처음부터 마지막 인덱스까지 반복하여 진행한다. 즉 인접 인덱스를 비교하면서 정렬하는 방식이다. 1회전을 수행하고 나면 제일 큰 숫자가 맨 뒤에 위치하게 된다. 따라서 다음 회전에서는 마지막 인덱스-1까지만 고려한다. 버블 정렬의 성능 분석 공식은 S(n) + S(n-1) + … + S(2) = (n-1) + (n-2) + (n-3) + … + 3 + 2 + 1 가 된다. 여기서의 S(n)은 인덱스 비교하는 시간 = 교환하는 시간이라고 한다. 식을 정리하면 O(n^2) 임을 알 수 있다. 위의 이미지에서는 5 3 1 4 2 의 자료를 정렬하는 과정을 보여주고 있다. 이를 자바 소스 코드로 작성하면 다음과 ..