버블 정렬

일반적으로 가장 기본적으로 생각할 수 있는 방법

인접한 두 요소의 대소 관계를 비교하여 교환을 반복!

 

앞(혹은 뒤)에서부터 차례대로 비교/교환이 이루어지기 때문에 안정정렬

 

맨 앞에서부터 현재 요소와 바로 다음 요소끼리 비교

현재 요소가 다음 요소보다 크다면 교환

다음 인덱스로 이동해 그 다음 요소와 비교/교환을 반복

 

배열의 요소 갯수가 n개라 한다면, 이웃한 요소끼리 비교/교환 작업을 처음부터 끝까지 한 번 진행하면,

가장 큰 요소가 맨 마지막 인덱스로 이동한다. 이 과정을 패스라고 한다.(n-1회 비교)

그리고선 남은 n-1개 요소로 비교/교환을 앞에서부터 끝까지 한 번 진행하면, 다음으로 큰 요소가 맨 마지막 직전 인덱스로 이동한다. (n-2회 비교) 이런 식으로 계속 진행하면, 이러한 작업이 총 n-1번의 패스가 필요하다.

 

즉, (n-1) + (n-2) + (n-3) + ... + 2 + 1 회 연산이 대략 일어난다. 즉 n(n-1)/2 => O(N^2)의 시간 복잡도를 가진다.

best, average, worst 상황 모두 O(N^2)이다. (교환은 안 일어나더라도 비교는 계속 일어나므로)

 

 

개선 1

1회의 패스가 일어나는 동안 요소끼리 교환되는 횟수를 측정한다.

만일 1회의 패스동안 교환된 요소가 없다면, 정렬이 끝났다는 의미이므로 반복을 종료한다.

 

정렬이 완료된 상태의 배열로 진행하는 경우(best 상황) 처음 1회 n-1회 비교만 일어나고, 교환이 일어나지 않으므로

과정을 종료한다. 이 때는, O(N)의 시간복잡도를 가진다.

 

개선 2

1회의 패스가 일어날 때, 마지막 교환이 일어났던 인덱스를 매번 저장한다.

이를 통해 다음 번 패스를 수행할 범위를 줄일 수 있다. (마지막 교환이 일어나고 그 뒤로는 비교만 일어났다는 건, 마지막 교환이 일어난 인덱스 이후로는 정렬이 완료되었다는 의미로 볼 수 있다.)

 

개선 3

양방향 버블 정렬 (칵테일 정렬, 셰이커 정렬)이라고 한다.

패스의 진행방향을 교차로 진행한다.

1. 맨 좌측 요소부터 맨 우측 요소까지 비교/교환 진행

2. 마지막 교환이 이루어진 지점을 우측 지점으로 지정

3. 우측 지점부터 좌측까지 비교/교환 진행

4. 마지막 교환이 이루어진 지점을 좌측 지점으로 지정

5. 좌측 지점부터 우측 지점까지 비교/교환 진행

6. 좌/우측 지점이 교차하여 더 이상 비교할 수 없게 될 때까지 위 과정을 반복

 

최악의 경우는 일반 버블 정렬과 속도가 동일하다.