2장 정렬

정렬 알고리즘의 기본 개념

정렬: 데이터를 크기 순서(오름차순/내림차순)로 재배치하는 작업.
정렬 방식의 구분:
- 내부 정렬: 모든 데이터를 주기억장치(RAM)에 저장 후 정렬.
- 외부 정렬: 데이터가 너무 커서 일부만 메모리에 적재하고 나머지는 보조기억장치에서 처리.
정렬의 특성:
- 안정적 정렬 (Stable Sort): 동일한 값을 가진 데이터의 상대적 순서가 유지됨.
- 제자리 정렬 (In-place Sort): 추가적인 저장 공간을 거의 사용하지 않음.

정렬 - 1

SelectionSort (A[ ], n)
{
  for (i=0; i < n-1; i++) {
    min = i;
    for (j=i+1; j < n; j++)
      if (A[min] > A[j])
        min = j;
        A[i]와 A[min]의 자리바꿈;
  }
  return (A);
}

BubbleSort (A[ ], n)
{
  for (i=0; i < n-1; i++) // 단계: (n-1)번 반복
    for (j=0; j < n-1; j++) // 왼쪽에서 오른쪽으로 진행하는 경우
      if (A[j] > A[j+1]) // ‘왼쪽 데이터 > 오른쪽 데이터’이면
      A[j]와 A[j+1]의 자리바꿈;
  return (A);
}

##개선된 버블정렬
Advanced_BubbleSort (A[ ], n)
{
  for (i=0; i < n-1; i++) { // 단계: 0, 1, …, (n-2)
    Sorted = TRUE; // 이미 정렬된 상태라고 가정
    for (j=0; j < (n-1) -i ; j++) // 왼쪽에서 오른쪽으로 진행하는 경우
      if (A[j] > A[j+1]) {
        A[j]와 A[j+1]의 자리바꿈;
        Sorted = FALSE; // 자리바꿈 발생 → 미정렬 상태
      }
    }
    if (Sorted == TRUE) break; // 이미 정렬된 상태이므로 종료
  } 
  return (A);
}

InsertionSort (A[ ], n)
{
  for (i=1; i < n; i++) { // A[0] 정렬 부분; 1, …, (n-1)까지 (n-1)번 반복
    val = A[i]; // 미정렬 부분 A[i..n-1]의 첫 번째 데이터 선택
    for (j=i; j > 0 && A[j-1] > val; j--) // 삽입할 위치 찾기
      A[j] = A[j-1]; // 정렬 부분의 A[j-1]이 크면 뒤로 한 칸 이동
    A[j] = val; // 찾아진 위치에 선택된 데이터 삽입
  }
  return (A);
}

1. 기본 개념

⦁ 내부 정렬 → 정렬할 전체 데이터를 주기억장치에 저장한 후 정렬하는 방식
⦁ 비교 기반 정렬 vs 데이터 분포 기반 정렬
- 비교 기반 정렬 → 두 데이터의 값 전체를 직접적으로 비교하여 어떤 값이 큰지 또는 작은지를 결정하여 정렬하는 방식 → 선택 정렬, 버블 정렬, 삽입 정렬, 셸 정렬, 합병 정렬, 퀵 정렬, 힙 정렬
- 데이터 분포 기반 정렬 → 데이터의 분포 정보를 활용하여 정렬을 수행하는 방식 → 계수 정렬, 기수 정렬, 버킷 정렬
⦁ 안정적 정렬 → 같은 값을 갖는 데이터에 대한 정렬 전의 상대적인 순서가 정렬 후에도 그대로 유지되는 정렬 방식
⦁ 제자리 정렬 → 입력 데이터를 저장하는 공간 이외에 추가적인 저장 공간을 상수 개만 사용하는 정렬 방식

2. 선택 정렬

⦁ 입력 배열에서 가장 작은 값부터 순서대로 선택해서 나열하는 방식 → 미정렬 부분에서 최솟값을 찾은 후, 이 최솟값과 미정렬 부분의 첫 번째 데이터와 위치를 교환하는 과정을 반복
⦁ O(n2), 불안정적, 제자리
⦁ 입력 데이터의 순서에 민감하지 않음 → 언제나 동일한 시간 복잡도를 가짐

3. 버블 정렬

⦁ 왼쪽(또는 오른쪽)에서부터 모든 인접한 두 값을 비교하여 왼쪽의 데이터가 더 큰 경우에는 오른쪽 데이터와 자리를 바꾸는 과정을 반복해서 정렬하는 방식
⦁ O(n2), 안정적, 제자리
⦁ 인접한 두 데이터의 비교 횟수와 처리 단계의 수를 줄이도록 개선 가능 → 개선된 알고리즘의 경우에는 입력 데이터의 상태에 따라 성능이 달라짐 → 데이터가 원하는 순서대로 이미 정렬되었을 때 O(n), 역순으로 정렬되었으면 O(n2)
⦁ 선택 정렬에 비해 데이터 교환이 많이 발생

4. 삽입 정렬

⦁ 주어진 데이터를 하나씩 뽑은 후, 나열된 데이터들이 항상 정렬된 상태를 갖도록 바른 위치를 찾아 뽑은 데이터를 삽입해서 나열하는 방식
⦁ O(n2), 안정적, 제자리
⦁ 입력 데이터의 원래 순서에 민감 → 역순의 경우에는 O(n2), 제 순서대로 거의 정렬되었으면 O(n)

5. 셸 정렬

⦁ 삽입 정렬의 단점 보완 → 데이터가 삽입될 위치에서 멀리 떨어져 있어도 한 번에 한 자리씩만 이동해서 제자리를 찾아가야 함
⦁ 처음에는 멀리 떨어진 두 원소를 비교/교환하고, 점차 가까운 위치의 원소를 비교/교환한 뒤, 맨 마지막에는 인접한 원소를 비교/교환하는 정렬 방식 → 개념적으로는 입력 배열을 부분배열로 나누어 삽입 정렬을 수행하는 과정을 부분배열의 크기와 개수를 줄여가면서 반복적으로 수행
⦁ O(n2), 불안정적, 제자리
⦁ 사용하는 순열에 따라 성능이 달라짐 → 각 순열값은 부분배열의 개수이며, 동시에 각 부분배열 내에서 이웃한 데이터 간의 거리를 의미

정렬 2

퀵 정렬의 개념

퀵 정렬은 분할 정복(Divide and Conquer) 방법을 사용하는 정렬 알고리즘입니다. 데이터를 작은 부분으로 나누고, 각 부분을 따로 정렬한 후 합치는 방식입니다. **피벗(Pivot)**이라는 기준값을 사용해 데이터를 두 그룹으로 나누며, 이 과정을 반복하여 데이터를 정렬합니다.

퀵 정렬의 주요 단계

1. 피벗(Pivot) 선택

피벗은 배열에서 기준이 되는 값입니다.
일반적으로 배열의 첫 번째, 마지막, 또는 중간 값을 피벗으로 선택합니다.
피벗을 기준으로 데이터를 두 그룹으로 나눕니다:
- 피벗보다 작은 값 → 왼쪽 그룹
- 피벗보다 큰 값 → 오른쪽 그룹

2. 분할(Partitioning)

배열을 피벗을 중심으로 두 부분으로 나눕니다.
이 과정에서 피벗은 자신의 최종 위치를 찾게 됩니다.
나뉜 두 그룹은 각각 다시 퀵 정렬을 적용합니다.

3. 재귀 호출(Recursion)

분할된 두 그룹에 대해 동일한 과정을 반복합니다.
배열의 크기가 1 이하가 되면 더 이상 나눌 필요가 없으므로 정렬이 완료됩니다.

퀵 정렬의 예제

예제: [30, 45, 20, 15, 40, 25, 35, 10]

1단계: 피벗 선택 및 분할

피벗: 30 (배열의 첫 번째 값)
30보다 작은 값 → [20, 15, 25, 10] (왼쪽 그룹)
30보다 큰 값 → [45, 40, 35] (오른쪽 그룹)
결과: [20, 15, 25, 10], 30, [45, 40, 35]

2단계: 왼쪽 그룹 [20, 15, 25, 10]에 대해 퀵 정렬 적용

피벗: 20
20보다 작은 값 → [15, 10]
20보다 큰 값 →
결과: [15, 10], 20,

3단계: 오른쪽 그룹 [45, 40, 35]에 대해 퀵 정렬 적용

피벗: 45
45보다 작은 값 → [40, 35]
결과: [40, 35], 45

4단계: 모든 부분 배열이 크기 1이 될 때까지 반복

최종적으로 모든 배열을 합치면:
[10, 15], 20, , 30, , , 45
결과: [10, 15, 20, 25, 30, 35, 40, 45]

퀵 정렬의 특징

장점

평균 시간 복잡도는 O(nlog⁡n)로 매우 빠릅니다.
추가적인 메모리를 거의 사용하지 않는 제자리(in-place) 알고리즘입니다.

단점

최악의 경우(예: 이미 정렬된 배열에 대해 첫 번째 값을 피벗으로 선택하면), 시간 복잡도가 O(n2)가 될 수 있습니다.
데이터의 순서를 유지하지 않으므로 불안정한 정렬 알고리즘입니다.

퀵 정렬과 실생활 비유

퀵 정렬은 사람들이 키 순서대로 줄을 설 때와 비슷합니다:

한 사람이 기준(피벗)이 되어 "나보다 키 작은 사람은 왼쪽으로 가세요. 큰 사람은 오른쪽으로 가세요"라고 말합니다.
각 그룹에서 또 다른 사람이 기준이 되어 같은 작업을 반복합니다.
모든 사람이 자기 자리를 찾으면 줄이 완벽히 정렬됩니다.

퀵 정렬의 성능 분석

합병정렬

합병 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 방법을 사용하는 안정적인 정렬 알고리즘입니다. 데이터를 작은 부분으로 나눈 뒤 정렬하고, 다시 합치는 과정을 반복하여 전체 데이터를 정렬합니다. 아래에서 합병 정렬의 원리와 과정을 자세히 설명하겠습니다.

합병 정렬의 원리

1. 분할(Divide)

배열을 동일한 크기의 두 부분 배열로 나눕니다.
각 부분 배열을 더 이상 나눌 수 없을 때까지(즉, 배열의 크기가 1이 될 때까지) 계속 나눕니다.

2. 정복(Conquer)

나뉜 배열들을 각각 정렬합니다.
크기가 1인 배열은 이미 정렬된 상태로 간주됩니다.

3. 결합(Merge)

두 개의 정렬된 부분 배열을 하나의 정렬된 배열로 합칩니다.
이 과정에서는 각 배열의 첫 번째 값을 비교해 더 작은 값을 결과 배열에 넣는 방식으로 진행됩니다.

합병 정렬의 단계별 예제

예제: [60, 20, 70, 10, 80, 30, 50, 40]

1단계: 분할

주어진 배열을 반으로 나눕니다.
- [60, 20, 70, 10]과 [80, 30, 50, 40]
각 부분 배열을 다시 반으로 나눕니다.
- [60, 20], [70, 10], [80, 30], [50, 40]
더 이상 나눌 수 없을 때까지 반복합니다.
- , , , , , , ,

2단계: 병합(정렬하며 합치기)

크기가 1인 배열부터 병합합니다.
- 과 → [20, 60]
- 과 → [10, 70]
- 과 → [30, 80]
- 과 → [40, 50]
병합된 배열끼리 다시 병합합니다.
- [20, 60]과 [10, 70] → [10, 20, 60, 70]
- [30, 80]과 [40, 50] → [30, 40, 50, 80]
최종적으로 두 개의 큰 배열을 병합합니다.
- [10, 20, 60, 70]과 [30, 40, 50, 80] → [10, 20, 30, 40, 50, 60, 70, 80]

합병 정렬 알고리즘

알고리즘 구조

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        # 분할
        merge_sort(left_half)
        merge_sort(right_half)

        # 병합
        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # 남은 요소 추가
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

정렬 3

1. 힙 정렬 (Heap Sort)

원리

힙 정렬은 완전 이진 트리의 구조를 활용하여 데이터를 정렬합니다.
최대 힙(Max-Heap)을 구성하여 가장 큰 값을 루트로 올린 뒤, 이를 배열의 끝으로 이동시키고 나머지 부분을 다시 힙으로 재구성하는 과정을 반복합니다.

과정

주어진 배열을 최대 힙으로 변환합니다.
힙의 루트(최대값)를 배열의 마지막 위치로 이동합니다.
남은 배열을 다시 최대 힙으로 재구성하고 위 과정을 반복합니다.

특징

시간 복잡도:
- 최선/평균/최악: O(nlog⁡n)
- 힙 구성에 O(n), 삭제 및 재구성에 O(log⁡n) 소요.
공간 복잡도: O(1) (제자리 정렬).
안정성: 불안정 (동일한 값의 순서가 유지되지 않음).
제자리 여부: 제자리 정렬.

2. 계수 정렬 (Counting Sort)

원리

데이터의 크기를 기준으로 빈도수를 계산하여 데이터를 정렬하는 알고리즘입니다.
데이터가 특정 범위 내의 정수일 때 효과적입니다.

과정

데이터의 최댓값과 최솟값을 이용해 크기를 알 수 있는 배열(카운팅 배열)을 생성합니다.
각 데이터가 등장한 횟수를 카운팅 배열에 저장합니다.
카운팅 배열을 누적합 형태로 변환하여 각 데이터가 위치할 인덱스를 계산합니다.
입력 데이터를 순회하며 결과 배열에 데이터를 배치합니다.

특징

시간 복잡도:
- O(n+k), 여기서 k는 데이터 범위.
공간 복잡도: O(n+k) (추가적인 카운팅 배열 필요).
안정성: 안정적 (동일한 값의 순서 유지).
제자리 여부: 제자리 정렬 아님 (추가 공간 사용).

3. 기수 정렬 (Radix Sort)

원리

데이터를 자릿수별로 나누어 가장 낮은 자리부터 높은 자리까지 차례대로 정렬하는 알고리즘입니다.
내부적으로 계수 정렬과 같은 안정적인 알고리즘을 사용합니다.

과정

데이터의 가장 낮은 자리(LSD)부터 시작해 각 자리수를 기준으로 데이터를 그룹화하고 정렬합니다.
다음 자리수를 기준으로 반복합니다.
모든 자리수를 처리하면 최종적으로 데이터가 정렬됩니다.

특징

시간 복잡도:
- O(d⋅(n+k)), 여기서 d는 자릿수, k는 데이터 범위.
- 자릿수가 상수라면 선형 시간인 O(n).
공간 복잡도: O(n+k) (계수 정렬 사용 시 추가 공간 필요).
안정성: 안정적 (동일한 값의 순서 유지).
제자리 여부: 제자리 정렬 아님 (추가 공간 사용).

4. 버킷 정렬 (Bucket Sort)

원리

데이터를 여러 개의 버킷(bucket)에 분배하고, 각 버킷을 개별적으로 정렬한 뒤 병합하는 방식입니다.
주로 데이터가 균등하게 분포되어 있을 때 효과적입니다.

과정

입력 데이터의 최솟값과 최댓값을 기준으로 여러 개의 버킷을 생성합니다.
각 데이터를 해당하는 버킷에 분배합니다.
각 버킷 내부를 삽입 정렬이나 다른 알고리즘으로 개별적으로 정렬합니다.
모든 버킷을 병합하여 최종적으로 데이터를 완전히 정렬합니다.

특징

시간 복잡도:
- 평균: O(n+k), 여기서 k는 버킷 개수.
- 최악: O(n2) (데이터가 한 버킷에 몰릴 경우).
공간 복잡도: O(n+k) (버킷 저장 공간 필요).
안정성: 안정적 (동일한 값의 순서 유지).
제자리 여부: 제자리 정렬 아님 (추가 공간 사용).

'컴퓨터 > 알고리즘' 카테고리의 다른 글

3장 탐색 (3)	2025.01.03