버블정렬
버블정렬은 서로 인접한 두 요소를 값을 비교해서 큰 값을 뒤로 정렬하는 것이다.
1라운드가 종료 될 때마다 최대값이 맨 뒤로 정렬된다.
모든 라운드가 종료되면 오름차순으로 값이 정렬된다.
구현이 간단하다는 장점이 있지만, 그 만큼 단점이 크다.
먼저 인접한 모든 요소를 비교를 반복해야한다.
그리고 그 비교하는 것을 요소의 크기만큼 다시 반복해야한다.
또한 정렬과정중 정렬이 완료 되어도, 끝까지 반복문을 수행해야 한다.
그러다보니 효율적이지 않다.
arr = [6,5,3,2,8]
# arr = [5,3,2,6,8]
def bubbleSort(arr):
for i in range(len(arr)):
for i in range(len(arr)-1):
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]
print(arr)
print("-----------------")
return arr
print(bubbleSort(arr))
1라운드
[5, 6, 3, 2, 8]
[5, 3, 6, 2, 8]
[5, 3, 2, 6, 8]
[5, 3, 2, 6, 8]
-----------------
2라운드
[3, 5, 2, 6, 8]
[3, 2, 5, 6, 8]
[3, 2, 5, 6, 8]
[3, 2, 5, 6, 8]
-----------------
3라운드
[2, 3, 5, 6, 8]
[2, 3, 5, 6, 8]
[2, 3, 5, 6, 8]
[2, 3, 5, 6, 8]
-----------------
4라운드
[2, 3, 5, 6, 8]
[2, 3, 5, 6, 8]
[2, 3, 5, 6, 8]
[2, 3, 5, 6, 8]
-----------------
5라운드
[2, 3, 5, 6, 8]
[2, 3, 5, 6, 8]
[2, 3, 5, 6, 8]
[2, 3, 5, 6, 8]
-----------------
버블정렬 결과
[2, 3, 5, 6, 8]버블정렬 시간복잡도
버블정렬의 경우 두번의 반복문을 사용하기 때문에 BigO표기법에 따르면,
O(n^2)의 복잡도가 된다.
