[Algorithm] 버블 정렬(Bubble Sort)

버블 정렬 (Bubble Sort)

■ 정의

버블 정렬은 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘으로
단순 교환 정렬(straight exchange sort)이라고도 함

 

■ 사용 예

 - 총 3번의 Pass를 통해 [1, 3, 4, 6, 7]로 오름차순 정렬을 만들 수 있음

 - 사진에서는 모든 비교과정을 표시하였지만, 이미 정렬된 수와의 비교는 굳이 진행하지 않아도 됨

 

■ 장점

 - 구현이 매우 간단하고, 소스코드가 직관적

 - 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않음

      => 제자리 정렬(in-place sorting)

 - 안정 정렬(Stable Sort)

 

■ 단점

 - 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적

 - 정렬 되어있지 않은 원소가 정렬 되었을 때 자리로 가기 위해, 교환 연산(swap)이 많이 일어남

 

■ Code

import java.util.Scanner;

public class BubbleSort {
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    static void bubbleSort(int[] a, int n){
        for(int i = 0; i < n - 1; i++){
            for(int j = n - 1; j > i; j--)
                if(a[j - 1] > a[j])
                    swap(a, j - 1, j);
        }
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        System.out.println("버블 정렬(버전 1)");
        System.out.print("요솟수: ");
        int nx = sc.nextInt();
        int[] x = new int[nx];

        for(int i = 0; i < nx; i++){
            System.out.print("x[" + i + "]: ");
            x[i] = sc.nextInt();
        }

        bubbleSort(x, nx);

        System.out.println("오름차순으로 정렬했습니다.");
        for(int i = 0; i < nx; i++)
            System.out.println("x[" + i + "]= " + x[i]);
    }
}