버블 정렬

이웃한 두 요소의 값을 비교하여 값으 교환을 반복하는 정렬입니다.

과정

1. (맨 뒤부터 시작) n-1번째와 n-2번째 인덱스의 값을 비교한다.
   1. n-1번째가 n-2번째보다 작으면 서로 값을 교환한다.
   2. 아닌 경우는 그냥 패스한다.
2. 0번째 인덱스까지 교환을 마쳤으면 0번째 요소가 가장 작은 값으로 정렬된다.
3. 0번째 인덱스를 제외하고 n-1부터 1번째까지 정렬을 계속한다.

package Sort;

import java.util.Scanner;

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

        int N = sc.nextInt();

        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        bubbleSort(arr);

        for (int i : arr) {
            System.out.println(i);
        }
    }

    static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = arr.length-1; j > i; j--) {
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j, j-1);
                }
            }
        }
    }

    static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = b;
        arr[b] = temp;
    }
}

시간 복잡도

첫 번째 비교는 (n-1)번, 두 번째 비교는 (n-2)번 ... 마지막 비교는 1번 발생한다.
총 교환 횟수를 계산하면 (n-1) + (n-2) + ... + 1 = n(n-1)/2이다.
따라서 시간 복잡도는 O(n^2)이다.

장점

• 코드가 직관적이다.
• 구현이 쉽다.
• Stable 정렬이다.
  • 안정 정렬 : 같은 키 값을 가지는 요소의 순서가 전후에도 유지되는 정렬.

단점

• 시간 복잡도가 O(n^2)로 오래 걸린다.