[알고리즘/버블정렬] #Bubble_Sort / in Python

버블 정렬

숫자를 오름차순으로 정렬하는 프로그램 
하지만 쉽게 해석하려면 가장 큰 숫자를 맨 뒤로 보내는 것과 같다고 생각하면 된다.

---

arr = [3, 4, 5, 1, 2]이라는 리스트가 있을 때 이것을 어떻게 오름차순으로 정렬할까? 

두 수를 선택해서 큰값을 뒤로 보내는 방법을 버블 정렬이라고 한다.

#1 [3, 4, 5, 1, 2] #3과 4을 자리 바꾸기 // 변하지 않음
#2 [3, 4, 5, 1, 2] #4와 5 자리 바꾸기 // 변하지 않음
#3 [3, 4, 1, 5, 2] #1과 5 자리 바꾸기 
#4 [3, 4, 1, 2, 5] #2와 5 자리 바꾸기

순서로 진행된다.

결국 5가 가장 마지막이고 1은 가장 처음으로 온다. 

---

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14

''' 반복문 사용 i,j >>> 배열에 있는 원소 반복적으로 탐색 ''' def bubble_sort(arr):     for i in range(len(arr)):         for j in range(0, len(arr)-i-1):             if arr[j] > arr[j+1]:                 arr[j], arr[j+1] = arr[j+1], arr[j]     return print(arr)   if __name__ == '__main__':     arr = [1,10,4,2,9,8,3,5,6,7]     bubble_sort(arr)

코드는 선택 정렬에 비해 직관적으로 해석할 수 있다.

앞 숫자와 뒤 숫자를 단순히 비교하여 앞숫자가 뒷숫자보다 크다면 바꿔주는 형식으로 진행하면 된다.

#집합의 크기가 1씩 줄어든다
#10 + 9 + ... + 2 + 1
#N * (N+1) / 2
#N^2
#실제 수행 결과는 선택정렬보다 느리다
#매번 자리를 바꿔줘야 되기 때문에....

이를 통해 시간 복잡도를 알 수 있다.

#빅오(Big O) 표기법
버블 정렬의 시간 복잡도는 O(N^2)가 된다.

 선택정렬과 시간 복잡도는 같으나, for문에 있는 자리 바꿈을 계속 해줘야 하기 때문에...
실제로 실행해보면 버블정렬이 선택정렬보다 시간이 더 걸리는걸 알 수 있다.