버블 정렬 코드로 구현 하기 - 자바

버블 정렬( - 整列, 영어: bubble sort, sinking sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 {\displaystyle O(n^{2})} 로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 양방향으로 번갈아 수행하면 칵테일 정렬이 된다.

위키백과에서는 버블 정렬을 위와 같이 설명하며, 좋은 예제와 수도 코드를 보여준다.

www.acmicpc.net/problem/2750

2750번: 수 정렬하기

백준의 위 문제를 버블 정렬을 활용하여 구현해보았다. 코드는 아래와 같다.

버블정렬의 구현 자체는 상당히 쉽지만 직접 구현하고 평소에 정리해놓지 않는다면 긴장이 많이 되는 면접과 같은 상황에서는 바로 풀이를 떠올리지 못할 수도 있을 것 같다.

import java.util.Scanner;

public class boj2750 {

    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();
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(j, j + 1, arr);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            System.out.println(arr[i]);
        }

    }

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

}