거품 정렬(Bubble Sort)에 대해 알아보자 (feat. JAVA)

이 거품 아니다.

 

 

거품 정렬(Bubble Sort)?

 

 

1. 거품 정렬은 두 인접한 원소를 검사하여 반복, 순차적으로 정렬하는 방법이다. ( 비교 정렬 )

2. 거품 정렬은 선택 정렬과 함께 정렬 알고리즘에서 최악의 성능을 보여준다. ( 시간 복잡도 O(N＾²) )

3. 또한 거품 정렬은 제자리(in-place)정렬이기 때문에 추가적인 메모리 사용량을 필요로 하지 않는다. 값을 바꾸기 위한 임시 공간이 필요하지만 정렬 알고리즘에서 정렬 항목 외에 O(1)개의 메모리만 필요한 것은 제자리 정렬로 간주한다.

4. 단순한 원리로 작동하기 때문에 구현이 굉장히 쉽다.

 

종합적으로 구현하기 쉽고 단순하나 성능이 너무 좋지 않기 때문에 실무에서 사용하면 기다리다가 혼자 사무실을 지키게 될 수도 있는 알고리즘이다.

 

 

 

 

거품 정렬의 예시

 

 

 

 

 

 

사실 이 하나의 gif 이미지에 거품 정렬의 모든 것이 담겨있다..

하지만 속도가 너무 빨라 처음 보면 어질어질할 수 있으니 고정된 이미지로 먼저 보고 다시 한 번 확인해보자.

 

 

 

(상 -> 하, 우 -> 좌 순서)

첫 정렬 시에는 전체 배열의 크기 N-1번 비교하고, 이후 정렬된 값이 늘어날수록 비교 수가 1씩 감소하며 숫자가 둘만 남았을 때 비로소 비교를 멈춘다. 너무 단순한 알고리즘이라 아마도 바로 이해가 될 것이다.

 

 

 

 

코드 예시

 

 

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

N개의 수가 주어졌을 때 해당 수의 배열을 오름차순으로 정렬하는 코드를 작성하는 문제이다.

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 배열의 크기를 정하는 입력값
        int[] arr = new int[N];

        for (int i=0; i<N; i++) { // 배열에 해당 수들을 추가
            arr[i] = Integer.parseInt(br.readLine());
        }

        for (int i=0; i<arr.length-1; i++) { 
            for (int j=0; j<arr.length-1-i; j++) { // 매 반복마다 반복 횟수가 줄어든다
                if (arr[j]>arr[j+1]) { // 만약 우측의 값이 좌측보다 작다면 위치를 바꾼다
                    int temp = arr[j]; // swap이 없기 때문에 별도 임시 변수를 만들어줘야 한다.
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }

        for (int num : arr) {
            System.out.println(num);
        }
        }
    }

 

 

쩝.. 정말 단순무식하게 비교하는 알고리즘이기 때문에 코드가 굉장히 직관적이다.

이 단순한 정렬을 조금이나마 개선하는 방법이 있다.

 

예를 들어 1 , 2 , 3 , 24 , 9, 5라는 수의 배열을 오름차순으로 정렬한다고 생각해보자.

24와 9만 뒤로 보내고나면 더이상 비교 작업을 수행할 이유가 없다.

 

이처럼 이미 모든 정렬이 끝났다면 비교 작업을 멈추게 만들어주는 것이다.

boolean 변수 하나만 더 만들어주면 되기 때문에 간단하다.

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        for (int i=0; i<arr.length-1; i++) {
        boolean isChanged = false; // 정렬 작업이 수행되고 있는지 체크
            for (int j=0; j<arr.length-1-i; j++) {
                if (arr[j]>arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    isChanged = true; // 정렬 작업이 수행되었다면 true
                }
            }
            if (!isChanged) { break; } // 배열을 순회하며 단 한 번도 반복되지 않았다면 비교를 멈춘다
        }

        for (int num : arr) {
            System.out.println(num);
        }
        }
    }

 

 

 

정렬 방식 자체의 한계는 어쩔 수 없지만 조금이나마 효율적이게 수 있다.