정렬 알고리즘(정보처리기사)

정렬 알고리즘 정리

버블 정렬(Bubble Sort)

버블 정렬은 인접한 두 요소를 비교하여 정렬하는 가장 기본적인 정렬 알고리즘이다. 가장 큰(또는 작은) 값을 한 번의 반복을 통해 리스트의 끝으로 이동시키는 과정을 반복하여 정렬을 수행한다.

버블 정렬의 동작 방식

1. 배열의 첫 번째 요소부터 인접한 두 요소를 비교한다.
2. 두 요소의 순서가 잘못되었으면 교환한다.
3. 한 번의 반복이 끝나면 가장 큰(또는 작은) 값이 리스트의 끝으로 이동한다.

위 과정을 배열이 완전히 정렬될 때까지 반복한다.

시간 복잡도 쉽게 이해하기

• 최선(O(n)): 데이터가 이미 정렬되어 있을 때는 한 번만 확인하면 끝난다.
• 평균(O(n²)): 대부분의 경우 여러 번 비교하고 교환해야 하므로 시간이 오래 걸린다.
• 최악(O(n²)): 데이터가 완전히 뒤죽박죽이면 가장 많은 비교와 교환이 필요하다.

---

선택 정렬(Selection Sort)

선택 정렬은 리스트에서 가장 작은(또는 큰) 값을 찾아 앞쪽으로 이동시키는 방식으로 동작하는 정렬 알고리즘이다.

선택 정렬의 동작 방식

1. 리스트에서 가장 작은 값을 찾아 첫 번째 요소와 교환한다.
2. 두 번째 요소부터 다시 가장 작은 값을 찾아 교환한다.
3. 이를 반복하여 전체 리스트를 정렬한다.

시간 복잡도 쉽게 이해하기

• 최선(O(n²)): 정렬이 되어 있어도 모든 요소를 비교해야 하므로 최선도 O(n²)이다.
• 평균(O(n²)): 항상 최소값을 찾아야 하므로 비교가 많이 필요하다.
• 최악(O(n²)): 정렬이 안 되어 있어도 항상 O(n²) 시간이 걸린다.

---

삽입 정렬(Insertion Sort)

삽입 정렬은 각 요소를 올바른 위치에 삽입하여 정렬하는 방식으로 동작하는 알고리즘이다.

삽입 정렬의 동작 방식

1. 두 번째 요소부터 시작하여 앞쪽 요소들과 비교한다.
2. 삽입할 위치를 찾아 값을 이동시킨다.
3. 이를 반복하여 전체 리스트를 정렬한다.

시간 복잡도 쉽게 이해하기

• 최선(O(n)): 데이터가 거의 정렬되어 있다면 한 번씩만 비교하면 된다.
• 평균(O(n²)): 대부분의 경우 여러 번 삽입해야 하므로 시간이 걸린다.
• 최악(O(n²)): 데이터가 완전히 반대로 되어 있다면 가장 많이 이동해야 한다.

---

정렬 알고리즘 비교 (쉽게 이해하기)

알고리즘 종류	최선 (빠를때)	평균 (보통)	최악 (느릴 때)	추가 메모리 사용
버블 정렬	빠름 (O(n)) - 거의 정렬된 경우	느림 (O(n²)) - 여러 번 비교해야 함	아주 느림 (O(n²)) - 반대로 정렬된 경우	적음 (O(1))
선택 정렬	느림 (O(n²)) - 항상 비교가 필요함	느림 (O(n²))	느림 (O(n²))	적음 (O(1))
삽입 정렬	빠름 (O(n)) - 거의 정렬된 경우	보통 (O(n²))	느림 (O(n²))	적음 (O(1))

---

결론 (정렬 알고리즘 선택하는 방법)

• 데이터가 거의 정렬된 상태라면? → 삽입 정렬이 가장 빠르다.
• 데이터 크기가 작고 간단한 정렬이 필요하면? → 선택 정렬도 괜찮다.
• 정렬을 이해하는 연습용으로는? → 버블 정렬이 쉽다.

 

버블 정렬 예제 문제

문제: 다음 리스트가 버블 정렬의 Pass 1을 거친 후의 상태는?

입력 배열:

4, 7, 3, 1, 5, 8, 2, 6

버블 정렬 Pass 1 과정:

1. (4,7) → 그대로 둠
2. (7,3) → 교환 → 4, 3, 7, 1, 5, 8, 2, 6
3. (7,1) → 교환 → 4, 3, 1, 7, 5, 8, 2, 6
4. (7,5) → 교환 → 4, 3, 1, 5, 7, 8, 2, 6
5. (7,8) → 그대로 둠
6. (8,2) → 교환 → 4, 3, 1, 5, 7, 2, 8, 6
7. (8,6) → 교환 → 4, 3, 1, 5, 7, 2, 6, 8

Pass 1 결과:

4, 3, 1, 5, 7, 2, 6, 8

정답: ③ 4, 3, 1, 5, 7, 2, 6, 8

---

선택 정렬 예제 문제

문제: 다음 리스트가 선택 정렬의 Pass 1을 거친 후의 상태는?

입력 배열:

5, 3, 8, 4, 2

선택 정렬 Pass 1 과정:

1. 전체 배열에서 가장 작은 값 2를 찾음
2. 2와 첫 번째 요소 5를 교환 → 2, 3, 8, 4, 5

Pass 1 결과:

2, 3, 8, 4, 5

정답: ① 2, 3, 8, 4, 5

---

삽입 정렬 예제 문제

문제: 다음 리스트가 삽입 정렬의 Pass 1을 거친 후의 상태는?

입력 배열:

5, 3, 8, 4, 2

삽입 정렬 Pass 1 과정:

1. 두 번째 요소 3을 첫 번째 요소 5와 비교
2. 3이 더 작으므로 5를 뒤로 이동시키고 3을 삽입 → 3, 5, 8, 4, 2

Pass 1 결과:

3, 5, 8, 4, 2

정답: ② 3, 5, 8, 4, 2

---

결론

• 버블 정렬은 Pass 1에서 가장 큰 값이 오른쪽으로 이동함
• 선택 정렬은 Pass 1에서 가장 작은 값을 찾아 첫 번째 자리로 이동함
• 삽입 정렬은 Pass 1에서 두 번째 요소를 적절한 위치에 삽입함