버블 정렬 (Bubble Sort)

I. 순차 비교 정렬 알고리즘, 버블 정렬

개념도	개념
	인접한 2개의 값을 비교하여 크기가 순서대로 되어 있지 않으면 값을 서로 교환하여 끝까지 진행하는 알고리즘

II. 버블 정렬에서 flag의 의미

가. flag를 두지 않는 경우

정렬 절차	설명
	flag를 두지 않는 경우 처음부터 끝까지 비교/교환 과정 수행 이미 정렬이 되어 있어도 모두 비교 과정 수행

나. flag를 두는 경우

정렬 절차	설명
	flag를 두는 경우 이미 정렬이 되어 있는 경우 flag 값을 1로 설정하여 루프 종료 이미 정렬되어 있는 값에 대해 불필요하게 비교/교환 과정 거치지 않음

다. flag를 두는 이유

• 버블 정렬의 단점 중 하나가 정렬이 완료 된 경우에도 지속적으로 정렬을 시도
• 따라서 flag값을 두어 특정 위치의 정렬이 모두 완료된 경우 의미 없는 정렬 수행을 차단하여 성능 개선

III. 버블 정렬 알고리즘으로 정렬 사례

• flag 두지 않는 경우 총 7단계에 걸쳐 비교/교환 과정 수행
• flag 두는 경우 2단계에서 정렬이 완료, 불필요한 비교/교환 과정 없이 결과 도출하여 수행 성능 개선

def bubbleSort(alist): for loop_count in range(len(alist)-1, 0, -1): for idx in range(loop_count): if alist[idx] > alist[idx+1]: tmp = alist[idx] alist[idx] = alist[idx+1] alist[idx+1] = tmp return alist