정렬

목록 안에 저장된 요소들을 특정한 순서대로 재배치하는 알고리즘

정렬 시 고려사항

• 시간 복잡도
• 메모리 사용량
• 안정성: 데이터의 순서가 바뀌지 않는지
• 직렬 vs 병렬

종류

• 선택 정렬(Selection Sort)
  • 선택된 값과 나머지 데이터 중 비교하여 알맞은 자리를 찾는 알고리즘. 안정성은 보장되지 않음
  • 시간 복잡도: O(n^2)
    • worst, average, best 모두 동일

• 삽입 정렬(Insertion Sort)
  • 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳으로 삽입하는 알고리즘
  • 성능은 버블 정렬보다 좋음
  • 시간 복잡도: O(n^2)
    • worst, average 동일. best 이미 정렬 되어있다면 O(n)

• 버블 정렬(Bubble Sort)
  • 인접한 두 수를 비교하여 오름차순 or 내림차순으로 정렬. 안정성 보장
  • 시간 복잡도: O(n^2)
    • worst, average, best 모두 동일

• 병합 정렬(Merge Sort)
  • 둘 이상의 부분집합으로 가르고 각 부분집합을 정렬한 뒤 다음 부분집합을 정렬하여 다시 정렬된 형태로 합치는 방식. 안정성 보장
  • 분할 정복법 사용 (Divide-And-Conquer)
    • 분할: 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
    • 정복: 각각의 작은 문제를 순환적으로 해결
  • 병합 정렬은 배열을 원소가 하나만 남을 때 까지 계속 이분할 한 다음, 대소관계를 고려하여 다시 재배열 하며 원래 크기의 배열로 병합
  • 데이터 집합이 메모리에 한번에 올리기에 너무 클 때 쓰기 좋은 방법
  • 시간 복잡도: O(nlog n)
    • worst, average, best 모두 동일
    • 다른 알고리즘과 비교했을 때 O(n) 수준의 메모리가 추가로 필요하다는 단점이 있음

• 힙 정렬(Heap Sort)
  • 트리 기반으로 최대 힙 트리 or 최소 힙 트리를 구성해 정렬하는 방법. 안정성 보장하지 않음
  • 내림차순 정렬을 위해서는 최대힙, 오름차순 정렬을 위해서는 최소힙을 구성하면 됨
  • 완전 이진 트리
  • 시간 복잡도: O(nlog n)
    • worst, average, best 모두 동일

최대 힙

• 퀵 정렬(Quick Sort)
  • 분할 정복법과 재귀를 사용하여 정렬하는 알고리즘
  • 데이터 집합 내에 임의의 기준(pivot)값을 정하고 해당 피봇을 기준으로 두 개의 부분 집합으로 나눔
  • 한쪽에는 피봇보다 작은 값들만, 다른 한쪽에는 큰 값들만 놓음. 안정성 보장하지 않음
  • 더이상 쪼갤 부분 집합이 없을 때 까지 재귀적으로 적용
  • 시간 복잡도: 
    • O(nlog n) average, best
    • O(n^2) worst

---

문자열이 엄청 길 때 정렬을 하는 방법

• 문자열이 많을 경우 외부 정렬 기법을 사용하거나 메모리 효율적인 알고리즘인 병합 정렬을 사용하는 것이 좋음

병렬 병합 정렬

• 일반 병합 정렬을 병렬 처리로 최적화한 알고리즘
• 대량의 데이터를 병렬로 분할하고 정렬하여 처리 속도를 높이는데 사용됨
• 장점
  • CPU의 멀티코어를 활용하여 대량 데이터 처리 속도를 높일 수 있음
  • 분할 및 병합 작업이 독립적이기 때문에 병렬화에 적합함
• 단점
  • 병렬화 오버헤드(스레드 생성, 관리 등)가 작동 시간을 늘릴 수 있음
  • 데이터가 작을 경우 병렬화가 일반 정렬보다 비효율적일 수 있음

전 국민의 키 데이터에서 중간 값을 찾는 방법

• 정렬 후 중간 값 찾기
  • 데이터를 정렬한 뒤 중앙 값을 찾음
  • 시간 복잡도 : O(nlogn). O(nlogn)O(n\log n)
  • 데이터가 너무 크면 메모리나 성능 이슈가 발생할 수 있음
• 선택 알고리즘 (Median of Medians)
  • 정렬 없이 중간 값을 직접 착아내는 알고리즘
  • 시간 복잡도: O(n). O(n)O(n)
  • 분할 정복 기법을 활용하여 데이터를 부분 집합으로 나누고 재귀적으로 중앙 값을 계산
  • 메모리 효율성과 속도에서 유리
• 스트리밍 데이터 처리(Sliding Window)
  • 대규모 데이터를 스트리밍 형태로 처리하면서 중간값을 유지
  • 힙(Heap)을 사용하여 데이터의 절반씩을 유지하고 중앙 값을 실시간으로 계산
  • 시간 복잡도: O(nlogk) k는 힙 크기. O(nlogk)O(n \log k)
  • 스트리밍 환경에서 데이터 처리에 적합한 방식