버블 정렬 알고리즘

2개일 경우

0	1
5	2

0과 1을 비교

 

3개일 경우

0	1	2
5	2	1

0과 1을 비교, 1과 2를 비교

0	1	2
2	1	5

한번 더 해야함.

 

4개일 경우 - 0과 1을 비교, 1과 2를 비교, 2와 3을 비교 x 3

 

순회 횟수 = length -1

반복 횟수 = length -1

 

기본 로직

1. length -1만큼 반복문

2. 1번 안에 length - 1만큼 중첩 반복문

3. 비교 후 바꿔주는 로직

 

 

반복 시 불필요한 순회 빼기

순회할 때마다 해당 순회차의 마지막 값은 확실하게 정렬된 값임

순회차 = i

i = 1일 때 반복 횟수 - 1

i = 2일 때 반복 횟수 - 2

 

반복횟수 = length - 1 - i

 

순회 시 스왑이 한번도 일어나지 않았을 경우 조기 종료

 

정리

1. length -1만큼 반복문

2. 1번 안에 length - 1 - i만큼 중첩 반복문

3. 비교 후 바꿔주는 로직

4. 한번도 바꿔주지 않았다면 브레이크

for index in range(length -1):
	스왑 = false
	for index2 in range(length - 1 - i):
    		if 앞데이터 > 뒤데이터:
        		바꿔준다.
                	스왑 토글
                    
	스왑 false면 종료
리턴

---

def bubblesort(data):
    for index in range(len(data) - 1):
        swap = False
        for index2 in range(len(data) - 1 - index):
            if data[index2] > data[index2 + 1]:
                data[index2], data[index2 + 1] = data[index2 + 1], data[index2]
                swap = True
        
        if swap == False:
            break
    return data