Bubble sort(거품? 정렬)

Bubble sort(거품? 정렬)

- 1원칙: i, i +1의 자리를 비교하여 뒤의것이 작다면 자리를 교환한다.

- 2원칙: 0 ~ n -1 이렇게 n개까지 돌리고 교환된 적이 있다면 다시 0부터 돌린다.(loop)

          loop: 앞이나 뒤로 계속 이동해야 할 수 있어서...

- 3원칙: 교환된 것이 없다면 모든것이 정렬완료된 상태이므로 loop를 종료한다.

0부터 n까지 계속 비교하기 때문에 

Best case: O() : 정렬이 거의 다 되어있는 상태에서...

Worst case: O() : 역순정렬된 상태 일때...

이미 정렬된 상태라고 예상될때 쓰는게 좋지 않을까 함

public class BubbleSort {

    public void sort(Comparable[] array) {

        boolean isCompleted = true;

        while (isCompleted) {

            isCompleted = false;

            for (int i = 0; i + 1 < array.length; i++) {

                if (array[i].compareTo(array[i + 1]) > 0) {

                    Comparable temp = array[i];

                    array[i] = array[i + 1];

                    array[i + 1] = temp;

                    isCompleted = true;

                }

            }

        }

    }

}

Reference:

- https://en.wikipedia.org/wiki/Bubble_sort