버블 정렬(Bubble Sort)

버블정렬이란?

거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법입니다. 

시간 복잡도가 $$O(n^2)$$ 로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용사용됩니다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름입니다.

 

버블정렬 동작 과정

버블정렬 소스코드

---

 

BubbleSort.java

public class BubbleSort{
  public void sort(int[] arr) {
  /*
    마지막 인덱스(arr.length)는 실행할 필요가 없기 때문에 -1을 해줍니다.
    (9번째 index까지 정렬이 되면 마지막은 당연히 정렬이 됐기 때문에)
  */
    for(int i = 0; i<arr.length-1; i++) {
     /* 
      위의 경우와 달리 -1을 해주지 않으면 Runtime Exception이 발생합니다.
      arr.length = 10
      int i = 0일 경우: if(arr[9] > arr[10])
      하지만 arr[10]은 존재 하지 않기 때문에 ArrayIndexOutOfBoundsException이 발생합니다.
      */ 
      for(int j =0; j<arr.length-1-i;j++) {
      
      //해당 값이 다음 값보다 크면, 해당 값과 다음 값을 바꿔줍니다. Swap
        if(arr[j]> arr[j+1]) {
          int temp = arr[j];
              arr[j] = arr[j+1];
              arr[j+1] = temp;
        }
      }
    }
  }
}

 

BubbleSortLauncher.java

public class BubbleSortLauncher {
  public static void main(String[] args) {
    int a[] = {7,10,1,8,3,5,2,9,4,6};
			
    BubbleSort bSort = new BubbleSort();
    bSort.sort(a);

    for(int x : a) 
      System.out.print(x + " ");
  }
}

출력

1 2 3 4 5 6 7 8 9 10

 

글에 오류가 있으면 알려주세요. 감사합니다.

 

REFERENCES

https://en.wikipedia.org/wiki/Bubble_sort