ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 버블정렬
    카테고리 없음 2023. 4. 18. 12:31

    버블정렬

    • 거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

    6 2 7 8 1

    • 6보다 2이 작기 때문에 교환

    2 6 7 8 1

    • 6보다 7이 크기 때문에 교환 하지 않는다.

    2 6 7 8 1

    • 7보다 8이 크기 때문에 교환 하지 않는다.

    2 6 7 8 1

    • 8보다 1이 작기 때문에 교환

    2 6 7 1 8

    • 다시 처음으로 돌아가 반복 한다.
    private static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
    

    조금 나은 버블정렬

    버블 정렬은 각각 한번씩 i랑 i+1 을 비교하므로 만약 한번도 교환이 일어 나지 않았다면 정렬이 된 상태다. 그걸 이용해서 조금 더 나은 버블정렬을 구현할 수 있다.
    private static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            boolean checked = false;
            for (int j = 0; j < arr.length - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    checked = true;
                }
            }
            if(!checked){
                break;
            }
        }
    }
    

    댓글

Designed by Tistory.