Bubble 정렬 알고리즘 Java: 배열 정렬 프로그램 및 예제

Bubbl전자 정렬?

BubbleSort는 배열의 첫 번째 요소와 다음 요소를 비교하는 간단한 비교 기반 정렬 알고리즘입니다. 현재 요소의 크기가 다음 요소보다 크면 두 요소의 위치를 ​​바꿉니다. 이와 같은 방식으로 배열의 모든 요소를 ​​순회합니다.

이 알고리즘은 정렬되지 않은 영역에서 가장 큰 값이 마치 물 표면으로 떠오르는 거품처럼 점진적으로 최종 위치로 올라가는 모습에서 이름을 따왔습니다. 첫 번째 과정이 완료되면 가장 큰 요소가 마지막 인덱스를 차지하게 됩니다. 두 번째 과정에서는 두 번째로 큰 요소가 그 자리에 고정되고, 배열이 완전히 정렬될 때까지 이 과정이 반복됩니다.

이 글에서는 다음을 만들겠습니다. Java 구현할 프로그램 Bubbl정렬을 실행하세요. 프로그램 논리를 이해하는 데 도움이 될 코드 출력 결과를 확인하고, 이어서 나오는 최적화된 버전과 복잡성 분석 결과를 검토하세요.

어떻게해야합니까? Bubbl정렬 알고리즘이 제대로 작동하나요?

Bubbl정렬은 배열을 반복적으로 순회하면서 작동합니다. 각 순회는 첫 번째 인덱스부터 현재 정렬되지 않은 영역의 끝까지 이동하면서 인접한 값을 비교하고 교환합니다.ping 값이 잘못된 순서로 나타날 때마다 해당 값들이 제거됩니다. 가장 큰 잔여 값이 항상 정렬되지 않은 영역의 맨 오른쪽으로 이동하기 때문에, 매 단계마다 영역이 정확히 한 위치씩 줄어듭니다.

전체 과정은 반복 가능한 네 단계로 나눌 수 있습니다.

1. 비교: 인덱스 j-1에 있는 요소와 인덱스 j에 있는 요소를 비교합니다.
2. 교환: 왼쪽 요소가 오른쪽 요소보다 크면 임시 변수를 사용하여 두 값을 서로 바꿉니다.
3. 전진: 오른쪽으로 한 칸 이동하고 정렬되지 않은 영역의 끝에 도달할 때까지 이 과정을 반복합니다.
4. 반복: 요소가 하나 줄어든 영역에 대해 새로운 패스를 시작하고, n-1번의 패스가 완료되거나 패스에서 더 이상 요소 교환이 발생하지 않으면 종료합니다.

아래 표 trac이 예시는 이 페이지 뒷부분의 프로그램에서 사용되는 샘플 배열 {860, 8, 200, 9}입니다. 이 배열은 매 단계가 끝날 때마다 어떤 값이 최종 위치에 정착하는지 정확하게 보여줍니다.

세 번째 단계에서는 비교는 수행하지만 스왑은 수행하지 않는다는 점에 유의하십시오. 최적화된 구현은 이러한 조건을 감지하고 즉시 중지하는데, 이는 이 알고리즘에 적용할 수 있는 가장 중요한 개선 사항입니다.

Bubbl정렬 알고리즘 의사 코드

작성하기 전에 Java 구문을 사용하면 언어에 구애받지 않는 의사 코드로 논리를 표현할 수 있습니다. 아래 버전에는 조기 종료 플래그가 포함되어 있어 기존 동작과 최적화된 동작 모두를 지원합니다.

procedure bubbleSort(array A, integer n)
    for i from 0 to n - 2 do
        swapped := false
        for j from 1 to n - i - 1 do
            // compare the adjacent pair
            if A[j - 1] > A[j] then
                swap A[j - 1] and A[j]
                swapped := true
            end if
        end for
        // no swap in a full pass means the array is sorted
        if swapped = false then
            break
        end if
    end for
end procedure

외부 루프는 반복 횟수를 제어하고, 내부 루프는 단일 반복 내에서의 비교 횟수를 제어합니다. 내부 루프의 상한은 n – i – 1인데, 이는 마지막 i개 위치에 이미 최종 값이 저장되어 있기 때문입니다.

Java 프로그램 시행 Bubble 정렬

다음 프로그램은 정수 배열을 오름차순으로 정렬합니다. 반복문 안에 추가적인 출력문을 넣은 것은 의도적인 것으로, 단계별 실행 과정을 읽기 쉽게 하기 위함입니다. trace는 초보자가 스왑이 어떻게 누적되는지 이해하는 가장 빠른 방법입니다.

package com.guru99;

public class BubbleSort {

    public static void main(String[] args)
    {
        int arr[] = {860, 8, 200, 9};

        System.out.println("---Array BEFORE Bubble Sort---");

        printArray(arr);

        bubbleSort(arr); //sorting array elements using bubble sort

        System.out.println("---Array AFTER Bubble Sort---");

        printArray(arr);

    }

    static void bubbleSort(int[] array)
    {
        int n = array.length;
        int temp = 0;
        for(int i = 0; i < n; i++) // Looping through the array length
        {   System.out.println("Sort Pass Number " + (i + 1));
            for(int j = 1; j < (n - i); j++)
            {
                System.out.println("Comparing " + array[j - 1] + " and " + array[j]);
                if(array[j - 1] > array[j])
                {
                    //swap elements
                    temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    System.out.println(array[j] + " is greater than " + array[j - 1]);
                    System.out.println("Swapping Elements: New Array After Swap");
                    printArray(array);
                }

            }
        }

    }

    static void printArray(int[] array){

        for(int i = 0; i < array.length; i++)
        {
            System.out.print(array[i] + " ");
        }
        System.out.println();

    }
}

출력:

---Array BEFORE Bubble Sort---
860 8 200 9
Sort Pass Number 1
Comparing 860 and 8
860 is greater than 8
Swapping Elements: New Array After Swap
8 860 200 9
Comparing 860 and 200
860 is greater than 200
Swapping Elements: New Array After Swap
8 200 860 9
Comparing 860 and 9
860 is greater than 9
Swapping Elements: New Array After Swap
8 200 9 860
Sort Pass Number 2
Comparing 8 and 200
Comparing 200 and 9
200 is greater than 9
Swapping Elements: New Array After Swap
8 9 200 860
Sort Pass Number 3
Comparing 8 and 9
Sort Pass Number 4
---Array AFTER Bubble Sort---
8 9 200 860

Code 설명: The 버블 정렬 이 메서드는 배열을 참조로 받기 때문에 호출자는 반환 값 없이 정렬된 결과를 볼 수 있습니다. 변수 임시직 세 줄의 스왑 과정에서 하나의 값만 유지되므로 알고리즘은 O(1)의 추가 메모리만 필요로 합니다. n – i 내부 루프 조건은 꼬리 부분의 이미 정렬된 위치가 다시 방문되지 않도록 보장합니다.

최적화 Bubble 정렬 프로그램 Java

위 프로그램은 배열이 일찍 정렬되더라도 항상 n-1번의 반복 작업을 수행합니다. 부울 플래그 하나만 추가하면 이러한 비효율성을 해결할 수 있습니다. 만약 한 번의 반복 작업에서 스왑이 한 번도 발생하지 않으면 배열이 정렬된 것으로 간주하여 외부 루프를 즉시 종료할 수 있습니다.

package com.guru99;

public class OptimizedBubbleSort {

    public static void main(String[] args) {
        int arr[] = {5, 12, 33, 47, 58};
        bubbleSort(arr);
        System.out.println(java.util.Arrays.toString(arr));
    }

    static void bubbleSort(int[] array) {
        int n = array.length;
        int passes = 0;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 1; j < n - i; j++) {
                if (array[j - 1] > array[j]) {
                    int temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    swapped = true;
                }
            }
            passes++;
            // Early exit: the array is already sorted
            if (!swapped) {
                break;
            }
        }
        System.out.println("Passes executed: " + passes);
    }
}

출력:

Passes executed: 1
[5, 12, 33, 47, 58]

입력 배열이 이미 정렬되어 있었기 때문에 최적화된 버전은 네 번의 패스 대신 한 번의 패스로 완료되었습니다. 거의 정렬된 데이터의 경우 이러한 변경으로 인해 작업 부하가 2차 함수가 아닌 거의 선형 함수로 바뀌는데, 이것이 주요 원인입니다. BubbleSort는 실제 코드에서 여전히 종종 나타납니다.

시간 복잡도와 공간 복잡도 Bubble 정렬

복잡도는 입력 크기가 커짐에 따라 실행 시간이 어떻게 증가하는지를 나타냅니다. Bubbl최적화되지 않은 버전에서 비교 횟수를 정렬하면 n(n-1)/2로 고정되어 이차 함수 클래스에 확실히 속하게 됩니다.

모든 교환이 원래 배열 내부에서 이루어지고 임시 변수는 하나만 사용되기 때문입니다. BubbleSort는 O(1) 보조 공간을 갖는 제자리 정렬 알고리즘입니다. 또한 안정 정렬이므로 동일한 키를 가진 두 레코드는 정렬 후 원래의 상대적 순서를 유지합니다.

장점과 단점 Bubble 정렬

양측의 입장을 모두 이해하면 해당 알고리즘이 적절한 선택인지, 아니면 교체해야 하는지를 판단하는 데 도움이 됩니다.

장점

• 간단: 논리는 대략 열 ​​줄 정도로 간결하게 표현할 수 있어 면접 상황에서도 정확하게 작성하기 쉽습니다.
• 현장 작업: 보조 배열이 할당되지 않으므로 입력 크기에 따라 메모리 사용량이 증가하지 않습니다.
• 안정: 동일한 키는 원래 순서를 유지하며, 이는 보조 필드를 기준으로 레코드를 정렬할 때 중요합니다.
• 조기 퇴장 감지: swapped 플래그는 한 번의 패스로 이미 정렬된 배열을 나타냅니다.

단점

• 이차 함수적 성장: 10,000개의 요소를 정렬하려면 최악의 경우 거의 50천만 번의 비교가 필요합니다.
• 과도한 글쓰기: 이 알고리즘은 선택 정렬보다 훨씬 더 많은 스왑을 수행하는데, 선택 정렬은 쓰기 작업 속도가 느려 메모리 사용량이 많습니다.
• 확장성이 떨어짐: 실제 운영 환경에서는 퀵 정렬, 병합 정렬 또는 내장된 Arrays.sort 메서드가 거의 항상 선호됩니다.

Bubble 정렬 vs 기타 정렬 Algorithms

아래 표를 비교하면 Bubbl초보자들이 다음에 배우게 될 정렬 기법들을 사용하여 정렬해 보세요. 그러면 각 기법이 어떤 부분에서 가장 효과적인지 정확히 알 수 있습니다.

Bubble 정렬과 삽입 정렬은 최상의 경우 시간 복잡도가 선형이지만, 삽입 정렬은 부분적으로 정렬된 데이터에서 스왑 횟수가 더 적습니다. 선택 정렬은 항상 정확히 n-1번의 스왑을 수행하므로 시간 복잡도는 선형입니다.trac쓰기 비용이 많이 드는 경우 효율적이지만 안정성을 희생해야 합니다. 수백 개 이상의 요소를 가진 배열의 경우 퀵 정렬이나 힙 정렬이 적합합니다.

여기서 사용된 배열 순회 패턴에 익숙해지면, 동일한 반복문 구조가 다음과 같은 많은 고전적인 연습 문제에서도 나타납니다. 피보나치 수열 Java 그리고 Java 회문 프로그램. Rev이잉 Java 배열 그리고 더 넓은 Java 지도 시간 이는 이 알고리즘이 의존하는 기본 원리를 강화할 것입니다.

자주 묻는 질문