알고리즘 공부를 하다보면 간단한 정렬 알고리즘 하나 정도는 알아두는 편이 좋습니다. 그런데, 정렬 알고리즘들은 정말 다양하게 존재합니다. 물론, 성능도 제각각입니다. 그럼 어떤 알고리즘을 알아두는 것이 좋을까요?

보통 후보로 뽑히는 알고리즘은 Quick Sort 또는 Merge Sort입니다. 둘 다 분할 정복(Divide & Conquer) 기반 알고리즘이며 성능도 O(N log N)으로 비슷합니다. 취향에 따라 선택하면 되지만, Merge Sort가 좀 더 구현하기 쉬워서 개인적으로는 후자를 추천합니다.

Quick Sort와 Merge Sort를 비교해보면 다음과 같습니다.

• Quick Sort는 Worst Case에서 O(N^2)의 속도를 가진다.
• Merge Sort는 Worst Case에서도 O(N log N) 속도를 유지한다.
• 대신 Merge Sort는 더 큰 메모리 공간이 필요하고 메모리 할당/복사/삭제가 빈번해서 Quick Sort보다 속도가 좀 더 느린 경우도 종종 있다. (평균적으로는 비슷하다.)
• Merge Sort는 같은 값들의 순서가 정렬 후에도 유지되는 stable 한 성격을 갖고 있고, Quick Sort는 그러지 않다.

참고로 C++ 표준 라이브러리인 STL 에서는 2가지의 sort 함수를 제공하고 있는데, 일반적인 sort는 Quick Sort, stable_sort는 Merge Sort를 사용하고 있다고 합니다.

자, 그럼 MergeSort에 대해서 단계적으로 살펴보도록 하겠습니다.

분할

분할 정복 기반의 알고리즘이기 때문에 일단 분할을 합니다. 다음과 같이 1/2씩 나누기만 하면 됩니다.

정합

이렇게 나누어진 값들을 이제 합치면서 정렬을 해줍니다.

정렬 방법은 다음과 같습니다.

코드

실제 코드로 확인해보도록 하겠습니다. 다음은 C++ 코드입니다.

int temp[MAX];

void mergeSort(int*arr, int left, int right) {
  // 종료 조건: 나눌 수 없을 때까지 나눈다.
  if(left >= right) {
    return;
  }

  // 분할
  int mid = (left + right) / 2;
  mergeSort(arr, left, mid);
  mergeSort(arr, mid + 1, right);

  // 정합
  int length = right - left + 1;
  int offset = 0, offset1 = left, offset2 = mid + 1;

  while((offset1 <= mid) || (offset2 <= right)) {
    if(offset1 > mid) {
      temp[offset++] = arr[offset2++];
      continue;
    }
    if(offset2 > right) {
      temp[offset++] = arr[offset1++];
      continue;
    }
    if(arr[offset1] <= arr[offset2]) {
      temp[offset++] = arr[offset1++];
      continue;
    } else {
      temp[offset++] = arr[offset2++];
      continue;
    }
  }

  for(int i = 0; i < length; i++) {
    arr[left + i] = temp[i];
  }
}

마크다운(Markdown) 문법에 대해서 간단히 포스팅해봅니다.
웹페이지에 접속해서 글을 작성하는 것이 아니라, 메모장 등의 일반 에디터기를 이용해서 블로그 글을 작성할 수 있습니다. 자신이 익숙한 에디터기가 있다면 상당히 편리합니다. 대신 수동으로 각종 태그들을 직접 입력해야 한다는 점에서 어느 정도 장벽이 있습니다. 하지만, 태그 몇 가지만 익히면 편리하고 빠르게 글을 작성할 수 있습니다.

여기서는 필수적인 문법 몇 가지만 언급하도록 하겠습니다.

제목

제목은 다음과 같이 사용할 수 있습니다.

# 큰 제목 (H1)
## 두번째 제목 (H2)
### 세번째 제목 (H3)
...

줄바꿈

마크다운에서 줄바꿈은 문장 맨 끝에 스페이스 두 번을 넣으면 됩니다.

안녕하세요.  
오랜만입니다.

문단 나누기

문단을 나누고자 할 때는 한 줄을 비우면 됩니다.

문단을 나누고 싶으시면 이렇게

한 줄을 비우시면 됩니다.

이탤릭체, 볼드체, 취소선

*이탤릭체*, _이탤릭체_
**볼드체**, __볼드체__
~~취소선~~

인용

> 인용하는 문구

테이블

Header | Header
------ | ------
Cell   | Cell  

Keyboard

<kbd>Ctrl</kbd> + <kbd>Alt</kbd> + <kbd>Del</kbd>

하이퍼링크

[단어](주소)

이미지 삽입

![사진 이름](주소)

안녕하세요. 이 페이지는 Markdown이 화면에 어떻게 렌더링되는지 확인하기 위해서 작성한 테스트 페이지입니다.

제목 1

제목 2

제목 3

제목 4

제목 5

제목 6

테이블 테스트

테이블 Allignment

Keyboard

Ctrl + Alt + Del

수평선

목록

• 목록 1
• 목록 2
• 목록 3

인용문

안녕하세요. 여기는 snowdeer 블로그입니다.
인용문 예제입니다.

인용문 안의 인용문

정의

Jekyll

정적 웹페이지 플랫폼

Code Block

기본 Code Block

int main(int argc, char** argv) {
    printf("Hello~ Welcome to SnowDeer's Blog.\n");

    return 0;
}

italic and bold text,
inline code in backticks,
and basic links.

CSS 클래스 테스트

message

안녕하세요.

lead

안녕하세요.

container

안녕하세요.

Default Syntax Highlighter

int main(int argc, char** argv) {
    printf("Hello~ Welcome to SnowDeer's Blog.\n");

    return 0;
}

Google Code Prettyfy

int main(int argc, char** argv) {
    printf("Hello~ Welcome to SnowDeer's Blog.\n");

    return 0;
}

Bitmap 이미지를 파일로 저장하는 코드는 다음과 같습니다.

private void saveBitmapAsFile(Bitmap bitmap, String filepath) {
    File file = new File(filepath);
    OutputStream os = null;

    try {
      file.createNewFile();
      os = new FileOutputStream(file);

      bitmap.compress(CompressFormat.PNG, 100, os);

      os.close();
    } catch (Exception e) {
      e.printStackTrace();
    } 
  }

안드로이드에서 사진을 ImageView 등에 출력할 때, 이미지의 Rotation 정보를 획득하여 적절하게 회전시켜주는 방법입니다.

이미지의 Orientation 정보 획득

public int getOrientationOfImage(String filepath) {
    ExifInterface exif = null;

    try {
      exif = new ExifInterface(filepath);
    } catch (IOException e) {
      e.printStackTrace();
      return -1;
    }

    int orientation = exif.getAttributeInt(ExifInterface.TAG_ORIENTATION, -1);

    if (orientation != -1) {
      switch (orientation) {
        case ExifInterface.ORIENTATION_ROTATE_90:
          return 90;

        case ExifInterface.ORIENTATION_ROTATE_180:
          return 180;

        case ExifInterface.ORIENTATION_ROTATE_270:
          return 270;
      }
    }

    return 0;
  }

Image 회전

  public Bitmap getRotatedBitmap(Bitmap bitmap, int degrees) throws Exception {
    if(bitmap == null) return null;
    if (degrees == 0) return bitmap;
    
    Matrix m = new Matrix();
    m.setRotate(degrees, (float) bitmap.getWidth() / 2, (float) bitmap.getHeight() / 2);

    return Bitmap.createBitmap(bitmap, 0, 0, bitmap.getWidth(), bitmap.getHeight(), m, true);;
  }