거품 정렬(Bubble Sort)

📍거품 정렬(Bubble Sort)

시간복잡도 : O(n^2)
공간복잡도 : O(n) -> 주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되기때문

거품 정렬은 선택 정렬과 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다.

이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다.

아래는 버블 정렬의 코드 예시이다.

function bubbleSort(array) {
	for(i in array) {
    	for(i in array) {
    		if(array[i] < array[j]){
            swap(array, i, j);
            }
        }
    }
    return array;
}

bubbleSort([6,1,2,3,4,5])
/결과 : [1,2,3,4,5,6]

장점 
- 구현이 간단하고, 소스코드가 직관적이다.
- 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬(in-place sorting)
- 안정 정력(Stable Sort)

단점
- 시간 복잡도가 최악의 종류의 정렬이다. 다른 정렬 알고리즘은 배열의 이미 정렬된 부분을 활용하는데 비해 거품 정렬은 모든 가능한 짝을 비교하기 때문이다.