목표
버블 정렬(Bubble Sort)을 구현하여 배열 안의 숫자를 오름차순으로 정렬하는 알고리즘을 블루프린트로 작성.
1. 버블 정렬 개요
-
정의:
- 버블 정렬은 두 개의 인접한 값을 비교하여 정렬하는 간단한 알고리즘.
- 가장 큰 값이 배열 끝으로 "버블"처럼 떠오르게 된다.
-
동작 원리:
- 첫 번째 반복: 배열의 처음부터 끝까지, 인접한 두 값을 비교하고 교환(Swap).
- 두 번째 반복: 끝에서 두 번째 값까지만 비교 (맨 끝 값은 이미 정렬).
- 반복 횟수는 배열 길이에 따라 줄어든다.
2. 블루프린트 구조 분석
A. 한 턴 구현
-
For Loop:
First Index: 0.Last Index: 배열의 길이 - 2.- 배열의 길이에서 2를 빼는 이유는 현재 인덱스와 그다음 인덱스를 비교해야 하므로, 마지막 인덱스를 넘어갈 수 없게 제한.
-
Get 노드:
- 현재 인덱스 값과 다음 인덱스 값을 가져옴.
-
Branch (조건문):
- 현재 값이 다음 값보다 큰지 비교.
- 조건이 참(True)인 경우에만 교환(Swap)을 실행.
-
Swap 노드:
- 두 값을 교환하여 배열 내 순서를 정렬.
B. 전체 반복 구현
-
외부 For Loop:
First Index: 0.Last Index: 배열의 길이 - 1.- 배열 전체를 정렬하기 위해 반복.
-
내부 For Loop:
- 반복 범위를 하나씩 줄임:
- 첫 번째 반복: 배열의 끝까지 비교.
- 두 번째 반복: 배열의 끝 - 1까지 비교.
- 이런 방식으로 점점 비교 범위를 줄여 효율적으로 정렬.
- 반복 범위를 하나씩 줄임:
3. 디버깅 및 과정 분석
초기 상태
- 배열
{ 5, 1, 9, 7, 2, 3 }이 주어짐. - 아직 정렬되지 않은 상태.
첫 번째 반복 결과
-
첫 번째 비교 (5와 1):
- 조건: 5 > 1 (참).
- Swap 실행 →
{ 1, 5, 9, 7, 2, 3 }.
-
두 번째 비교 (5와 9):
- 조건: 5 > 9 (거짓).
- Swap 실행 안 됨 →
{ 1, 5, 9, 7, 2, 3 }.
-
이후 비교:
- 9와 7 → Swap 실행 →
{ 1, 5, 7, 9, 2, 3 }. - 9와 2 → Swap 실행 →
{ 1, 5, 7, 2, 9, 3 }. - 9와 3 → Swap 실행 →
{ 1, 5, 7, 2, 3, 9 }.
- 9와 7 → Swap 실행 →
두 번째 반복 결과
-
첫 번째 비교 (1과 5):
- 조건: 1 > 5 (거짓).
- Swap 실행 안 됨 →
{ 1, 5, 7, 2, 3, 9 }.
-
이후 비교:
- 7과 2 → Swap 실행 →
{ 1, 5, 2, 7, 3, 9 }. - 7과 3 → Swap 실행 →
{ 1, 5, 2, 3, 7, 9 }.
- 7과 2 → Swap 실행 →
최종 결과
- 배열
{ 1, 2, 3, 5, 7, 9 }로 정렬 완료.
4. 코드 최적화
문제점
- 내부 For Loop에서 이미 정렬된 배열을 계속 비교.
- 불필요한 연산이 발생.
해결 방법
- 내부 For Loop의
Last Index를 반복 횟수마다 1씩 줄임. - 정렬된 값은 비교에서 제외하여 연산 최적화.
결과
- 배열 길이가 커질수록 실행 속도 향상.
5. Swap 노드 역할
- Swap은 두 인덱스의 값을 교환하는 핵심 역할.
- 배열에서 특정 인덱스를 직접 접근하여 값을 바꿔줌.
6. 블루프린트 실행 흐름
-
BubbleSort 이벤트:
- 정렬 시작.
-
외부 For Loop:
- 배열 전체를 반복.
-
내부 For Loop:
- 인접한 값을 비교하여 정렬.
-
Branch 조건문:
- 현재 값이 다음 값보다 큰 경우에만 Swap 실행.
-
Swap 노드:
- 두 값을 교환하여 정렬.
7. 장점과 단점
장점
- 구현이 간단하고 직관적.
- 소규모 배열 정렬에 적합.
단점
- 시간 복잡도가 (O(n^2))으로 비효율적.
- 대규모 배열에 사용 시 성능 저하.
李家네_공부방