[핵심] 컴퓨터공학개론 9단원 – 자료구조와 알고리즘: 정렬(Sorting)

9단원 – 자료구조와 알고리즘: 정렬(Sorting)

1. 정렬이란?

정렬(Sorting)이란, 주어진 데이터를 일정한 기준(오름차순, 내림차순 등)에 따라 순서를 재배열하는 작업을 의미한다. 다양한 알고리즘이 존재하며, 시간 복잡도와 공간 복잡도, 안정성 등에 따라 각각의 특징이 있다.

정렬은 검색, 데이터 분석, 시각화 등 다양한 응용 분야에서 필수적인 전처리 단계이다.

---

2. 정렬 알고리즘 분류

정렬 방식내부/외부정렬 기준특징

버블 정렬	내부 정렬	인접 비교	가장 단순, 느림
선택 정렬	내부 정렬	최소값 선택	데이터 이동 적음
삽입 정렬	내부 정렬	위치 삽입	거의 정렬된 경우 효율적
퀵 정렬	내부 정렬	피벗 기반	평균 속도 빠름, 불안정
병합 정렬	내부 정렬	분할 후 병합	안정적, 추가 메모리 사용
힙 정렬	내부 정렬	힙 자료구조	빠르고 메모리 효율적
기수 정렬	외부 정렬	자릿수 기준	숫자나 문자열 정렬에 강점

 

---

3. 주요 정렬 알고리즘 설명

① 버블 정렬 (Bubble Sort)

• 인접한 두 값을 비교하여 위치를 바꾸는 방식
• 반복문을 통해 가장 큰 값을 끝으로 보내는 구조
• 시간 복잡도: O(n²)
• 코드 예시 (Python):

for i in range(len(arr)):
    for j in range(len(arr)-i-1):
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]

---

② 선택 정렬 (Selection Sort)

• 매 반복마다 최소값을 찾아 맨 앞으로 이동
• 교환 횟수 적음 (n번)
• 시간 복잡도: O(n²)

---

③ 삽입 정렬 (Insertion Sort)

• 정렬된 리스트에 새로운 요소를 삽입하면서 정렬
• 거의 정렬된 데이터에 매우 빠름
• 시간 복잡도: O(n²)

---

④ 퀵 정렬 (Quick Sort)

• 피벗을 기준으로 좌우로 분할하며 정렬
• 평균 시간 복잡도: O(n log n)
• 최악의 경우: O(n²) (데이터가 이미 정렬된 경우)

---

⑤ 병합 정렬 (Merge Sort)

• 데이터를 반으로 나누고 다시 합치며 정렬
• 안정 정렬
• 시간 복잡도: O(n log n)
• 공간 복잡도: O(n) (임시 배열 필요)

---

⑥ 힙 정렬 (Heap Sort)

• 최대 힙 또는 최소 힙을 사용하여 정렬
• 시간 복잡도: O(n log n)
• 불안정 정렬

---

⑦ 기수 정렬 (Radix Sort)

• 자릿수를 기준으로 정렬
• 비교 기반 아님 → 문자열, 숫자에 강점
• 시간 복잡도: O(kn) (k = 자릿수)

---

4. 정렬 알고리즘 비교 요약

알고리즘평균 시간 복잡도공간 복잡도안정성특징

버블 정렬	O(n²)	O(1)	O	구현 쉬움, 매우 느림
선택 정렬	O(n²)	O(1)	X	교환 적음
삽입 정렬	O(n²)	O(1)	O	거의 정렬된 경우 효율적
퀵 정렬	O(n log n)	O(log n)	X	평균 매우 빠름
병합 정렬	O(n log n)	O(n)	O	안정적, 메모리 사용
힙 정렬	O(n log n)	O(1)	X	공간 효율적
기수 정렬	O(kn)	O(n+k)	O	숫자, 문자열 특화

 

---

5. 실습 예시 (퀵 정렬)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = [x for x in arr[1:] if x <= pivot]
    right = [x for x in arr[1:] if x > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

nums = [5, 3, 8, 4, 2]
print(quick_sort(nums))

---

6. 학습 포인트 요약

• 정렬은 알고리즘의 기초 중의 기초로, 모든 문제 해결의 출발점이다.
• 다양한 정렬 방식의 특징과 시간 복잡도, 안정성을 이해해야 한다.
• 실제 문제 풀이에서는 입력 데이터의 특성에 따라 정렬 알고리즘을 적절히 선택해야 한다.
• 정렬은 코딩 테스트, 면접, 실무 데이터 처리 등 모든 개발 과정에서 활용된다.