버블 정렬(Bubble Sort)
정렬되는 모습이 마치 거품(버블)과 비슷하다고 붙여진 이름이다. 과정을 그림으로 보면 그 의미가 조금은 이해된다. 난이도는 쉬운편이며 이론을 먼저 정리했고, 그 다음에 구현해봤다.
버블 정렬 알고리즘은 정렬 알고리즘중에서 많이 언급되는 정렬 방법이다. 하지만 순차 탐색이자 완전 탐색의 방식이므로 크기가 큰 수열을 정렬하는데는 무리가 있다. 소요 시간은 마지막에 언급하겠지만 데이터의 크기가 작을 때 사용하는 것이 좋겠다.
#목차
(각 목차를 클릭하면 해당 내용을 바로 볼 수 있습니다.)
개발 환경
언어 : 코틀린(Kotlin)
IDE : IntelliJ IDE
이론
왼쪽에서부터(혹은 오른쪽에서부터) 두 개의 수를 비교하여 자리를 바꾸는 정렬 방법이다. 하나의 숫자가 다른 모든 숫자를 하나씩 검사해 나가는 것이다. 아래는 하나의 숫자에 대한 순회 과정이다.
수열 [5, 2, 3, 4, 1]을 정렬하는데, 첫 번째 0번 인덱스의 값 5가 제자리를 찾아가는 과정이며, 모든 숫자가 제자리를 찾을 때까지 반복한다.
Round 1.
정렬을 시작할 첫 번째 숫자가 나머지 숫자들과 비교한다. 배열의 시작 인덱스는 0부터이기 때문에, 0번째와 1번째 값을 비교한다. 그리고 자리를 바꾼다.
Round 2.
반복문에 의해 인덱스는 1이 증가하고, 이제 1번째와 2번째 값을 비교한다. 그리고 자리를 바꾼다.
Round 3.
인덱스는 다시 +1 되어, 2번째와 3번째 값을 비교한다. 그리고 자리를 바꾼다.
Round 4.
4번째 순회에서는 3번째와 4번째 값을 비교한다. 역시 숫자가 더 크기 때문에 자리를 바꾼다.
Round 5.
사실 5회차는 없다. 이미 4회차에서 정렬이 완료되기 때문에 실질적인 순회는 n-1회에 정렬이 끝난다.
전체 과정을 보면 이렇다. 이렇게 보면 어렴풋이 정렬과정이 거품이 이는 것처럼 보이긴 한다. 이런 순회를 5개 숫자 모두 정렬될 때까지 반복하게 된다.
코딩
이론을 알았다면, 이제 만들어봐야한다. 구현하지 못하면 무슨 의미가 있겠는가. 구글링을 해보면 생각보다 코틀린으로 구현한 내용이 많지 않았다. 그래서 코틀린으로 만들어 봤다.
하지만 버블 정렬에 대한 개념만 확실히 알고 있다면 어떤 프로그래밍 언어로도 구현할 수 있다고 생각한다.
Main()
fun main() {
//정렬이 필요한 배열
var arrNum = arrayListOf(5, 2, 3, 4, 1)
print("정렬되기 전 상태 :")
for (beforeSort in arrNum) {
print("${beforeSort}")
}
//정렬
sort(arrNum)
print("\n정렬된 상태 : ")
for (afterSort in arrNum) {
print("${afterSort}")
}
}
sort()
//오름차순으로 정렬
fun sort(arrNum: ArrayList<Int>) {
var temp = 0
for (i in arrNum) { //5회 반복한다.
//0 부터 3까지만 순회한다.
for (j in 0 until arrNum.size-1) {
//0>1, 1>2, 2>3, 3>4 비교
if (arrNum[j] > arrNum[j+1]) {
temp = arrNum[j]
arrNum[j] = arrNum[j+1]
arrNum[j+1] = temp
}
}
}
}
결과
결과
버블 정렬은 배열의 모든 요소를 확인하므로 완전 탐색이다. 하나의 값이 제자리를 찾아가려면 다른 모든 요소를 확인하는데 5개의 숫자를 정렬한 위의 예시와 같은 경우는 5 x 5 x 5 x 5 x 5 가 된다. 즉, 52이다.
따라서 버블 정렬에 소요되는 시간을 빅오(big O)표기법으로 표현하면 O(n2)이다.