합병 정렬 (Merge sort)이란? 분할정복알고리즘 중 하나입니다. 일단 분할정복법이 뭔지 먼저 설명하는 게 좋을 듯합니다. 분할정복 (Divide and Conquer) 분할정복은 다음의 3단계로 이루어집니다. 1. Divide --- 문제를 subproblem으로 나눕니다. 2. Conquer --- 그 subproblem을 재귀적으로 주루룩 정복합니다. 이때 Base case까지 다다르게 됩니다. Base case란, subproblem이 충분히 작으면 그냥 아주 쉽게, 거의 그 자체 풀리는 수준의 케이스입니다. 3. Combine --- 2단계에서 subproblem들을 정복해 해답을 얻었습니다. 이 답들을 Combine해서 맨 처음의 original problem의 해답으로 얻어냅니다. 이것..

삽입정렬이란? 어떤 숫자 배열이 Input으로 들어왔을 때, 뒤죽박죽인 그 수열을 오름차순으로 정렬해나가는 과정을 거칩니다. 결국 Output은 "오름차순 수열"로 "정렬"됩니다. 이때, 삽입정렬에서는 정렬시에 다음과 같은 방식을 따릅니다 "이미 정렬된 앞 원소들"과 "기준이 되는 수인 key"를 대소비교합니다. 그리고 key인 수를 "이미 정렬된 앞 수열"의 적절한 자리에 삽입합니다. 이때, 이미 정렬되어있는 앞 원소들과 key를 차례차례 대소비교해가며 삽입의 위치를 정합니다. 이러한 정렬 방식을 삽입정렬이라고 합니다. 예를 들어 3 8 5 2 1이라는 수열이 있다고 합시다. 왼쪽에서 오른쪽 방향으로 차례차례 수의 크기를 비교해나가며 정렬을 쭉 하게 됩니다. 어떤 수를 그 앞자리에 있는 수와 하나하나 ..

간단히 말하자면 자연스러운 정렬 즉, 자연정렬은 자연스러운 순서 1,2,3, ... 를 따라 정렬한다. 하지만 모든 타입의 배열이 이러한 자연스러운 정렬 방식을 따르는 것은 아니다. 배열의 정렬 방식은 배열 요소의 형식(타입, 클래스)마다 다르다. 좋은 예시 하나는 String클래스다. String 즉 문자열의 정렬 방법을 확인해보자. String[] a = {"324", "43", "12", "1", "39", "9"}; System.out.println(Arrays.toString(a)); Arrays.sort(a); System.out.println(Arrays.deepToString(a)); 실행 결과는 아래와 같다. [324, 43, 12, 1, 39, 9] [1, 12, 324, 39, 43,..