[알고리즘] 정렬 - 버블정렬

버블정렬이란

• 현재 인덱스와 다음 인덱스를 일일히 비교해가면서 원하는 정렬방향(정순/역순)에 맞게 값을 정렬하는 것이다.
• 모든 아이템들을 순회하고, 정렬이 필요하면 자리를 바꾼다.

동작원리

1. 배열의 가장 처음 인덱스부터 기준이 되는 하나의 아이템을 선정.
2. 그 다음 이 아이템으로 뒤에 인접한 아이템과 값을 비교 및 교환
3. 해당 아이템이 모든 아이템을 순회했을 경우 1번 동작부터 반복

이렇게하면 모든 아이템들을 처음부터 끝까지 순회하면서 인접한 값들을 비교할 수 있다.

복잡도

버블 정렬의 시간 복잡도는 O(N²)이며 Worst, Average, Best 모두 동일.일일히 비교해야하기 때문에 연산 수가 많아 정렬 알고리즘 중에서 가장 느리고 효율성이 떨어지는 정렬 방식입니다.

코드

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 1, 6, 88, 2, 5, 9, 312, 99}; // 길이가 9인 배열 arr

        // 버블정렬 1 -> 정순
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }


        // 버블정렬 2 -> 역순
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] < arr[j + 1]) {
                    int tmp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
}
// 정순 출력 >> 1 2 3 5 6 9 88 99 312  
// 역순 출력 >> 312 99 88 9 6 5 3 2 1 

[출처] : https://aiday.tistory.com/53#:~:text=Bubble%20Sort%2C%20%EB%B2%84%EB%B8%94%20%EC%A0%95%EB%A0%AC,Average%2C%20Best%20%EB%AA%A8%EB%91%90%20%EB%8F%99%EC%9D%BC%ED%95%A9%EB%8B%88%EB%8B%A4.