7. Sorting (1)

Sorting

: 데이터를 특정 기준에 따라 순서대로 배치하는 과정

검색 효율을 높이거나 데이터 분석 전 처리 과정에서 자주 사용됨.

---

1. Bubble Sort (버블 정렬)

인접한 두 원소를 비교해 큰 값을 뒤로(또는 작은 값을 앞으로) 반복적으로 이동시켜서 정렬함. 한 번의 전체 패스(pass)를 돌면 가장 큰(또는 작은) 값이 끝으로 확정됨 → “거품이 올라오는” 모습에서 이름 유래.

 

과정 (예: [5, 2, 4, 1])

[5, 2, 4, 1] 패스1:	비교(5,2)	swap	[2,5,4,1]
	비교(5,4)	swap	[2,4,5,1]
	비교(5,1)	swap	[2,4,1,5]  (가장 큰 5가 끝에 위치)
[2,4,1,5]  패스2:	비교(2,4)	no swap	[2,4,1,5]
	비교(4,1)	swap	[2,1,4,5]
패스3:	비교(2,1)	swap	[1,2,4,5]
패스4:	[1,2,4,5]	이미 정렬됨, 종료

 

특징

• 한 번의 순회가 끝날 때마다 가장 큰 값이 맨 끝에 고정됨
• 총 n-1번 반복
• 최적화: 더 이상 교환이 없을 경우 반복 종료 가능
• 안정성 높으나 데이터가 클 경우 비효율적임.

시간복잡도

• 최악: O(n²)
• 평균: O(n²)
• 최선: O(n) (이미 정렬된 경우)

비교 및 교환 횟수

• 비교: n(n-1)/2
• 교환: 많음 (효율 낮음)

 

코드)

for i = 0 to n-2:
  for j = 0 to n-2-i:
    if A[j] > A[j+1]: swap(A[j], A[j+1])

 

최적화 (Early exit)

한 패스에서 swap이 없으면 이미 정렬된 상태이므로 종료하도록 설정하기

void bubbleSort(int a[], int n) {
    int i, j, temp;
    int swapped; // 교환 여부 플래그

    for (i = 0; i < n - 1; i++) {
        swapped = 0; // 이번 패스에서 교환이 있었는지 체크
        for (j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                swapped = 1;
            }
        }
        if (swapped == 0) break; // 교환이 없으면 종료
    }
}

---

2. Selection Sort (선택 정렬)

 : 매 단계에서 남은 원소들 중 최소(또는 최대)를 찾아서 정해진 위치로 옮김.

 선택 과정은 전체 남은 부분을 스캔해야 함.

과정 (예: [5, 2, 4, 1])

단계	최소 숫자	동작
i = 0	1	swap A[0], A[index(1)] → [1,2,4,5]
i = 1	2	이미 제자리에 있음
i = 2	4	이미 제자리에 있음

 

특징

• 한 번의 순회가 끝날 때마다 가장 큰 값이 맨 끝에 고정됨
• 총 n-1번 반복
• 최적화: 더 이상 교환이 없을 경우 반복 종료 가능
• 안정성 높으나 데이터가 클 경우 비효율적임.

시간복잡도

• 최선, 최악 평균 모두 : O(n²)
• 평균: O(n²)
• 최선: O(n) (이미 정렬된 경우)

비교 및 교환 횟수

• 비교: n(n-1)/2
• 교환: 많음 (효율 낮음)

 

특징

• 정렬된 부분과 정렬되지 않은 부분으로 나뉨
• 매번 최솟값을 찾아서 왼쪽으로 보냄
• 일반적으로는 퀵/힙/병합 정렬에 비해 느림.
• 불안정(unstable) — 동일한 값이 있을 때 상대 순서가 바뀔 수 있음(최솟값을 swap할 때).

시간 ·공간 복잡도

• 최선, 최악 평균 모두 : O(n²)
• 항상 전체를 순회해야 하므로 상황에 관계없이 동일함
• 공간: O(1) (in-place)

비교 및 교환 횟수

• 교환(swap) 횟수가 O(n)으로 적음(매 단계 1번 swap)
• == 메모리 교체 비용이 높은 상황에 유리할 때 생각해볼 수 있음

코드)

for i = 0 to n-2:
  minIdx = i
  for j = i+1 to n-1:
    if A[j] < A[minIdx]: minIdx = j
  swap(A[i], A[minIdx])

---

3. Insertion Sort (삽입 정렬)

: 배열을 정렬된 부분과 비정렬된 부분으로 나누고, 비정렬된 원소를 하나씩 꺼내 적절한 위치에 삽입함

카드로 손의 패를 정렬하는 과정과 유사.

 

과정 (예: [5, 2, 4, 1])

단계	key	동작
i = 1	2	비교 5>2 → shift → [_,5,4,1], insert 2 → [2,5,4,1]
i = 2	4	비교 5>4 → shift → [2,_,5,1], insert 4 → [2,4,5,1]
i = 3	1	shift 5,4,2 → [_,2,4,5], insert 1 → [1,2,4,5]

 

특징

• 데이터가 거의 정렬된 상태일 때 매우 빠름
• 실제로 많은 정렬 알고리즘의 내부에서 사용됨 (ex. QuickSort의 작은 구간 정렬)
• 안정적(stable) — 같은 값이 들어오면 원래 순서 유지
• Binary insertion: 삽입 위치를 이진 검색으로 찾으면 비교 횟수는 줄지만, 이동(shift)은 여전히 O(n) → 전체 O(n²) 유지.
• 작은 배열 최적화: 퀵/병합 정렬과 함께 작은 청크(예: 길이 ≤ 16)는 삽입 정렬로 처리하는 것이 빠름.

시간 ·공간 복잡도

• 시간: 최악 O(n²), 평균 O(n²), 최선 O(n) (이미 정렬된 경우, 비교만 O(n))
• 공간: O(1) (in-place)

 

코드)

for i = 1 to n-1:
  key = A[i]
  j = i-1
  while j >= 0 and A[j] > key:
    A[j+1] = A[j]   // shift
    j = j-1
  A[j+1] = key

---

4. Quick Sort (퀵 정렬) — 개념 및 O(n²) 관련 설명

하나의 피벗(pivot) 을 선택하고, 배열을 피벗보다 작거나 같은 것 왼쪽, 큰 것 오른쪽으로 분할(partition) 한다. 그런 다음 좌우 부분 배열을 재귀적으로 정렬함. 분할이 균형 잡히면 O(n log n), 매우 치우치면 O(n²).

 

1. 기준이 되는 pivot 값을 선택함
2. pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할
3. 분할된 부분 배열에 대해 재귀적으로 동일 과정 수행

 

 

과정 (예: [5, 2, 4, 1])

pivot = 2

왼쪽 [1], 오른쪽 [4, 5]

[1] + [2] + [4, 5]

 

특징

• 비교적 빠른 정렬 알고리즘
• 분할 정복(Divide and Conquer) 기반
• 재귀적 접근
• 피벗 선택이 성능에 큰 영향을 줌
• 일반 구현은 불안정(unstable)

피벗 선택 전략(성능에 큰 영향)

• 항상 첫/마지막 원소: 이미 정렬된 데이터에서 최악(편향) 발생 → O(n²)
• 중앙값(median-of-three): 세 요소(첫, 중간, 마지막)의 중앙값 선택 → 편향 완화
• 랜덤 피벗: 무작위 선택 → 평균적으로 O(n log n), 최악 확률 낮춤
• median of medians: 이론상 좋은 중간값 선택(복잡도 높음)

시간 ·공간 복잡도

• 평균: O(n log n)
• 최악: O(n²) (이미 정렬되었거나 편향된 피벗 선택)
• 공간: 평균 O(log n) 재귀 깊이(스택), 최악 O(n) (편향시)

 

코드)

quickSort(a, left, right) {
  if (left < right) {
    pivot = a[left];
    i = left; j = right + 1;
    do {
      do i++; while (a[i] < pivot);
      do j--; while (a[j] > pivot);
      if (i < j) swap(a[i], a[j]);
    } while (i < j);
    swap(a[left], a[j]);
    quickSort(a, left, j-1);
    quickSort(a, j+1, right);
  }
}

---

정리하자면

알고리즘	최선	평균	최악	특징
Bubble Sort	O(n)	O(n²)	O(n²)	구현 쉬움, 교환 많음
Selection Sort	O(n²)	O(n²)	O(n²)	교환 적음, 느림
Insertion Sort	O(n)	O(n²)	O(n²)	거의 정렬된 데이터에 빠름
Quick Sort	O(n log n)	O(n log n)	O(n²)	평균적으로 가장 빠름