파이썬 버블정렬 Python Bubble Sort

안녕하세요, 츄르 사려고 코딩하는 집사! 코집사입니다.

1. 코드입니다.

---

N = int(input()) #1
A = []
for i in range(N) : #2
    A.append(input())


for a in range(N-1) : #3
    for b in range(N-1) :
        if A[b] > A[b+1] : #4
            A[b], A[b+1] = A[b+1], A[b]

print(A)

#1 : 리스트의 크기 입력(입력 받을 리스트의 값들 갯수)

#2 : 리스트에 값 입력

#3 : 버블 소트를 리스트의 크기 N 만큼 반복

#4 : 첫 자리와 그 다음 자리 비교 후 앞이 더 크면 swap

---

이미 정렬 완료 됐을 때 코드

---

N = int(input())
A = []
for i in range(N) :
    A.append(input())


for a in range(N-1) :
    flag = 0
    for b in range(N-1) :
        if A[b] > A[b+1] :
            A[b], A[b+1] = A[b+1], A[b]
            flag = 1
            print(A)

    if flag == 0 :
        break

print(A)

flag를 사용하여 기존에는 0이다가, 스왑을 했을 시 1로 변경 if문으로 안들어갈 때 flag는 1로 변하지 않으니 정렬이 완료되면  정지

---

버블정렬

---

- 두 인접한 원소를 검사하여 정렬하는 방법

- 버블정렬의 시간 복잡도 : O(n^2)

- 최선 : 이미 정렬되어 있는 경우 -> swap 횟수 : 0번, 비교횟수 :  n(n-1) / 2

- 최악 : 숫자가 내림차순으로 되어 있는 경우 -> swap 횟수 : n(n-1) / 2, 비교 횟수 n(n-1) / 2