버블정렬 알고리즘 (Bubble Sort)

• 서로 인접한 두 요소를 비교하여, 정렬하는 알고리즘
• 큰 수 부터, 오른쪽에 정렬된다.
• 인접한 두 수를 비교하여, 크기 순으로되어있지않으면, 스왑한다.

[ 5 , 1 , 2 , 8 , 7 , 3 , 9 , 6 , 10 , 4 ]

위와같은 배열이 존재할때,

1. 1번째 요소와 2번째 요소를 비교, 크기순으로 스왑
2. 2번째 요소와 3번째 요소를 비교, 크기순으로 스왑
3. N-1번째 요소와 N번째 요소를 비교, 크기순으로 스왑
4. 반복

[ 5 , 1 , 2 , 8 , 7 , 3 , 9 , 6 , 10 , 4 ]

[ 1, 5 , 2 , 8 , 7 , 3 , 9 , 6 , 10 , 4 ]

...

[ 1 , 2 , 5 , 7 , 8 , 3 , 9 , 6 , 10 , 4 ]

[ 1 , 2 , 5 , 7 , 3 , 8 , 9 , 6 , 10 , 4 ]

...

[ 1 , 2 , 5 , 7 , 3 ,8 , 6 , 9 , 10 , 4 ]

[ 1 , 2 , 5 , 7 , 3 ,8 , 6 , 9 , 4 , 10 ]

...

[ 1 , 2 , 3 , 4 , 5 ,6 , 7 , 8 , 9 , 10 ]

알고리즘 구현

def solution(array):
   answer = []
   
   for (idx,n) in enumerate(array):
       for a in range(len(array) - 1 - idx):
           if array[a] > array[a+1]:
               array[a], array[a+1] = array[a+1], array[a]

   answer = array  
   return answer

시간 복잡도 O(N^2)

버블정렬은 최악이든 최선이든 O(N^2)의 복잡도를 갖는다.

O(N^2)을 갖는 정렬

삽입정렬(Insertion Sort), 선택정렬(Selection Sort), 버블정렬(Buble Sort)가 존재한다.
삽입정렬 > 선택정렬 > 버블정렬 순으로 빠르다.