1. 버블정렬
버블정렬은 인접한 두개의 자료 값을 비교하며 위치를 교환하는 방식으로 진행된다.
번호가 n번까지 있는 배열을 생각해보자.
처음에는 배열의 0번부터 시작하여 0번과 인접한 1번의 값을 비교한다.
만약 값이 크다면 자리를 바꿔주고, 아니라면 바꿔주지 않는다.
그 후 1번부터 다시 비교를 시작한다. 1번과 인접한 2번의 값을 비교한다.
1번 값이 큰다면 자리를 바꿔주고, 아니라면 바꾸지 않는다.
…
이런 과정들을 반복하다 보면 0번부터 배열의 n-1번에 도달하여 비교함을 끝으로 해당 배열의 가장 큰 수가 마지막에 와있을 것이다.
가장 큰 수를 정렬해 주었으면 이제 0번부터 n-1번까지의 수를 정렬해주어야한다.
위의 방식을 한번 더 반복하면 n-1번에는 배열에서 두번째로 큰 수가 오게된다.
…
반복, 반복 하다보면 결국에는 배열이 정렬되어있는 것을 볼 수 있을것이다.
또한, 버블정렬은 동일 수가 있어도 자리가 바뀌지 않는 안정(stable)정렬이다.
1-1. 시간복잡도
버블정렬의 방법을 생각해보면 처음 순환할 때는 0번부터 n번까지 서로 인접한 값을 비교하는데 n-1번 비교를 하게 된다.
두번째 순환할 때는 n-2번을, 세번째는 n-3번을 … 결국 마지막에는 1번을 비교하게 될것이다.
이 경우를 모두 더하면 버블 정렬을 이용하여 정렬을 하게 되는 최악의 경우
\((n-1) + (n-2) + ... + 2 + 1\) 번 비교를 해야 할 것이고,
해당 식을 줄이면 \((n-1) n / 2 = (n^2 - n) / 2\)가 된다.
결국 버블정렬의 시간복잡도는 \(O(n^2)\)이다.(최선의 경우도 \(Ω(n^2)\)이다.)
2. 구현하기 - python
아래의 코드에서는 change변수를 넣어 개선을 조금 하였다.
만약 change를 넣지 않고 진행 하였다면 최선, 평균, 최악 모두 시간복잡도가 \(O(n^2)\)일 것이다.
하지만 change를 이용하여 한바퀴를 돌았을 때 자리가 한번도 바뀌지 않았다면
이미 배열이 정렬이 완료가 되었다는 뜻이 되므로 정렬이 완료되면 더이상 반복문을 돌지않고 중단한다.
1
2
3
4
5
6
7
8
9
def bubbleSort(list) :
for i in range(0, len(list)) : # 배열의 길이만큼 반복한다.
change = False # 순환 중 자리가 바뀌었는지 확인을 위한 change
for j in range(0, len(list) - 1 - i) : # 배열의 n-1까지 비교한다.
if list[j] > list[j + 1] : # 만약 현재값과, 다음값을 비교시 현재값이 크면
list[j], list[j + 1] = list[j + 1], list[j] # 자리 변경
change = True
if change == False : # 한 바퀴를 돌았는데 자리가 바뀌지 않았다면 정렬이 완료된것.
break # 더 이상 반복하지 않아도 된다.