정보처리기사 실기 - 정렬(삽입, 선택, 버블, 쉘, 퀵, 힙, 2-Way, 기수)

정렬(Sort)

주어진 데이터(레코드, 배열 등)를 특정 기준(오름차순·내림차순 등)에 따라 순서대로 재배열하는 과정

정렬은 알고리즘의 기본 중 기본으로,
데이터 탐색이나 분석을 효율적으로 하기 위해 꼭 필요한 과정

---

삽입 정렬(Insertion Sort)

• 이미 정렬된 부분에 새로운 데이터를 순서에 맞게 삽입하여 정렬하는 방식
• 두 번째 원소부터 시작 → 앞의 정렬된 구간과 비교하여 적절한 위치에 삽입
• 구현이 단순하고 직관적
• 데이터가 거의 정렬되어 있으면 빠름
• 자료 이동이 많음
• 평균과 최악 수행 시간 복잡도 : O(n²)

---

선택 정렬(Selection Sort)

• 전체 원소 중 가장 작은 값(최소값)을 찾아 맨 앞자리로 보내는 과정을 반복
• 1회전 : 최소값 → 첫 번째 위치
  2회전 : 두 번째 최소값 → 두 번째 위치
• 교환 횟수가 최소화됨
• 자료 이동은 적지만, 비교 횟수 많음
• 평균과 최악 수행 시간 복잡도 : O(n²)

---

버블 정렬(Bubble Sort)

• 인접한 두 원소를 비교해 큰 값을 뒤로 보내는 방식
• 1회전마다 가장 큰 값이 맨 뒤로 이동
• 구현 간단
• 비교 및 교환이 많아 비효율적
• 평균과 최악 수행 시간 복잡도 : O(n²)

---

쉘 정렬(Shell Sort)

• 삽입 정렬을 개선한 방법
• 일정 간격으로 떨어진 원소끼리 부분 정렬을 수행
• 전체 데이터를 여러 개의 부분 리스트로 나누어 각 리스트를 삽입 정렬로 처리 후, 간격을 줄여가며 반복
• 삽입 정렬의 개선형
• 데이터 이동이 적고 평균적으로 빠름
• 간격 선택에 따라 효율성 달라짐
• 평균 수행 시간 복잡도 : O(n¹·⁵)
• 최악 수행 시간 복잡도 : O(n²)

---

퀵 정렬(Quick Sort)

• 기준값(Pivot)을 중심으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하여 정렬하는 분할 정복 방식
• 원리
  1. Pivot 선택
  2. Pivot 기준으로 좌/우 분할
  3. 각각 재귀적으로 정렬
• 평균적으로 매우 빠름
• 정렬 중간에 원소 교환만 수행 → 추가 공간 적음
• 평균 수행 시간 복잡도 : O(n log n)
• 최악 수행 시간 복잡도 : O(n²)

---

힙 정렬(Heap Sort)

• 완전 이진 트리 형태의 힙(Heap) 자료 구조를 이용한 정렬
• 최대 힙 : 루트가 가장 큰 값
• 루트 제거 후 마지막 노드와 교환 → 재정렬 반복
• 정렬 중에 추가 메모리 불필요
• 항상 일정한 수행 시간 보장
• 평균과 최악 수행 시간 복잡도 : O(n log n)

---

2-Way 합병 정렬(Merge Sort)

• 이미 정렬된 두 개의 리스트를 하나로 합치는 과정을 반복하는 정렬
• 원리
  1. 리스트를 반으로 분할
  2. 각각 정렬 후 합병
  3. 병합 과정에서 항상 순서 유지
• 평균과 최악 수행 시간 복잡도 :  O(n log n)

---

기수 정렬(Radix Sort, = Bucket Sort)

• 자릿수(Digit)를 기준으로 낮은 자릿수부터 차례로 정렬하는 방식
• 각 자릿수에 따라 버킷에 분배 후, 버킷 순서대로 다시 수집
• 비교 연산을 수행하지 않음
• 키 값이 일정 범위일 때 매우 효율적
• 정렬 속도가 일정함
• 평균과 최악 수행 시간 복잡도 : O(dn)

---