[Sort] 버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)

[출처: 위키]

개념: 인접한 두개의 원소를 비교하여 자리를 교환하는 방식으로, 

첫번째 원소부터 마지막 원소까지 반복하면서 가장 큰 원소가 마지막 자리로 정렬하게 되는 방식

개념은 일단 이렇습니다...

네... 

역시 그림으로 보는게 나을듯 싶네요~

버블버블은 너무 캡쳐뜰것이 많아서

이 포스팅은 개고생의 포문이 보이는 듯 싶네요ㅜㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

그럼 시작!!

자, 이렇게 5개의 값으로 시작하것습니다~

---

1단계:

버블버블은 음...

2개씩 비교해서 큰 수를 맨 뒤로 보내는 방식입니다.

아래 그림을 통해서 1단계가 어떻게 진행되는지 보시와요

 

 

빨간 괄호 안에서 비교를 통해 어떤게 큰 수인지 찾아서 둘이 자리를 바꿉니다!!

69가 크니깐 10이랑 자리를 바꾸겠죠??

아래처럼 바뀌면서 바로 값을 또 비교하죠?? 빨간 괄호 안에서??

 

그럼 자리를 또 바꿔 줍니다.

 

또 바꿔주고... 해서 마지막 까지 왔네요

 

마지막 으로 바꿔주면!!!

빨간 괄호가 일시적으로 풀리고, 

아래와 같이 1단계가 끝이 납니다!!!

 

69라는 제일 무거운 수는 정렬 대상에서 제외 됩니다!!!

---

---

2단계:

 

자 그럼 악마의 빨간 괄호가 정렬을 위해 다시 옥죄여 오네요...

 

비교를 시작합시다!!!

오잉? 비교 해보니 30이 크니깐 가만히 있네요 10 은~

 

다음 비교로 넘어가 보니, 30 Vs 2 니깐 30이 크네용

 

바꿔 줍시다~ 그리고 비교~

 

30이 더 크므로 자리를 바꿔주면 2단계 끝이네요~~~

 

30 까지 정렬이 되었네요~

---

---

3단계:

바로 비교해보도록 하죠~

10이 더 크므로 바꿔주고 비교!

16이 더 크므로 걍 두면 

이단계는 끝이죠~

   

오호 근데 4단계까지 갈 필요가 있을까요~

운이 좋네요 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

이렇게 해서 정렬이 끝이 났네요~

 

---

이 버블 정렬의 시간 복잡도(Time Complexity)는 아래와 같습니다!

Worst, Average

 

Best 일 경우만

입니다!!

그럼 코드로 확인해 볼까요~

먼저 BubbleMain.java 입니다

'

 

package Bubble;
 
public class BubbleMain {
    public static void main(String[] args) {
        int [] arr = {69, 10, 30, 2, 16};
        
        BubbleSort.bubbleSort(arr);
    }
}
 

다음으로 BubbleSort.java

 

 
package Bubble;
 
import Selection.SelectionSort;
 
public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int arr_size = arr.length;
 
        for (int i = arr_size - 1; i > 0; i--) {
            System.out.println("\n버블 정렬 " + (arr_size - i) + "단계");
 
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    SelectionSort.swap(arr, j, j + 1);
                }
                SelectionSort.printArr(arr);
 
            }
        }
    }
 
}
 

기존 SelectionSort 때 만들었던 swap 과 printArr를 그대로 이용헀습니다.

결과는 아래와 같습니다~