버블 정렬 (Bubble Sort)

▶ 정의

버블 정렬은 두 인접한 데이터의 크기를 비교해 정렬하는 알고리즘이다. Selection Sort와 유사한 알고리즘이고, 시간복잡도는 O(n²)으로 다른 정렬 알고리즘보다 속도가 느린편이다.

 

▶ 버블 정렬 과정

 

1. 비교 연산이 필요한 루프 범위를 설정함
2. 인접한 데이터 값을 비교함
3. swap 조건에 부합하면  swap 연산을 수행
4. 루프 범위가 끝날 때까지 2~3 반복
5. 정렬 영역을 설정함. 다음 루프를 실행할 때는 이 영역을 제외함
6. 비교 대상이 없을 때까지 1~5를 반복

 

---

백준 버블 예제 1 - 2750번 수 정렬하기

 

▶ 문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

▶ 코드

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        for(int i=0; i<N; i++){
            A[i] = sc.nextInt();
        }
        for(int i=0; i<N-1; i++){
            for(int j=0; j<N-1-i; j++){
                if(A[j] > A[j+1]){
                    int tmp = A[j];
                    A[j]= A[j+1];
                    A[j+1] = tmp;
                }
            }
        }
        for(int i=0; i<N; i++){
            System.out.println(A[i]);
        }
    }
}

 

 

▶ 풀이

 

백준 2750번은 버블정렬의 아주 기초 문제였다.

자바는 sort() 메서드를 사용하면 쉽게 정렬을 할 수 있지만 오늘은 버블 정렬에 대해 알아보기위해 직접 구현해봤다!

 

---

 

백준 버블 예제 2 - 1377번 버블 소트 프로그램 1

 

▶ 문제

버블 소트 알고리즘을 다음과 같이 C++로 작성했다.

bool changed = false;
for (int i=1; i<=N+1; i++) {
    changed = false;
    for (int j=1; j<=N-i; j++) {
        if (A[j] > A[j+1]) {
            changed = true;
            swap(A[j], A[j+1]);
        }
    }
    if (changed == false) {
        cout << i << '\n';
        break;
    }
}

위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.

위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.

 

▶ 코드

import java.io.*;
import java.util.Arrays;

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());
        B[] arr = new B[n];
        for (int i = 0; i < n; i++) {
            arr[i] = new B(Integer.parseInt(br.readLine()), i);
        }
        br.close();
        
        Arrays.sort(arr);
        int Max =0;
        
        for(int i=0; i<n; i++){
            if(Max < arr[i].idx-i)
                Max = arr[i].idx - i;
        }
        System.out.println(Max+1);
    }
}

class B implements Comparable<B>{
    int val;
    int idx;
    
    public B(int val, int idx){
        super();
        this.val = val;
        this.idx = idx;
    }
    @Override
    public int compareTo(B o){ //val 기준 오름차순 정렬하기
        return this.val - o.val;
    }
}

 

▶ 풀이

으아아ㅏㅏ 문제 난이도가 어려웠다... 심지어 찾아보면서 구현을 했는데도 이렇게 많이 수정을 했다...

컴파일 에러, 런타임 에러, 메모리 초과,,, 

 

이 문제는 버블정렬의 swap이 한 번도 일어나지 않는! 즉 모든 정렬이 끝났을 때가 언제인지를 출력하면 되는 것인데 데이터를 봤을 때 오른쪽에서 왼쪽으로 가장 많이 이동한 값을 찾으면 이 문제를 해결할 수 있었다!

컴파일에러는 선언하지 않은것을 불러와서 오류 났고 런타임 에러는 배열에 null 값이 있어서 오류가 났다. 그리고 메모리 초과는 Scanner를 사용해서 데이터를 받아왔는데 메모리 초과가 떠서 찾아보니 BufferedReader 를 사용하면 해결이 된다길래 바꿔봤는데 바로 해결이 되었다!!!!! (아! Buffered 관련된 것을 사용할 때는 throws IOEception을 사용해줘야 한다)

앞으로 scanner 대신 bufferedreader를 자주 사용해야겠다!