버블 정렬

지난 시간에는 선택 정렬에 대해서 알아봤습니다!!

그렇다면 이번에는 또 다른 정렬 방법중 하나인 버블 정렬에 대하여 알아볼 계획입니다

먼저 버블 정렬이란?

출처 : http://wonjayk.tistory.com/219

위의 사진과 같이 반복하는 정렬 방법입니다!!

바로 옆의 Index와 값의 교환을 N번 까지 반복하는 간단한 정렬입니다

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int[] arr = new int[scanner.nextInt()];

        for (int i = 0; i < arr.length; i++) {
            System.out.print(i + 1 + "번째 값 입력 : ");
            arr[i] = scanner.nextInt();
        }

        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j + 1] < arr[j]) {
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

위의 코드의 순서로 진행됩니다

첫번째 반복문에서는 Index의 초기값을 1로 설정한 이유는 두번째 반복문 부터 정렬이 완료된만큼 반복의 횟수를 줄여야하기 때문입니다.

전처럼 시간 복잡도를 보면 O(n^2)로 선택정렬과 같지만 버블정렬은 교환와 반복횟수가 많은 비효율적인 정렬 방식입니다.

그렇다면 어떻게 해야 좋은 정렬인거야??

라고 생각하실수 있으신데 그렇기에 다음부터는 분할과 정복을 이용한 정렬방식인 퀵정렬 (Quick Sort)에대하여 알아보겠습니다