해당 포스트는 'R에서 버블 정렬(Bubble Sort)을 구현하는 방법'을 소개합니다.
INTRO
알고리즘(algorithms)을 배우기 시작하면 가장 먼저 접하는 것이 정렬 알고리즘(Sorting Algorithms) 종류입니다. 그 중에서도 버블 정렬(Bubble Sort)는 기초 단계로 구현이 간단하지만 정렬되지 않은 자료에 대해서는 성능이 좋지 않은 편에 속합니다.
알고리즘 학습 입문자 분들에게 성능은 아직 고려할 사항이 아니니 이번 포스트에서는 알고리즘의 방식을 이해하고 실제 구현을 통해 이해를 높여보셨으면 좋겠습니다.
버블 정렬(Bubble Sort)?
버블 정렬(Bubble Sort) 알고리즘은 입력 벡터의 이웃한 항목들이 원하는 순서가 아닐 때 그것들을 서로 교환함으로써 동작하는 정렬 방식으로, 더이상의 교환(Swap)이 필요하지 않을 때까지 반복하게 됩니다.
예를 들어, 4,3,2,1이라는 벡터를 버블 정렬(Bubble Sort)을 이용해 오름차순(increasing order)으로 정렬한다면 아래와 같이 절차로 정리됩니다.
- Input :
4,3,2,1 - 첫 번째 벡터
4를 이웃 벡터와 비교 및 자리 교환 :3,4,2,1 - 이동한 위치의
4를 이웃 벡터와 비교 및 자리 교환 :3,2,4,1 - 이동한 위치의
4를 이웃 벡터와 비교 및 자리 교환 :3,2,1,4
(4는 더이상 우측에 이웃이 없으므로 다음 스텝으로 넘어감) - 현재 첫번째 벡터
3을 이웃 벡터와 비교 및 자리 교환 :2,3,1,4 - 이동한 위치의
3을 잉수 벡터와 비교 및 자리 교환 :2,1,3,4
(우측 이웃의 값이 더 크므로 교환없이 다음 스텝으로 넘어감) - 현재 첫번째 벡터
2를 이웃 벡터와 비교 및 자리 교환 :1,2,3,4 - 전체 벡터의 정렬이 완료되어 정렬 종료
버블 정렬(Bubble Sort)에 대해 더욱 자세하게 알고 싶으시다면 아래 사이트를 참고해 보세요.
버블 정렬 함수 구현 (기본)
R에서 버블 정렬(Bubble Sort)를 이용해 오름차순(Increasing order)으로 정렬해 주는 함수는 아래와 같이 생성할 수 있습니다.
# Input: 2개 이상의 숫자형 벡터
bubble_sort <- function(x) {
swap_performed <- TRUE
# 더이상의 교환(swap)이 없을때까지 반복 수행
while (swap_performed) {
swap_performed <- FALSE
# 만약 교환(swap)이 필요하다면 아래 동작
for (i in 1:(length(x) - 1)) {
if (x[i] > x[i + 1]) {
# 오름차순 정렬이 되도록 벡터 위치 교환
tmp <- x[i]
x[i] <- x[i + 1]
x[i + 1] <- tmp
# 여기까지가 벡터의 위치 교환이 처리된 상황
# while 반복문 컨트롤을 위한 swap_performed 세팅
swap_performed <- TRUE
}
}
}
# Output: 오름차순으로 정렬된 벡터 출력
return(x)
}결과 테스트
1부터 10까지의 수들을 랜덤 추출하여 정렬되지 않은 숫자 벡터 x를 생성하고 위에서 생성한 bubble_sort() 함수로 버블 정렬을 수행하고 결과를 확인합니다. 위 과정을 총 4번 반복한 결과는 아래와 같습니다.
for (i in 1:4) {
x <- sample(1:10)
cat("\nInput: ", x, "\n")
cat("Output: ", bubble_sort(x), "\n")
}Input: 10 3 9 8 6 1 4 5 2 7 Output: 1 2 3 4 5 6 7 8 9 10 Input: 4 8 10 5 2 6 9 3 7 1 Output: 1 2 3 4 5 6 7 8 9 10 Input: 4 9 5 3 10 2 1 6 8 7 Output: 1 2 3 4 5 6 7 8 9 10 Input: 10 9 3 7 6 4 8 5 2 1 Output: 1 2 3 4 5 6 7 8 9 10
버블 정렬 함수 구현 (중간 상태 출력 방식)
위 결과를 보면 4번의 시도 모두 성공적으로 오름차순으로 정렬된 것을 볼 수 있습니다. 만약, 버블 정렬의 각 스텝(step) 별로 상태를 확인하고 싶다면 위에서 생성한 코드를 아래와 같이 수정하면 됩니다. (참고 : for 반복문 안에 출력을 위한 cat() 함수가 추가되었습니다.)
# Input: 2개 이상의 숫자형 벡터
bubble_sort <- function(x) {
swap_performed <- TRUE
# 더이상의 교환(swap)이 없을때까지 반복 수행
while (swap_performed) {
swap_performed <- FALSE
# 만약 교환(swap)이 필요하다면 아래 동작
for (i in 1:(length(x) - 1)) {
if (x[i] > x[i + 1]) {
# 오름차순 정렬이 되도록 벡터 위치 교환
tmp <- x[i]
x[i] <- x[i + 1]
x[i + 1] <- tmp
# 여기까지가 벡터의 위치 교환이 처리된 상황
# while 반복문 컨트롤을 위한 swap_performed 세팅
swap_performed <- TRUE
# 정렬중인 벡터의 현재 상태를 출력
cat("Current state: ", x, "\n")
}
}
}
# Output: 오름차순으로 정렬된 벡터 출력
return(x)
}결과 테스트
반복문안에 cat() 함수를 추가하여 버블 정렬(Bubble Sort)의 진행 상황(Progress)을 확인하면 아래와 같이 출력됩니다.
bubble_sort(c(1, 3, 5, 2, 4, 6))Current state: 1 3 2 5 4 6 Current state: 1 3 2 4 5 6 Current state: 1 2 3 4 5 6 [1] 1 2 3 4 5 6
마무리
이번 포스트에서는 정렬 알고리즘(Sorting Algorithms)의 하나인 버블 정렬(Bubble Sort) 함수를 구현하고 결과를 확인하였습니다. 성능이 좋은 정렬 알고리즘은 아니지만 알고리즘 구현의 입문 단계로 동작 가능한 정렬 함수를 만들어보고 이해도를 높이는데 도움이 되셨으면 좋겠습니다.
관련 링크
[1] [R-Bloggers] How to write bubble sort in R
[2] [나무위키] 정렬 알고리즘
