[정렬 알고리즘] 버블 정렬

2021.08.23 - [자료구조 & 알고리즘] - [알고리즘] 정렬

 

 

📎 버블 정렬

버블 정렬은 맨 끝단부터 이웃한 두 요소의 비교-교환의 과정을 진행하며 정렬하는 알고리즘이다.

 

버블정렬의 과정

1. 정렬되지 않은 배열의 왼쪽 혹은 오른쪽 끝단부터 시작
2. 이웃한 두 요소 비교, 정렬
3. n개의 요소일 경우 n-1번만큼 <1~2> 반복

 

설명자체로만 보면 선택 정렬과 매우 유사하다. 

단 버블 정렬의 포인트는 이웃한 두 요소를 비교-교환하는 패스 과정으로 진행된다는 점이다.

 

 

그림으로 보면 이렇다.

 

 

배열의 왼쪽 끝단에서부터 진행방향 -> 로 정렬을 수행한다. 

 

이웃하는 두 요소를 비교, 정렬한다.

 

이미 대소관계대로 정렬되어 있으니 바로 다음 요소로 넘어간다.

 

 

두 요소를 비교, 정렬한다. 앞요소보다 뒷요소가 더 작으니 둘의 자리를 바꿔준다.

 

 

(...) 이렇게 쭉 정렬을 해주다가

 

 

다른쪽 끝단에 다다르면 비교, 정렬한 값을 고정해준다.

이제 마지막 요소는 가장 큰 요소로 정렬이 완료됐다.

 

 

이 후부터는 다시 배열의 왼쪽 끝단에서부터 진행방향 -> 로 정렬을 수행하면 된다.

 

 

 

+ 각종 정렬의 과정을 눈으로 볼 수 있다.

https://visualgo.net/ko/sorting

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

 

 

버블 정렬을 자바 코드로 구현하면 이렇다

 

 

import java.util.Scanner;
 
public class BubbleSort {
    /*
     * 버블 정렬 : 버블 정렬은 맨 끝단부터 이웃한 두 요소의 비교-교환의 과정을 진행하며 정렬하는 알고리즘
     * 일반적인 버블 정렬의 시간 복잡도는 O(n²)
     * 
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("정렬할 요소의 수: ");
    
        int n = sc.nextInt();
        
        int[] arr = new int[n];
        
        //요소 입력받음
        for(int i=0; i<n; i++) {
            arr[i]=sc.nextInt();
        }
        sc.close();
                
        bubbleSort(arr, n);
                        
        System.out.println("버블 정렬 완료");
        
        //정렬 후 출력
        for(int i=0; i<n; i++) {
            System.out.print(arr[i]+" ");
        }
    }
    
    static void bubbleSort(int[] arr, int n) {        
        //n개의 요소 -> n-1번 비교
        for(int i=0; i<n-1; i++) {
            for(int j=i+1; j<n; j++) {
                if(arr[j]<arr[i]) {
                    swap(arr, j, i);
                }
            }
        }
    }
    
    //배열의 요소 두개의 위치를 바꿈 
    static void swap(int[] arr, int idx1, int idx2) {
        int tmp = arr[idx1];
        arr[idx1]=arr[idx2];    //idx1 : idx1 -> idx2
        arr[idx2]=tmp;            //idx2 : idx2 -> idx1
    }
 
}
 

 

 

버블 정렬의 성능 분석

버블 정렬의 시간 복잡도는 O(n²) 이다.

선택 정렬과 같이 n개의 요소를 받아 정렬하기 위해서는 총 n(n-1)/2 번의 수행이 필요하다.

 

코드도 간결하고 구현도 쉽지만 실제로는 잘 쓰이지 않는다고 한다.

그 이유는 쓸데 없는 SWAP 횟수가 선택 정렬보다 많아 시간이 많이 소요되기 떄문이다.

 

 

 

+참고

책정보, Do it! 자료구조와 함께 배우는 알고리즘 입문 : 네이버 책 (naver.com)

Do it! 자료구조와 함께 배우는 알고리즘 입문