BubbleSort.py

# 04-1 버블 정렬

# 1. 정렬 알고리즘 정의와 종류
# 1) 버블 : 인접한 요소끼리 비교해서 swap 연산을 수행하며 정렬
# 2) 선택 : 대상에서 가장 크거나 작은 데이터를 찾아 선택을 반복하며 정렬
# 3) 삽입 : 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하며 정렬
# 4) 퀵 : 피봇 값을 선정해 해당 데이터를 기준으로 정렬
# 4) 병합 : 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬
# 5) 기수 : 데이터의 자릿수를 바탕으로 비교해 정렬

# ------------------------------------------------------------------------------------------------------------------------
# 1. 버블 정렬 
# - 간단하게 구현할 수 있으나 시간 복잡도가 O(n^2)으로 비교적 다른 정렬 알고리즘에 비해 느리다.

# 과정
# 1) 비교 연산이 필요한 루프 범위 설정
# 2) 인접한 데이터끼리 비교
# 3) swap 조건에 맞으면 swap 연산 수행
# 4) 루프 범위까지 2~3 과정 반복
# 5) 정렬 영역을 재설정, 이때 정렬를 완료한 영역은 제외한다.
# 6) 비교 대상이 없을 때까지 1~5 과정 반복

# - 특정 루프의 전체 영역에서 swap이 한 번도 발생하지 않음
# => 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 의미! 프로세스 종료!