Sort

[su3inni]

정렬 알고리즘 선택시 아래 요소를 고려해야한다.

• 데이터의 양
• 초기 데이터의 배열 상태
• 키 값들의 분포 상태

[su3inni]

정렬 Sort 의 종류

1. 내부 정렬

• 모든 데이터를 메모리 내에서 정렬하는 방법이다. 주로 RAM과 같은 메모리 공간에서 이루어지기 때문에 속도가 빠르다.
• 작은 데이터 크기나 메모리 용량이 충분할 경우 적용한다.

2. 외부 정렬

• 데이터가 너무 많아 한 번에 메모리에 올릴 수 없을 때 사용되는 방법이다.
• 주로 하드디스크에서 이루어지기 때문에 내부 정렬보다 느리다.
• 대량의 데이터나 메모리 용량이 부족한 경우에 사용된다.

[su3inni]

내부 정렬의 종류

1. 버블 정렬 Bubble Sort

• 인접 데이터를 비교하면서 데이터를 정렬한다.
• 간단하게 이해하고 구현할 수 있지만, 비효율적이다. 대규모 데이터셋이나 성능이 중요한 경우 사용하지 않는다.
• 시간 복잡도는 O(n^2) 이며, 이미 정렬된 배열을 정렬할 때 최선의 경우 O(n)이다.
  • 역으로 정렬되어있는 경우를 다시 재정렬할 때 최악
  • 이미 정렬되어있는 배열이 최선

2. 삽입 정렬 Insertion Sort

• 정렬된 배열에 새로운 값을 삽입시켜 정렬하는 방법이다.
• 작은 데이터셋에 적합한 방법이고 이미 정렬되어있는 경우 효과적이다.
• 최악/평균 시간 복잡도는 O(n^2)이며 이미 정렬되어있는 최선의 경우 O(n)이다.

버블정렬과 삽입정렬의 차이의 경우 버블 정렬은 지속적으로 값 교환이 빈번하게 일어나지만 삽입정렬의 경우 정렬이 진행될 수록 정렬된 부분이 늘어나므로 효율적이다.

3. 선택 정렬

• 배열에서 최솟값을 찾아 맨 앞으로 이동시키는 과정을 반복시키는 방식이다.
• 데이터 이동이 빈번하게 나타난다.
  • 시간 복잡도는 O(n^2)

4. 병합 정렬 Merge Sort

• 분할정복 알고리즘의 일종으로 배열을 반을 나누고 부분 정렬 후 다시 병합하여 전체 배열을 정렬하는 방식이다.
• 항상 일정한 시간 복잡도 O(nlogn)을 보이기 때문에 매우 효율적인 정렬 알고리즘이다.
• 추가적인 메모리 공간이 필요하며 병합할 때 임시 배열이 필요하다.
• 대용량 데이터셋에서도 잘 동작한다.

5. 퀵 정렬 Quick Sort

• 분할 정복 알고리즘을 기반으로한 정렬 알고리즘이다.
  • 배열에서 피벗 Pivot을 선택하고 Pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누어 정렬하는 방식이다.
    • 피벗은 정렬의 기준이 되는 값으로 일반적으로 가운데 원소를 선택한다.
    • 나뉜 두 부분에 대해 재귀적으로 퀵 정렬을 수행한다.
• 추가적인 메모리를 사용하지 않는다.
• 최악의 경우 O(n^2) : pivot이 항상 최소값이나 최대값으로 선택될 때
• 평균/최선의 경우 O(nlogn) : pivot이 중간값으로 선택될 때

[su3inni]

6. 힙 정렬 Heap Sort

• Heap이라는 자료구조를 기반으로 하는 정렬 알고리즘이다.
  • 일종의 이진트리 구조로, 부모 노드의 값이 자식 노드의 값보다 항상 크거나(Max Heap) 작은 조건(Min Heap)을 만족한다.
• 시간 복잡도는 항상 일정한 성능을 보이는 O(nlogn)이다.
• 추가적인 메모리를 사용하지 않고 In-place 정렬이다.
• 위의 5가지 정렬과 다르게 안정 정렬이 아니다. ( 같은 수의 순서가 보장되지 않음 ).
• 추가 메모리를 사용하지 않고 대량의 데이터를 정렬할 때 유용하다.