알고리즘 - 정렬 알고리즘(병합 정렬, 퀵 정렬, 기수 정렬)

병합 정렬

• 원리: 데이터를 반으로 나누어 정렬 후 병합
• 특징: 안정적인 정렬이며, 추가적인 메모리 공간 필요
• 공간 복잡도: O(n)
• 시간 복잡도: O(n log n)
• 예시
  • 최초에는 8개의 그룹으로 나눔
  • 이 상태에서 2개씩 그룹을 합치며 오름차순 정렬
  • 투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합함
  • 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킴

  [5, 3, 8, 2, 4, 1, 6, 7]
  → [5], [3], [8], [2], [4], [1], [6], [7]
  → [3, 5], [2, 8], [1, 4], [6, 7]
  → [2, 3, 5, 8], [1, 4, 6, 7] // 여기 병합 기준으로 설명
  → [1, 2, 3, 4, 5, 6, 7, 8]
  

  • 왼쪽 배열: [2, 3, 5, 8], 오른쪽 배열: [1, 4, 6, 7] → 각각 배열의 포인터를 둠
  1. 첫 번째 비교
     • 왼쪽 포인터: 0 → 값: 2
     • 오른쪽 포인터: 0 → 값: 1
     → 두 값을 비교 후 작은 값을 새로운 배열에 둠, 작은 쪽인 포인터 이동 (오른쪽 포인터)
     • 새로운 배열 [1]
  2. 두 번째 비교
     • 왼쪽 포인터: 0 → 값: 2
     • 오른쪽 포인터: 1 → 값: 4
     → 2가 더 작으므로 왼쪽 포인터 이동 및 배열에 2 추가
     • 새로운 배열 [1, 2]
  3. 세 번째 비교
     • 왼쪽 포인터: 1 → 값: 3
     • 오른쪽 포인터: 1 → 값: 4
     → 3이 더 작으므로 왼쪽 포인터 이동 및 배열에 3 추가
     • 새로운 배열 [1, 2, 3]
  4. 네 번째 비교
     • 왼쪽 포인터: 2 → 값: 5
     • 오른쪽 포인터: 1 → 값: 4
     → 4가 더 작으므로 오른쪽 포인터 이동 및 배열에 4 추가
     • 새로운 배열 [1, 2, 3, 4]
  5. 다섯 번째 비교
     • 왼쪽 포인터: 2 → 값: 5
     • 오른쪽 포인터: 2 → 값: 6
     → 5가 더 작으므로 왼쪽 포인터 이동 및 배열에 5 추가
     • 새로운 배열 [1, 2, 3, 4, 5]
  6. 여섯 번째 비교
     • 왼쪽 포인터: 3 → 값: 8
     • 오른쪽 포인터: 2 → 값: 6
     → 6이 더 작으므로 오른쪽 포인터 이동 및 배열에 6 추가
     • 새로운 배열 [1, 2, 3, 4, 5, 6]
  7. 일곱 번째 비교
     • 왼쪽 포인터: 3 → 값: 8
     • 오른쪽 포인터: 3 → 값: 7
     → 7이 더 작으므로 오른쪽 포인터 이동 및 배열에 7 추가
     • 새로운 배열 [1, 2, 3, 4, 5, 6, 7]
  8. 오른쪽 배열을 모두 정렬시켰으므로, 이후 왼쪽 배열을 순서대로 새로운 배열에 추가
     • 새로운 배열 [1, 2, 3, 4, 5, 6, 7, 8]

 

퀵 정렬

• 원리: 기준점(피벗)을 설정하고, 피벗보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 분할하여 정렬
• 특징: 분할 정복 방식으로 동작하며, 실제로 가장 빠르게 동작하는 경우가 많음
• 공간 복잡도: 필요 없음
• 시간 복잡도: O(n log n)
  • 최악의 시간 복잡도: O(n^2) (피벗 선택이 비효율적인 경우)
• 예시

[3, 2, 5, 4, 1] (피벗: 3)
→ [2, 1] [3] [5, 4] // 1
→ [1, 2] [3] [4, 5] // 2
→ [1, 2, 3, 4, 5]   // 3

• 1. 피벗(3) 기준으로 왼쪽은 피벗 보다 작은 데이터, 오른쪽은 피벗보다 큰 데이터 (분할)
     • 피벗: [3]
     • 작은 데이터: [2, 1]
     • 큰 데이터: [5, 4]
  2. 각 데이터 배열을 정렬
     • 피벗: [3]
     • 작은 데이터: [1, 2]
     • 큰 데이터: [4, 5]
  3. 데이터 배열 병합
     • [1, 2, 3, 4, 5]

 

기수 정렬

• 원리: 자릿수별로 데이터를 비교하여 정렬, 낮은 자릿수부터 높은 자릿수까지 진행함
• 특징: 바교를 사용하지 않음, 정수 또는 고정 길이의 문자열에 적합
• 시간 복잡도: O(nk) (k: 자릿수의 길이)
• 예시
  • 대상 데이터: [16, 80, 18, 77, 03, 24, 88, 23]
  • 기수 정렬은 자릿수를 기준으로 비교하기 때문에 10개의 큐를 사용
  •  → 각 자릿수는 0~9까지의 수로 이루어지기 때문
  • 1의 자릿수 큐는 0 ~ 9까지의 큐로 이루어짐
  • 16부터 1의 자릿수를 비교하여 해당 큐에 삽입
    • 16: 6번째 큐
    • 80: 0번째 큐
    • 18: 8번째 큐
    • 77: 7번째 큐
    • 03: 3번째 큐
    • 24: 4번째 큐
    • 88: 8번째 큐
    • 23: 3번째 큐
    → 1의 자리 큐
    • 0번째 큐: [80]
    • 1번째 큐: []
    • 2번째 큐: []
    • 3번째 큐: [03, 23]
    • 4번째 큐: [24]
    • 5번째 큐: []
    • 6번째 큐: [16]
    • 7번째 큐: [77]
    • 8번째 큐: [18, 88]
    • 9번째 큐: []
  → 0번째 큐부터 0번째 큐까지 순서대로 10의 자릿수 큐로 이동
  • 순서대로 10의 자리 수 큐로 이동
    • 80: 8번째 큐
    • 03: 0번째 큐
    • 23: 2번째 큐
    • 24: 2번째 큐
    • 16: 1번째 큐
    • 77: 7번째 큐
    • 18: 1번째 큐
    • 88: 8번째 큐
    → 10의 자리 큐
    • 0번째 큐: [03]
    • 1번째 큐: [16, 18]
    • 2번째 큐: [23, 24]
    • 3번째 큐: []
    • 4번째 큐: []
    • 5번째 큐: []
    • 6번째 큐: []
    • 7번째 큐: [77]
    • 8번째 큐: [80, 88]
    • 9번째 큐: []
• 순서: [80, 03, 23, 24, 16, 77, 18, 88 ] → 이 순서는 적어도 1의 자리 수는 정렬되어 있음

→ 최종 정렬 데이터: 0번째 큐부터 꺼내기

[03, 16, 18, 23, 24, 77, 80, 88]