모두의 알고리즘 문제11. 퀵 정렬 연습 문제

11-1 거품정렬 과정을 알고리즘으로 적어보라

 

def bubble_sort(a):
    n=len(a)
    while 1:
        change=False
        for i in range(0, n-1):
            if a[i] > a[i+1]:
                a[i], a[i+1] = a[i+1], a[i]
                change=True
        if change==False: return
    

d=[2, 4, 5, 1, 3, 9, 11, 22, 7, 2]
bubble_sort(d)
print(d)

결과: [1, 2, 2, 3, 4, 5, 7, 9, 11, 22]

 

 

처음엔 재귀함수를 써야하나 했는데 생각해보니 반복문으로 충분하겠더라.

 

첫 시도에선 while문 탈출 조건을 True/False가 아니라 변수 하나에 0을 저장하고 앞뒤 값이 바뀌지 않을때마다 변수에 1을 더해서 값이 n-1이었나 n-2가 되면 탈출하는 식으로 했는데 뭐가 문제인지 전부 정렬되기 전에 루프가 끝나버렸다.

 

그래서 T/F 방식으로 했는데 이게 훨씬 편한 것 같다. 설령 상술한대로 변수에 1 더하는식으로 체크한게 성공햇다고 해도 T/F방식이 더 효율적이고 머리도 편할 거 같다.

 

거품정렬의 시간복잡도는 최선의 경우에, 즉 이미 자료가 정돈되어있는 경우에는 O(n)이다.

 

일반적인 경우에는 O(n^2)이다. 하지만 거품정렬은 자료 위치를 서로 바꾸는 횟수가 선택 정렬이나 삽입 정렬보다 더 많기 때문에 실제로 더 느리게 동작한다는 단점이 있다.