버블 정렬 (Bubble Sort) + Java 구현 코드

 

버블정렬

개요

인접한 배열의 두 수를 선택해, 그 두 수가 정렬되어 있지 않다면 두 수를 정렬하는 방식

 

개념

루틴: 인덱스 0부터 n-1까지 순차적으로 n번 비교하고, 만약 정렬이 필요하다면 Swapping함

루틴 1번이 돌 때 1개의 숫자가 정렬됨 (가장 큰 수가 n(가장 마지막)에 고정되고, 그 다음으로 큰 수가 n-2 자리에...)

 

시간 복잡도

O(n^2)

-> 배열의 크기가 n일 때 n번 비교(&스와핑)

 

---

BubbleSort.java
|-- main(String[] args)
|-- void bubbleSort()

public class BubbleSort {
    public static void main(String[] args) {
        bubbleSort();
    }

    static void bubbleSort() {
        int[] arr = createIntArray(10000);

        long startTime = System.currentTimeMillis();
        // 현재 시간 기준의 Milli seconds

        for (int i=0; i<arr.length; i++) {
            for (int j=0; j<arr.length-1; j++) {
                if (arr[j] > arr[j+1]) {    // 부등호 뒤집으면? 내림차순
                    swap(arr, j, j+1);
                }
            }
        }

        long endTime = System.currentTimeMillis();

        System.out.println(Arrays.toString(arr));
        System.out.printf("소요시간: %s 밀리초\n", endTime - startTime);
    }
}

 

유틸

TestUtil.java
|-- int[] createIntArray(int size)
|-- void swap(int[] arr, int i, int j)

import java.util.Random;

public class TestUtil {
    
    public static int[] createIntArray(int size) {
        int[] arr = new int[size];
        Random random = new Random();

        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(size);
        }
        return arr;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}