버블 정렬 (Bubble Sort)

정렬 알고리즘

 

 

 

버블 정렬 (Bubble Sort) 

기초적인 정렬 방법 중 하나입니다. 큰 값이 끝으로 가는 것이 거품처럼 피어오른다고 해서 버블 정렬이라고 합니다. 

시간 복잡도는 O(N^2) 이고 느린 편에 속합니다. 버블 정렬은 선택 정렬, 삽입 정렬 보다 느립니다.

 

평균적인 정렬 속도 : 버블 < 선택 < 삽입

 

버블 정렬은 구현이 간단하지만 효율성이 낮은 편입니다. 각 요소가 평균적으로 여러 번 비교되고 이동해야 하기 때문입니다. 

 

 

 

동작 과정

시간 복잡도 : O(n^2) 

 

1. 비교화 교환 : 배열을 순회하면서 현재 인덱스의 값과 다음 인덱스의 값을 비교하여 오른쪽이 큰 값이 오도록 교환합니다.

2. 반복 : 이 과정을 한 번 수행하면 가장 큰 값이 배열의 끝으로 버블링(상승)하게 됩니다. 이 과정을 반복합니다.

3. 완료 조건 : 더 이상 교환이 필요없을 때 정렬을 종료합니다. 

 

이 결과 배열은 오름차순으로 정렬됩니다. 반대로 하면 내림차순 정렬이 됩니다. 

 

 

예시

초기 배열 

int[] board = {3,1,4,2,6,5}; 

3

1

4

2

6

5

 

 

index = 0 

board[0] = 3이고 board[1] = 1 이므로 오른쪽으로 큰 수를 보내기 위해 자리를 바꾼다. 

1

3

4

2

6

5

 

index = 1 

board[1] = 3, board[2] = 4 이므로 오른쪽 수가 크므로 정렬은 일어나지 않는다. 

1

3

4

2

6

5

 

index = 2 

board[2] = 4, board[3] = 2 이므로 교체 합니다.

1

3

2

4

6

5

 

index = 3 

board[3] = 4, board[4] = 6 이므로 교체하지 않습니다. 

1

3

2

4

6

5

 

index = 4

board[4] = 6, board[5] = 5 이므로 교체 합니다. 

1

3

2

4

5

6

 

 

한 번 순회한 결과 마지막 인덱스에 가장 큰 값 6이 들어오게 됩니다.

이 과정을 더 이상 교체 작업이 일어나지 않을 때까지 반복하여 정렬을 완성합니다.

1

2

3

4

5

6

 

 

 

 

Java 코드 구현

/*
버블 정렬
시간 복잡도 : O(n^2)
앞에서부터 2개씩 값을 비교하면서 작은 값을 앞으로 큰 값을 뒤로 보낸다.
한 번 선형 반복할 때 마다 마지막의 값이 정렬된 값을 가진다.
이 과정을 끝까지 반복해서 정렬을 하는 방법이다.

참고 자료 : https://www.youtube.com/watch?v=YbsQiiubO74
 */
public class BubbleSort {

  public static void main(String[] args) {
    int[] array = {3,1,5,9,4,8,7};
    printArray(array);
    bubbleSort(array);
    printArray(array);
  }

  // 버블 정렬 시작
  public static void bubbleSort(int[] array) {
    bubbleSort(array, array.length-1);
  }

  // 버블 정렬 로직 수행
  public static void bubbleSort(int[] array, int last) {
    // 마지막 인덱스가 0보다 클 때까지 반복 (마지막부터 정렬된다.)
    if(last > 0) {

      // 반복을 하면 마지막 인덱스는 정렬이 된다.
      for(int i = 1; i <= last; i++) {
        if(array[i-1] > array[i]) {
          swap(array, i-1, i);
        }
      }

      // 마지막은 정렬되었기에 last - 1을 정렬하기 위해 last - 1을 입력
      bubbleSort(array, last - 1);

    }
  }

  public static void swap(int array[], int source, int target) {
    int temp = array[source];
    array[source] = array[target];
    array[target] = temp;
  }



  public static void printArray(int[] array) {
    for(int number : array) {
      System.out.print(number + " ");
    }
    System.out.println();
  }

}

 

 

 

 

마무리

이번에는 버블 정렬을 알아보았습니다.

다음에는 선택 정렬에 대해 알아보겠습니다. 

 

 

 

참고 사이트

버블 정렬, 선택 정렬, 삽입 정렬 

https://www.youtube.com/watch?v=Bor_CRWEIXo&t=1s

 

버블 정렬 구현

https://www.youtube.com/watch?v=YbsQiiubO74