Bubble_Sort(거품 정렬)+JAVA로 구현

 

➡️Bubble_Sort란?

• 서로 인접한 두 원소를 검사하여 절영하는 알고리즘 
• Bubble_Sort는 데이터를 비교하면서 찾기 때문에 비교정렬이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 제자리 정렬이기도 하다

 

➡️Bubble_Sort의 장단점 

장점

• 메모리 소비가 적다.
• 구현이 비교적 쉬운편이다.

단점

• 교환 과정이 많아 시간이 많이 소요된다.
• Bubble_Sort의 평균 시간복잡도가 O(N^2)이다. 효율성이 떨어진다.

 

 

➡️Bubble_Sort의 과정 

1. 앞에서부터 현재 원소와 다음의 원소를 비교한다.
2. 현재 원소가 다음 원소보다 크면 원소를 교환한다.
3. 다음 원소로 이동하여 앞 과정을 반복한다.

위 과정은 아래 그림과 같다.

출처:https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

각 회전은 배열의 크기 -1만큼 진행된다.

각 회전별 비교횟수는 배열크기에서 회전횟수를 뺀 만큼 비교한다.

 

 

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

 

 

💻구현하기💻

public class BubbleSort {
 
    public static void bubble_sort(int[]arr){
        bubble_sort(arr, arr.length);
    }
 
    
    private static void bubble_sort(int[]arr,int size){
 
           //회전은 배열 크기 - 1 만큼 진행됨
        for(int i =1; i<size; i++){
 
            // 각 회전별 비교횟수는 배열 크기의 현재 회전을 뺀 만큼 비교함
            for (int j = 0; j<size -i; j++){
                
                /*
                 *  현재 원소가 다음 원소보다 클 경우
                 *  서로 원소의 위치를 교환한다.
                 */
 
                if(a[j]> arr[j+1]){
                    swap(arr, j ,j+1);
                }
 
            }
        }
    }
 
    private static void swap(int []arr ,int i, int j){
        int temp =arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
 

 

---

REFERENCE

• https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html
• https://st-lab.tistory.com/195?category=892973
• https://en.wikipedia.org/wiki/Bubble_sort