#01 거품정렬 (bubble sort)

arr = [6,8,3,1,5,4,9,0,2,7]

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

def improved_bubblesort(arr):
    end_index = len(arr)-1
    while end_index > 0 :
        swap = 0
        for i in range(end_index):
            if arr[i] > arr[i+1] :
                arr[i], arr[i+1] = arr[i+1], arr[i]
                swap = i
        end_index = swap
    return arr

- 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 변경

https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html

최선 평균 최악 모두 O(n^2) 

개선된 거품정렬은 최선 O(n) , 최악 O(n^2), 평균은 O(nlogn ~ n^2)일 것같다.(절반만 정렬되어 있을 경우) n마다 logn개만큼 반복

 

공간복잡도는 주어진 배열안에서 교환을 통해 정렬되므로 O(n)

 

장점 : 구현이 간단, 직관적, 다른 메모리 공간을 필요로 하지 않음, 안정 정렬 (정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지되느냐 yes)

단점 : 비효율적인 알고리즘 , 교환 연산이 많이 일어남