4.2.1 버블 정렬 구현

다음은 파이썬으로 구현한 버블 정렬이다.

def bubble_sort(list): 
    unsorted_until_index = len(list) - 1  
    sorted = False 

    while not sorted:  
        sorted = True 
        for i in range(unsorted_until_index):  
            if list[i] > list[i+1]: 
                list[i], list[i+1] = list[i+1], list[i] 
                sorted = False  
        unsorted_until_index -= 1

    return list

위 함수는 다음 코드처럼 정렬되지 않은 배열을 전달하여 사용한다.

print(bubble_sort([65, 55, 45, 35, 25, 15, 10]))

그러면 함수는 정렬된 배열을 반환한다.

한 줄씩 나눠서 어떻게 동작하는지 살펴보자. 각 줄마다 설명을 먼저 하고 뒤이어 해당 코드를 보이겠다.

가장 먼저 unsorted_until_index 변수부터 생성한다. 이 변수는 아직 정렬되지 않은 배열의 가장 오른쪽 인덱스를 기록한다. 알고리즘을 처음 시작할 때는 전체 배열이 정렬되지 않은 상태이므로 배열의 마지막 인덱스로 변수를 초기화한다.

unsorted_until_index = len(list) - 1

배열의 정렬 여부를 기록하는 sorted 변수도 생성한다. 물론, 코드가 처음 실행될 때는 정렬되지 않은 상태이므로 False를 할당한다.

sorted = False

배열이 정렬될 때까지 계속 실행될 while 루프를 시작한다. 루프 한 번 실행이 배열의 한 패스스루에 해당한다.

while not sorted:

이어서 sorted에 True를 할당한다.

sorted = True

각 패스스루 안에서는 교환이 일어나기 전까지 배열이 정렬되어 있다고 가정하고 값을 교환하면 변수를 다시 False로 바꾸는 방식을 취한다. 이렇게 해야 어떤 교환도 하지 않고 전체 패스스루를 통과할 때 sorted가 True로 남아서 배열이 완전히 정렬된 상태임을 알 수 있다.

while 루프 내에서 for 루프를 시작한다. 루프 안에서는 배열 내 모든 값 쌍을 가리킨다. 변수 i를 첫 포인터로 사용해 배열의 첫 인덱스부터 아직 정렬되지 않은 인덱스까지 수행한다.

for i in range(unsorted_until_index):

for 루프 내에서는 모든 인접 값 쌍을 비교하고 순서가 뒤바뀌어 있으면 교환한다. 또한, 교환하게 되면 sorted를 False로 바꾼다.

if list[i] > list[i+1]:
    list[i], list[i+1] = list[i+1], list[i]
    sorted = False

각 패스스루가 끝나면 오른쪽으로 올려준 값(버블)이 이제 올바른 위치에 있음을 알 수 있다. 바꿔 말하면 기존에 가리키고 있던 인덱스가 이제 정렬된 상태이니 unsorted_until_index 값을 1 감소시킨다.

unsorted_until_index -= 1

sorted가 True가 되면, 즉 배열이 완전히 정렬되면 while 루프가 종료된다. 이때 정렬된 배열을 반환한다.

return list