Sorting(정렬) 알고리즘의 주요 특성

Sorting 알고리즘 개발시에는 무엇을 주로 고려해야 하는가?

• Time Efficiency: 얼마나 빠른 시간 내에 정렬을 수행할 수 있는가?
• Stablility: 가령 [1, 1]와 같은 리스트가 있다고 하면, 정렬한 뒤에도 이 두 값의 위치가 변하지 않는가?라는 것을 의미하죠. 두 값이 같다면 이 두 원소 간에 swap이 발생하지 않아야 한다는 이야기죠.
  • 아니 그게 뭐가 중요해?라는 생각이 들 수 있지만, 만약 각 원소가 Object고, 비교해야 하는 attribute가 같다고 하죠.
  • Stablility가 유지되지 못할 경우, cmpkey가 같으니까, 이 두 객체의 위치가 바뀔 수도 있습니다.
  • 즉 Stable하다면 값이 같을 때 위치가 바뀌지 않는 것, Unstable하다면 값이 같아도 위치가 바뀔 수 있다는 것을 의미합니다.
• In-place/out-of-place sorting: ’시간’이 아닌 ’공간’에 대한 문제로, 정렬 시에 필요로 하는 추가 메모리 공간이 얼마나 필요하냐? 를 의미합니다.
  • in-place sorting: 정렬의 대상이 되는 array의 크기가 커져도, constant한 메모리 공간이 필요한 경우
  • out-place sorting: 정렬의 대상이 되는 array의 크기가 커질 때 linear 혹은 그 이상의 메모리 공간이 필요한 경우
• Internal or external Sorting: 정렬을 할때, 컴퓨터의 메인 메모리에 데이터가 저장되는 경우 Internal sorting이라고 하고, 상대적으로 낮은 Hard drive와 같은 메모리에 담겨도 되는 경우 External Sorting이라고 합니다.
  • 사실 이건 좀 낯설게 느껴질 수 있는데요, 우리가 일상에서 프로그래밍으로 다루는 정도의 데이터는 메모리에 올라가는데 문제가 없습니다. 다만, 훨씬 큰 종류의 데이터, 가령 1테라 바이트 정도의 용량의 배열을 정렬해야 한다 라면 어떨가요.
  • 따라서, 내부 메모리처럼 조작이 자유롭지 못한 경우에는 한번에 다 정렬하는 경우보다 배열을 쪼개어서 정렬하는 MergeSort의 개선된 형태가 좀 더 적합하죠. 즉, 메모리에 한 번에 다 올릴 수 없으니까, 이 공간을 고려하여 나누어 정렬하도록 알고리즘을 수정해야 합니다.