알고리즘: 버블 정렬

버블정렬

두 인접한 데이터의 크기를 비교해 정렬하는 방법으로 간단하게 구현가능하지만 시간 복잡도가 O(n^2)이다. 루프를 돌면서 데이터 간 swap연산으로 정렬한다.

정렬 과정

1. 비교 연산이 필요한 루프 범위 설정
2. 인접한 데이터 값 비교
3. swap 조건에 부합하면 swap 연산 수행
4. 루프 범위가 끝날 때까지 2~3과정 반복
5. 정렬 영역 재설정
6. 비교 대상이 없을 때까지 1~5과정 반복

중단 조건

특정한 루프 전체 영역에서 swap이 한 번도 발생하지 않았다면 정렬이 완료됐다는 뜻으로, 프로세스를 종료해도 된다.

코드 구현

기본 코드

n = int(input())
lst = []
    
for i in range(n):
    x = int(input())
    lst.append(x)

for i in range(n-1):
    for j in range(n-1-i):
        if lst[j] > lst[j+1]:
            temp = lst[j]
            lst[j] = lst[j+1]
            lst[j+1] = temp

중단 조건 추가

swap 발생했는지 확인하는 변수를 추가해 swap이 발생하지 않았으면 종료

n = int(input())
lst = []
    
for i in range(n):
    x = int(input())
    lst.append(x)

for i in range(n-1):
    change = False
    for j in range(n-1-i):
        if lst[j] > lst[j+1]:
            changed = True
            temp = lst[j]
            lst[j] = lst[j+1]
            lst[j+1] = temp
    if changed == False:
        break