[Kotlin] 버블 정렬 - Bubble Sort

🔷 버블 정렬 (Bubble Sort)이란?

[이미지 출처] https://www.programmingsimplified.com/c/source-code/c-program-bubble-sort

    거품이 터지면서 위로 올라오듯이 값을 하나씩 비교하며 올라오는 정렬이다.

    인접한 두 값을 비교하며 값을 정렬한다. 값을 비교하면서 정렬하기 때문에 '비교 정렬'이라고도 부른다.

    데이터를 정렬하기 위하여 추가적인 데이터가 필요하지 않기에 '제자리 정렬(in-place sort)'로 분류되기도 한다.

---

🔷 버블 정렬의 장점

🔹쉬운 난이도

    구현이 간단하다.

🔹적은 메모리

    정렬을 위하여 추가적인 메모리를 사용하지 않는다.

---

🔷 버블 정렬의 단점

🔹교환  낭비

    가장 큰 값이 가장 왼쪽에 있을 때 맨 끝으로 이동하기 위해서는 모든 값과 비교되어 올라가야한다.
    혹은, 가장 큰 값이 이미 맨 끝으로 정렬되어 있어도 교환을 확인하는 상황이 생길 수 있다.

---

🔷 시간 복잡도

🔹최악의 경우 :  O(n^2)

    n개를 입력했을 때, 최악의 경우 n*n번이 실행된다.

🔹최선의 경우 :  Ω(n^2)

    n개를 입력했을 때, 최선의 경우 n*n번이 실행된다.

---

🔷 구현

🔹코틀린 (Kotlin)

[이미지 출처] https://visualgo.net/en/sorting

fun main() {
	// 리스트 생성
    val bubbleList = mutableListOf<Int>(6, 5, 1, 2, 4, 3)
	
    // 위치 변경용 변수
    var temp = 0
    
	// 리스트 내부 반복
    for (i in bubbleList){
    	// 0부터 리스트-2까지 반복
        for (j in 0 until bubbleList.size-1){
        	// 앞, 뒤 데이터 비교 : 오름차순으로 정렬
            if (bubbleList[j] > bubbleList[j+1]){
            	temp = bubbleList[j]
                bubbleList[j] = bubbleList[j+1]
                bubbleList[j+1] = temp
            }
        }
    }
}