[알고리즘] 버블정렬(w/python)

---

개념

앞의 항과, 바로 뒤의 항 단 두 항만을 비교한다.

앞의 숫자보다 뒤의 숫자가 더 작다면 서로를 바꾼다.

 

아래의 배열을 버블정렬로 오름차순 정렬 해보자.

1. 인덱스 0과 1의 숫자들을 우선 비교한다.

8보다 3이 더 크므로, 둘을 바꾼다.

 

2. 인덱스 1과 2의 숫자들을 비교한다. 

8보다 2가 더 크므로, 둘을 바꾼다.

 

3. 인덱스 2와 3의 숫자들을 비교한다.

8보다 7이 더 크므로, 둘을 바꾼다.

 

4. 마지막으로 인덱스 3과 4의 숫자들을 비교한다.

8보다 6이 더 크므로, 둘을 바꾼다.

 

첫번째 턴을 다 돌았다. 그러나 정렬되지 않았다.

이렇게 턴을 총 인덱스 - 1번만큼 돈다.

 

끝까지 가면 네번 돌아야 하지만 다 정렬 돼 버렸다.

 

---

구현

 

lists = [8, 3, 2, 7, 6]
for i in range(len(lists) - 1):
    for j in range(len(lists) - 1):
        if lists[j] > lists[j + 1]:
            lists[j], lists[j + 1] = lists[j + 1], lists[j]
print(lists)

위의 코드로 구현해도 충분히 답은 구해낼 수 있다.

하지만 이미 lists가 정렬이 된 상태라면?

아니면 len(lists) - 1번째까지 가지 않아도 정렬이 될 수 있다면?

굳이 꽉꽉 채워 루프를 도는 것은 낭비일것이다.

 

그렇기에, 한번을 다 돌았을 때, 한번도 숫자 교환을 하지 않았다면 그것이 곧 정렬이 된 상태임을 알게 되는 것이다.

이를 체크하기 위해 isChanged라는 불리언 변수를 넣어주자.

 

lists = [8, 3, 2, 7, 6]
isChanged = False
for i in range(len(lists) - 1):
    # 한번 턴 도는 주기
    for j in range(len(lists) - 1):
        if lists[j] > lists[j + 1]:
            lists[j], lists[j + 1] = lists[j + 1], lists[j]
            # 교환 했으니 True로
            isChanged = True
    # 한번 턴 돌았을 때 changed 했다면 정렬 될 때 까지 다시 턴
    # 아니라면 여기서 턴 멈추기
    if isChanged == False:
        break
print(lists)

 

또 하나 체크해야 할 것이 있다.

 

턴을 한번 할 때 마다, len(lists) - 1번째 수, 즉 마지막 인덱스의 수는 리스트의 최댓값이다.

그렇기 때문에 굳이 마지막과 그 이전 수의 비교는 할 필요가 없다는 것이다.

이게 턴을 돌 때 마다 뒤에서부터 정렬이 착착 이루어질 것 이기 때문에 이것도 낭비다.

 

이를 해결하기 위해, 한번 턴을 돌 때마다 i를 빼 주면 된다.

 

아래는 최종적으로 정리가 된 코드이다.

 

lists = [8, 3, 2, 7, 6]
isChanged = False
for i in range(len(lists) - 1):
    # 턴 횟수가 증가하면서 뒤에서부터 정렬 된 숫자 갯수도 그만큼 늘어나므로 그냥 빼준다.
    for j in range(len(lists) - 1 - i):
        if lists[j] > lists[j + 1]:
            lists[j], lists[j + 1] = lists[j + 1], lists[j]
            isChanged = True

    if isChanged == False:
        break
print(lists)

---

시간복잡도

이중 for문 이기 때문에 O(n^2)이다.

이미 정렬 돼 있다면 한번만 돌아서 확인하면 되므로 O(n)이다.

 

---

패스트캠퍼스 자료구조와 알고리즘 공부 후 정리한 내용입니다