[java, 알고리즘] 버블 정렬(Bubble Sort)

알고리즘을 이해하자 하자 하자 하자!

 

함께 보면 좋을 포스팅

[알고리즘] 선택 정렬(Selection Sort)

 

---

 

버블 정렬의 이해

버블 정렬은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘입니다.
원소의 이동이 거품이 올라오는 듯한 모습을 하여 이를 본떠 버블 정렬이라고 지어졌습니다.

방식

버블 정렬은 크게 3단계로 동작합니다.

1.  지정 : 비교 탐색을 할 원소를 지정합니다.
2.  정렬 : 지정한 원소와 인접한 원소를 비교하여 정렬합니다. (조건 충족 시 원소 교환)
3.  회전 : 1·2단계를 반복해 마지막 인덱스까지 비교 후 처음 원소로 돌아가 정렬한 마지막 원소를 제외하고 회전합니다.

 

분류

선택 정렬은 정렬 유형 3가지에 해당합니다.

• 비교 정렬 : 정렬 연산이 두 값을 비교하는 것을 기반으로 일어납니다.
• 제자리 정렬 : 주어진 메모리 공간 외에 추가적인 공간을 필요로 하지 않는 정렬 방식
  • 원소의 정렬이 내부적으로 이뤄지며, 원소 외부의 필요한 변수나 메모리가 거의 없음을 의미함
• 안정 정렬 : 입력 순서와 동일하게 정렬 (중복 원소 존재 시 원소의 순서를 보장합니다)

 

선택 정렬의 구현

알고리즘 내부 동작 흐름

버블 정렬을 활용해 배열 {3, 9, 1, 7, 5} 를 오름차순 {1, 3, 5, 7, 9}로 정렬할 시 내부 원소의 정렬 흐름 예시입니다.

 

 

[범례]

* 현재 지정한 원소(교환 전 / 후로)

* 지정 원소와 비교할 원소(교환 전 / 후로)

* 정렬이 완료된 원소

 

 

[알고리즘 동작 단계 : 총 3단계]

1. 원소 지정(배열의 0부터 배열의 크기 n까지 인덱스를 순회하며 탐색) 
   • 예제에서 인덱스는 j, 원소는 arr[j] 로 가정
2. 지정한 원소 arr[j] 와 인접한 원소인 arr [j+1]의 비교 및 교환
   • arr [j] 보다 arr [j+1] 이 작을 시 원소 순서 교환 발생
3. 1·2단계를 반복할 시 마지막 인덱스에는 가장 큰 수가 위치, 처음 원소로 돌아가 마지막 원소를 제외하고 재회 전
   • 예제에서 정렬이 완료된 인덱스를 제외한 회전은 i로 나타냄

 

3

9

1

7

5

 

1. 초기 인덱스인  j = 0 일 때,  arr [0]과 arr [1]을 비교합니다. 3이 9보다 작으므로 교환은 일어나지 않습니다.

 

3

9

1

7

5

 

2. 지정 인덱스를  j = 1로 옮긴 후, arr [1]과 arr [2]를 비교합니다. 

 

3

1

9

7

5

 

3. 1 < 9 이므로 두 원소를 교환합니다.

 

3

1

9

7

5

 

4. 지정 인덱스를 j =2로 옮긴 후, arr [2]와 arr [3]을 비교합니다.

 

3

1

7

9

5

 

5. 7 < 9 이므로 두 원소를 교환합니다.

 

3

1

7

9

5

 

6. 지정 인덱스를  j=3으로 옮긴 후, arr [3]과 arr [4]를 비교합니다.

 

3

1

7

5

9

 

7. 5 < 9이므로 두 원소를 교환합니다.

 

이로써 j = 0부터 n-1인 4까지 인덱스가 증가하며 1회전이 완료되었으며,

최종적으로 가장 큰 수인 9를 맨 오른쪽 인덱스로 옮겼습니다.

 

따라서 2회전은 가장 큰 수로 정렬을 완료한 마지막 인덱스를 제외한 j = 0부터 n - 2까지 정렬을 다시 실시합니다.

 

3

1

7

5

9

 

8. i는 배열의 크기 n에서 마지막 인덱스를 제외한 n-1로 줄었으며,

인덱스는 j = 0부터 다시 인접 인덱스와 교환을 실시합니다.

이하는 과정은 반복되므로 도표만 참고하시어 원소가 어떻게 교환되어 가는지 참고해 주세요.

 

3

1

7

5

9

 

1

3

7

5

9

 

1

3

7

5

9

 

1

3

7

5

9

 

1

3

5

7

9

 

1

3

5

7

9

 

1

3

5

7

9

 

1

3

5

7

9

 

1

3

5

7

9

 

1

3

5

7

9

 

 

슈도 코드

method sort(배열의 길이, 정렬할 배열) { // 배열을 오름차순으로 정렬한다.
    for (int i = (배열의 길이 -1)부터 ~ 1까지 loop, 1씩 감소) { 
    // i : j가 탐색할 깊이를 지정
        for(int j = 0부터 ~ i까지 탐색하며 loop, 1씩 감소) { 
        // j : j, j+1 원소를 비교
        	if(arr[j] > arr[j+1) 
            	arr[j]와 arr[j+1]의 위치 교환
        }
    }
    return 정렬 완료된 배열
}

 

구현 (java)

public int[] solution(int n, int[] arr) { // 배열을 오름차순으로 정렬한다.
    for (int i = n-1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

 

 

시간복잡도

• 탐색, 비교 수
  • 2개의 for문 실행, 비교 횟수 최초 1회전 n-1 + 2회전 n-2 + 3회전 n-3... + n회전 1번 = n(n-1)/2 
  • 최상, 최악, 평균의 경우에도 일정하게 시행
• 교환 수
  • 1번의 교환 작업을 위해 3번의 이동이 필요(기존 원소 → 임시 원소 → 바꿀 원소)
  • 최악의 경우 (역순 정렬 되어 있는 경우) 모든 탐색, 비교에 3번의 이동 작업 소요  
  • 최상의 경우 자료 이동 및 교환이 미발생(정렬되어 있는 경우)
• 시간복잡도 :  
  • 최선 : T(n) = O(n^2) 비교, O(1) 교환
  • 평균 : T(n) = O(n^2) 비교, O(n^2) 교환
  • 최악 : T(n) = O(n^2) 비교, O(n^2) 교환

 

 

결론

• 버블 정렬 알고리즘의 장점
  • 이해와 구현이 매우 편합니다.
• 버블 정렬 알고리즘의 단점
  • 정렬 과정에서 비효율적 자료 교환 작업이 발생합니다. (해당 원소의 최종 위치임에도 정렬이 발생하는 등)
  • 버블 정렬은 무조건 느립니다. (기본적으로 최악, 최선 무관 O(n^2)의 시간복잡도)

 

 

# 구현 코드

클릭 시 깃허브로 연결됩니다.