4장 버블정렬

버블정렬 알고리즘

• 최종 정렬이 될 때까지 이웃한 두 개의 값을 비교 정렬 (오름차순으로)

• 매 단계마다 가장 오른쪽에 위치해야 할 하나의 값 결정

• 각 단계를 "패스스루"라고 부름

  • 패스스루 passthrough : 알고리즘의 주요 단계들을 "통과"했다는 의미

    배열이 완전히 정렬될 때까지 같은 절차를 반복

• 예시

버블 정렬 함수 설명

#버블 정렬 함수 구현
def bubble_sort1(list):
    #어떤 인덱스까지 아직 정렬되지 않았는지 기록
    unsorted_until_index = len(list) - 1

    #배열의 정렬 여부를 기록
    sorted = False

    #배열이 완전히 정렬됐음을 알 때까지 while 루프 실행
    while not sorted:

        #for루프는 배열의 첫 인덱스부터 아직 정렬되지 않은 인덱스까지 수행
        for i in range(unsorted_until_index):

            #모든 인접 값 쌍을 비교하고 순서가 뒤바뀌어 있으면 교환
            if list[i] > list[i+1]:
								sorted = False
                list[i], list[i+1] = list[i+1], list[i]

        #unsorted_until_index값을 1 감소
        unsorted_until_index = unsorted_until_index -1
        if unsorted_until_index == 0:
            sorted = True

• len(list) - 1 : 어떤 인덱스까지 아직 정렬이 되지 않았는지 기록

  인덱스를 구해야 하는 것이기 때문에 배열의 길이에서 1을 빼야 하는 것

  왜냐하면 배열은 항상 0부터 시작하기 때문에 1을 빼야 한다.

버블 정렬의 효율

버블 정렬 알고리즘의 두 단계

• 비교 : 어느 쪽이 더 큰 지 두 수를 비교

• 교환(swap) : 정렬하기 위해 두 수를 교환

• N개의 원소가 있는 때 버블 정렬의 비교 횟수

  → 비교는 항상 일어남

  • (N-1) + (N-2) + (N-3) + ... + 1