Sorting Algorithm - 버블정렬 (bubble sort)

버블 정렬은 인접한 두 개의 원소를 비교해여 자리를 교환하는 방식이다.

 

첫번째 원소부터 시작해서 마지막 원소까지 서로 인접한 원소와 크기를 비교하여 자리를 교환한다.

 

버블정렬은 첫번째 원소부터 마지막 원소 까지 한 사이클을 진행하면 가장 큰값이 마지막 자리에 놓인다.

 

---

 

다음 배열을 버블정렬하면 다음과 같이 시각화 할 수 있다 (한 사이클)

96

35

1

58

2

19

---

1) 96과 35를 비교해서 96이 더 크므로 교환

35

96

1

58

2

19

 

2) 96과 1를 비교해서 96이 더 크므로 교환

35

1

96

58

2

19

 

3) 96과 58을 비교해서 96이 더 크므로 교환

35

1

58

96

2

19

 

3) 96과 2을 비교해서 96이 더 크므로 교환

35

1

58

2

96

19

 

3) 96과 19을 비교해서 96이 더 크므로 교환

35

1

58

2

19

96

 

 

한 사이클 종료 이후 다음 사이클에서는 96을 제외 (이미 가장 큰수로 정렬되었기 때문)

 

35

1

58

2

19

 

---

이를 코드로 구현하면 다음과 같다. 

int[] arr = {96, 35, 1, 58, 2, 18}

for (int i=0; i < arr.length; i++) {
    for (int j=0 < arr.length-i < j++) {
        int temp = arr[j+1];
        arr[j+i] = arr[j];
        arr[j] = temp;
    }
}

i = 0 일때

j = 0 ~ 4 까지 진행된다. 

swap(j, j+1)  >>  [0,1] [1,2] [2,3] [3.4] [4,5] 이 진행되어 마지막인 index 5 에 가장 큰 값인 96이 배치된다.

 

i = 1 일때

j = 0 ~ 3 까지 진행된다. ( i 가 1씩 커질수록 j 의 마지막 범위는 줄어든다)

swap(j, j+1)  >>  [0,1] [1,2] [2,3] [3.4] 이 진행되어 마지막인 index 4 에 그 다음 큰 값인 58이 배치된다.

 

i = 2 일때

j = 0 ~ 2 까지 진행된다. ( i 가 1씩 커질수록 j 의 마지막 범위는 줄어든다)

swap(j, j+1)  >>  [0,1] [1,2] [2,3] 이 진행되어 마지막인 index 3 에 그 다음 큰 값인 35이 배치된다.

 

i = 3 일때

j = 0 ~ 1 까지 진행된다. ( i 가 1씩 커질수록 j 의 마지막 범위는 줄어든다)

swap(j, j+1)  >>  [0,1] [1,2] 이 진행되어 마지막인 index 2 에 그 다음 큰 값인 18이 배치된다.

 

i = 4 일때

j = 0 이 진행된다. ( i 가 1씩 커질수록 j 의 마지막 범위는 줄어든다)

swap(j, j+1)  >>  [0,1] 이 진행되어 마지막인 index 1 에 그 다음 큰 값인 2이 배치된다.