버블정렬(Bubble) 이란?
두 인접한 원소를 검사하여 정렬하는 방법이다.
시간복잡도는 O(n^2)으로 느리지만, 구현하기 매우 쉽다.
def bubble(array):
print("bubble")
for i in range(len(array)-1):
for j in range(len(array)-1-i):
if array[j] > array[j+1]:
array[j],array[j+1] = array[j+1],array[j]맨 앞 숫자부터 다음 숫자로 가면서 바로 뒤에 있는 숫자들과 비교하여, 뒤에 있는 숫자가 더 작을때마다 서로 교환하는 방식이다.
위 코드가 돌아가는 단계를 세세히 뜯으면 아래와 같다.
Array = [3,4,5,2,1] 일때
1번째 큰 루프 시작
1번째 숫자 3 비교 (1번째 숫자 == 0번 인덱스 숫자 일때)
3 > 4 : 뒤에 있는 숫자가 더 크다. 변화 없음
2번째 숫자 4 비교
4 < 5 : 뒤에 있는 숫자가 더 크다. 변화 없음
3번째 숫자 5 비교
5 > 2 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [3,4,2,5,1]
4번째 숫자 5 비교
5 > 1 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [3,4,2,1,5]
첫번째 큰 루프 끝. (for i)
2번째 큰 루프 시작
Array = [3,4,2,1,5]
1번째 숫자 3 비교
3 < 4 : 뒤에 있는 숫자가 더 크다. 변화 없음
2번째 숫자 4 비교
4 < 2 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [3,2,4,1,5]
3번째 숫자 4 비교
4 < 1 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [3,2,1,4,5]
두번째 큰 루프 끝. 5까지 비교하지 않는 이유는 첫번째 큰 루프때 제일 큰 숫자 자리가 정해진다. 같은 원리로 두번째 루프가 끝나면 2번째로 큰 숫자 자리가 정해진다.
3번째 큰 루프 시작
Array = [3,2,1,4,5]
1번째 숫자 3 비교
3 < 2 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [2,3,1,4,5]
2번째 숫자 3 비교
3 < 1 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [2,1,3,4,5]
3번째 큰 루프 종료.
4번째 큰 루프 시작
Array = [2,1,3,4,5]
1번째 숫자 2 비교
2 < 1 : 뒤에 있는 숫자가 더 작다. 자리 교환
Array = [1,2,3,4,5]
4번째 큰 루프 종료.
큰 루프 종료
