[Algorithm] 거품 정렬(Bubble Sort) .01

알고리즘의 첫 장입니다.

먼저 알아볼 알고리즘은 거품 정렬(Bubble Sort)입니다.

이 알고리즘은 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘입니다.

이름의 유래는 정렬 과정에서 원소의 이동이 마치 거품이 수면 위로 올라 오는 듯한 모습을 보이기 때문이라고 합니다.

 왜 거품처럼 안보이는거지..

 

🤔 과정 및 코드

첫 회전에서 첫번째 원소와 두번째 원소 비교를, 두번째 원소와 세번째 원소 비교 이렇게 쭉 해나가서 결국 마지막엔 가장 큰 원소가 맨 뒤로 가게 되고, 해당 회전을 반복하면 큰 순으로 뒤에서 부터 정리 됩니다.

 

📝 Python 예시 코드.

def Bubble_Sort(arr):
    for i in range(0, len(arr)):
        for j in range(1, len(arr)-i):
            if arr[j-1] > arr[j]:
                temp = arr[j-1]
                arr[j-1] = arr[j]
                arr[j] = temp
    return arr

🕒 시간 복잡도.

시간 복잡도를 단순하게 계산하자면 배열 arr을 처음부터 끝까지 겹쳐서 두 번 사용합니다. arr^2가 되죠.

정확하게 계산하면 (n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2이므로, O(n^2) 시간 복잡도를 가집니다.

 

💾 공간 복잡도.

주어진 배열 안에서 움직이기 때문에  O(n) 입니다.

 

✋ 장점과 단점.

장점.

구현이 쉽고, 코드가 직관적이다.

배열 안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다. (제자리정렬 - in-place sorting)

 

단점.

최악,최선,평균 어느 상황에서나 O(n^2) 시간 복잡도를 가진다.

정렬 되어 있지 않은 원소가 정렬될 때 많은 자리 이동이 일어난다.

 

참조.

GimunLee/tech-refrigerator