[Sort] 버블 정렬(Bubble Sort)

버블 정렬은 정렬하면 가장 먼저 떠오르는 간단한 정렬방법이다.

버블 정렬은 이름 그대로 앞에서부터 순서대로 비교하고 교환하는 과정이 마치 거품이 일어나는 모습에

비유되어 버블 정렬이라는 이름이 지어진 것이다.

그만큼 이해하기도, 구현하기도 쉽고 간단하다. 물론 구현이 쉬운만큼 성능적으로는 매우 떨어진다.

만약, 오름차순으로 정렬을 하려고 한다. 아래와 같은  배열 6 1 2 3 4 5이 있다면, 

위 그림에서 보듯, 버블 정렬은 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다.

두 개의 데이터를 비교하여, 정렬순서상 위치가 바뀌어야 할 경우에는 두 데이터의 위치를 바꿔나간다.

즉, 정렬의 우선순위가 가장 낮은, 제일 큰 값을 맨 뒤로 보내는 것을 반복하는게 바로 이 정렬의 핵심이다.

위 사진의 경우에는 6만 보내면 해결됐지만, 만약 6 5 4 3 2 1이라면 모든 값을 비교 후 이동함으로 최악이다.

먼저, 하나의 요소와 그 뒷 요소를 비교해서 앞이 뒤보다 크다면 앞.뒤의 위치를 변경하는 코드를 구현하면,

if( arr[j] > arr[j+1){ tmp = arr[j]; arr[i] = arr[j+1]; arr[j+1] = tmp; }

import java.util.Scanner;

public class Main {
 public static void main(String[] args) {

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

  for (int i = 0; i < bubbleSort.length; i++) {
   System.out.print (bubbleSort[i]+" ");
  }  // 6 3 4 5 2 1 출력
  

BubbleSort(bubbleSort,bubbleSort.length); 

  System.out.println();
  for (int i = 0; i < bubbleSort.length; i++) {
   System.out.print (bubbleSort[i]+" ");
  }  // 1 2 3 4 5 6 출력
 }

 private static void BubbleSort(int[] bubbleSort, int length) {
  
  int temp;
  
  for (int i = 0; i < length-1; i++) {
   for (int j = 0; j < (length-i)-1; j++) {
    if(bubbleSort[j] > bubbleSort[j+1]){
         temp = bubbleSort[j];
         bubbleSort[j] = bubbleSort[j+1];
         bubbleSort[j+1] = temp;
    }
   }
  }
 }
}

위에서 BubbleSort()메소드가 바로 버블 정렬 알고리즘을 구현한 코드이다.

++추가적으로 다른 방법으로 버블 정렬을 구현하였다. 이것이 더욱 간단하지 않을까싶다.

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int num1 = scanner.nextInt();

int[] arr = new int[num1];

int flag = 0, temp = 0;

for (int i = 0; i < arr.length; i++) {

arr[i] = scanner.nextInt();

}

for (int i = num1 - 2; i >= 0; i--) {

for (int j = 0; j <= i; j++) {

if (arr[j] > arr[j + 1]) {

temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

}

}

for (int j = 0; j < arr.length; j++) {

System.out.print(arr[j]);

}

}

}

입력 :

7

2 5 11 24 8 1 9

출력 :

1 2 5 8 9 11 24 

성능

정렬 알고리즘의 성능은 두 가지를 근거로 판단한다.  

1. 비교 횟수  : 두 데이터간의 비교연산의 횟수

2. 이동 횟수  : 위치의 변경을 위한 데이터의 이동 횟수.

최선의 경우는 배열이 이미 완벽하게 정렬되어 있는 상태 - 데이터의 이동이 한 번도 일어나지 않음

최악의 경우에는 내림차순.. 즉, 역순으로 정렬되어 있을 경우 비교횟수 = 이동횟수.. 

버블 정렬은 빅오 오브 n^2 (= O(n^2))이므로 매우 좋지 않은, 실제로 사용하지 부담스러운 성능을 보인다.

하지만, 코드가 간단하게 구현할 수 있기 때문에 간단한 배열의 정렬의 경우에는 이 방식을 사용해도 무방하다..

이상으로 버블 정렬에 대한 정리를 마치도록 하겠다. 다음번에는 선택 정렬!!!