[알고리즘] 버블정렬 향상 시키기

 

버블정렬은 가장 쉽고

이해하기 쉬운 정렬이다.

 

그러나 시간복잡도가

O(n²)이어서 효율이 좋지 않다.

 

 

7개의 수를 일차원 배열에 저장하였다. 이제 버블정렬을 사용하여 오름차순으로 바꾸어 보자.

 

 

버블정렬은 우측 끝부터 두 개씩 대소를 비교하여 위치를 바꾸는 방법이다. 모든 비교가 끝났을 때, 맨 좌측에는 오름차순일 경우 가장 작은 수, 내림차순인 경우 가장 큰 수가 자리잡는다. 이렇게 반복하여 좌측을 하나씩 오름차순 혹은 내림차순으로 정렬하는 방식이 버블정렬이다.

 

그러나 버블정렬은 효율이 좋지 않다. 

 

n개의 수를 정렬한다고 가정해보자.

1회전 : n-1 번 비교

2회전 : n-2 번 비교

3회전 : n-3 번 비교

.

.

n-1회전 : 1번 비교

(n-1) + (n-2) + (n-3) + .... + 2 + 1 = n(n-1)/2 

▶ 시간복잡도 : O(n²)

 

버블정렬을 효율을 조금 더 높혀보자.

 

 

첫 번째 비교, 두 번째 비교, 세 번째 비교는 교환이 일어나지 않았다. 교환이 일어나지 않았다는 의미는 이미 정렬이 완료되었다는 의미이다.

 

이 원리를 활용한 두 가지 방법이 있다.

 

첫 번째 방법

1회전, 2회전, 3회전... 을 하면서 교환횟수를 카운트 한다. 만약 교환횟수가 0이면 정렬이 완료되었다는 의미이다.

 

두 번째 방법

1회전, 2회전, 3회전...을 하면서 교환이 일어난 마지막 위치를 파악한다. 

 

 

6과 4를 교환한 후, 3 과 4 비교, 1 과 3 비교는 교환을 만들어내지 못한다. 이는 곧 1, 3, 4는 정렬이 완료되었다는 의미이다. 그러므로 6의 위치부터 버블정렬을 실시하면된다. 

 

이와 같이, 버블 정렬은 교환이 일어나지 않으면 이미 정렬이 되었다는 의미를 갖고 있기에 이를 잘 활용하면 효율을 최대한으로 높힐 수 있다.

 

버블정렬의 코드 구현은 아래 포스팅에서 정리해두었으니 참고 바란다. 

[JAVA] 백준 2750번 수 정렬하기 : 버블 정렬