버블 정렬(Bubble Sort)

동빈나 실전 알고리즘 강좌(Algorithm Programming Tutorial) 참고

https://www.youtube.com/playlist?list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz

실전 알고리즘 강좌 (Algorithm Programming Tutorial)

버블 정렬(Bubble Sort)

옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내자

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

시간 복잡도는 선택 정렬과 같으나 더 비효율적 => 선택 정렬은 가장 작은 하나의 값을 찾아서 맨 앞의 값과 한 번씩 교환하지만 버블 정렬의 경우 서로 값을 교환하는 코드가 더 많이 실행되기 때문

정렬 알고리즘 중 가장 느린 알고리즘 = 버블 정렬 알고리즘

 

첫 번째 요소부터 마지막 요소까지 서로 양옆을 교환하면 최종적으로 마지막 요소가 가장 큰 값이 됨

따라서 그 다음부터는 그 값을 제외하고 양옆을 교환해 주면 됨

점점 비교할 요소가 -1 -2 -3으로 줄어듦

 

package algorithmProgramming;

public class BubbleSort {

    public static void main(String[] args) {

        int[] numbers = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };

        for (int i = 1; i < numbers.length; i++) { 
            for (int j = 0; j < numbers.length - i; j++) { 
                if (numbers[j] > numbers[j + 1]) {
                    int tmp = numbers[j]; 
                    numbers[j] = numbers[j + 1]; 
                    numbers[j + 1] = tmp; 
                }
            }
        }

        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }

    }

}

 

오름차순 정렬 완료