Sorting Algorithm(정렬 알고리즘)

• 시간 복잡도와 공간복잡도 비교

	best-case	average-case	worst-case	space complexity
Insertion Sort	O(n)	O(n²)		O(1)
Merge Sort	O(n log n)			O(n)
Quick Sort	O(n log n)		O(n²)	O(n)
Heap Sort	O(n log n)			O(1)
Counting Sort	O(n + k)			O(k)

 

• Insertion Sort
  
  • 특징
    • 삽입 정렬은 같은 크기의 데이터 시퀀스라도, 이미 정렬된 정도에 따라 빠를 수도 느릴 수 도 있다. 역으로 정렬된 경우 최악의 성능을 보인다.
    • 데이터 셋의 크기가 시간에 따라 증가할 때, 실시간 정렬을 요구하는 경우에 사용한다.
  • Pros
    • 어느 정도, 이미 정렬된 경우 매우 매우 효과적이다.
    • auxiliary space를 요구하지 않는 In-place 알고리즘이다.
    • 작은 데이터 셋일 경우 효과적이다.
    • 같은 키 값을 가진 원소들의 상대적인 순서를 바꾸지 않는 Stable 알고리즘이다.
  • Cons
    • 데이터 쉬프팅 때문에, 큰 데이터셋일 경우 비효율적이다. 
• Merge Sort
  • 특징
    • 데이터 셋의 크기가 크고, Stability가 요구될 경우, 또는 메인 메모리에 저장된 데이터 셋을 외부에서 정렬하고자 할 때, 사용된다.
  • Pros
    • 데이터 셋 전체를 여러 번 순회하지 않기 때문에, Insertion Sort와는 달리 큰 데이터셋에 유리하다.
    • 큰 데이터 셋에서, Heap Sort보다 조금 빠르다.
    • 최악의 경우, O(n log n)이므로 평타는 친다.
    • divide-and-conquer
  • Cons
    • 작은 데이터셋에서 불리하다.
    • 일반적인 경우, Quick Sort보다 느리다.
    • 데이터 셋이 정렬되어 있더라도, 모든 과정을 거친다.
    • Heap Sort보다 두 배의 메모리를 사용한다.
• Quick Sort
  • 특징
    • In-place 알고리즘이기 때문에, 시스템의 메모리 공간이 한정적인 상용 데이터 베이스 시스템에서 사용한다.
    • divide-and-conquer 혹은 recursive 알고리즘이다.
    • 피봇의 위치에 따라 성능이 결정된다. 
      • Balanced Partition 일 경우, Merge Sort 이상의 성능을 낸다.
      • Unbalaced Partition 일 경우, Insertion Sort 보다 느리다.
  • Pros
    • O(1)의 공간 복잡도
  • Cons
    • Unstable 알고리즘
• Heap Sort
  • 특징
    • In-place 알고리즘이라, O(1)의 공간 복잡도를 가지기 때문에,  임베디드 시스템, 실시간 시스템에서 많이 쓰인다.
    • Complete Binary Tree를 사용하므로, 트리의 모든 레벨이 차있다.
  • Pros
    • Merge Sort와 마찬가지로 Heap Sort는 점근적으로 최적화된 비교 알고리즘이다.
    • O(1)의 공간 복잡도
  • Cons
    • Unstable 알고리즘
• Counting Sort
  • 특징
    • 인풋의 범위가 작을 때(small-k), 그래픽스 분야에서 색을 정렬할 때, 전산 생물학에서 DNA 시퀀스를 정렬할 때 사용한다.
    • 비교 알고리즘이 아님
  • Pros
    • 작은 데이터셋에서, 선형 시간의 성능을 보임
  • Cons
    • n개의 원소들이 정수 0~k까지의 범위에 있다고 가정하고 정렬을 시작함.
    • k >>> n 일 경우, 선형 시간복잡도의 장점이 사라짐. 이 경우 Merge Sort가 유리함.