버블 정렬(bubble sort)

1. 비효율적이지만 코드가 단순하기 때문에 자주 사용된다
2. 최악의 경우 역순으로 정렬되어 있는 리스트를 정렬하려고 할 때 O(n2)의 성능을 낸다.
3. 순환할 때마다 하나의 원소만 변경하기때문이다.
4. 이미 정렬되어 있는 경우 O(n)의 성능을 낸다.
5. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 
6. 양방향으로 번갈아 수행하면 칵테일 정렬이 된다.

public class SortTest {
    @Test
    void bubble() {
        int[] array = new int[]{5,9,3,1,2,8,4,7,6};
//        int[] array = new int[]{1,2,3,4,5,6,7,8,9};
//        int[] array = new int[]{9,8,7,6,5,4,3,2,1};

        int temp;

        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 1; j < array.length - i; j++) {
                if (array[j] < array[j - 1]) {
                    temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                }
            }
        }

        assertArrayEquals(array, new int[]{1,2,3,4,5,6,7,8,9});
    }
}

 

시작 [5, 9, 3, 1, 2, 8, 4, 7, 6]

1. [5, 3, 1, 2, 8, 4, 7, 6, 9]
2. [3, 1, 2, 5, 4, 7, 6, 8, 9]
3. [1, 2, 3, 4, 5, 6, 7, 8, 9]

시작 [9, 8, 7, 6, 5, 4, 3, 2, 1]

1. [8, 7, 6, 5, 4, 3, 2, 1, 9]
2. [7, 6, 5, 4, 3, 2, 1, 8, 9]
3. [6, 5, 4, 3, 2, 1, 7, 8, 9]
4. [5, 4, 3, 2, 1, 6, 7, 8, 9]
5. [4, 3, 2, 1, 5, 6, 7, 8, 9]
6. [3, 2, 1, 4, 5, 6, 7, 8, 9]
7. [2, 1, 3, 4, 5, 6, 7, 8, 9]
8. [1, 2, 3, 4, 5, 6, 7, 8, 9]

시작 [1, 2, 3, 4, 5, 6, 7, 8, 9]

1. [1, 2, 3, 4, 5, 6, 7, 8, 9]