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

'Algorithms > Sorting' 카테고리의 다른 글

Quick sort(퀵 정렬)  (0) 2017.06.24
Merge sort(병합 정렬)  (0) 2017.02.08
Selection sort(선택 정렬)  (0) 2017.02.08
Insertion sort(삽입 정렬)  (0) 2017.02.06

+ Recent posts