버블 정렬 (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

콘텐츠 사용 시 출처 표기 부탁 드리고, 댓글은 큰 힘이 됩니다^^