버블 정렬 (Bubble sort)

버블 정렬 (Bubble Sort)

두 인접한 데이터의 크기를 비교해 정렬하는 방법. 간단하게 구현할 수 있지만 시간 복잡도는 O(n^2)으로 다른 정렬 알고리즘보다 속도가 느린 편이다. 다음 그림과 같이 루프(loop)를 돌면서 인접한 데이터 간의 swap 연산으로 정렬한다.

https://www.computersciencebytes.com/sorting-algorithms/bubble-sort/

 

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

 

만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료해도 된다.

 

---

 

[백준 2750번] 수 정렬하기

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

 

(자바에서는 sort() 함수를 이용해 쉽게 정렬할 수 있다.)

N의 최대 범위가 1,000으로 매우 작기 때문에 O(n^2) 시간 복잡도 알고리즘으로 풀 수 있다. 버블 정렬의 시간 복잡도가 O(n^2)이므로 버블 정렬 알고리즘을 이용해 정렬해도 시간 복잡도 안에 문제를 해결할 수 있다.

 

[정답]

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

public class Main {
    static int[] A;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        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 - i - 1; j++) {
                if(A[j] > A[j+1])
                    swap(j, j+1);
            }
        }
        for (int i = 0; i < N; i++) {
            System.out.println(A[i]);
        }
    }
    static void swap(int a, int b) {
        int tmp = A[a];
        A[a] = A[b];
        A[b] = tmp;
    }
}

 

---

 

[백준 1377번] 버블 소트

 

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

 

버블 정렬의 swap이 한 번도 일어나지 않은 루프가 언제인지를 묻는 문제로, 이 말은 즉 이미 모든 데이터가 정렬됐다는 것을 의미한다. 이때는 프로세스를 바로 종료해 시간 복잡도를 줄일 수 있다. 하지만 이 문제는 N의 최대 범위가 500,000이므로 버블 정렬로 문제를 풀면 시간을 초과할 수 있다. 안쪽 for 문이 몇 번 수행됐는지 구하는 다른 아이디어가 필요하다.

 

다른 아이디어

안쪽 루프는 1에서 n-i 까지, 즉 왼쪽에서 오른쪽으로 이동하면서 swap을 수행한다. 이는 특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는 최대 거리가 1이라는 뜻이다. 즉, 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾으면 이 문제를 해결할 수 있다.

 

1. 자바에서 제공하는 sort() 함수로 배열을 정렬한다. sort() 함수의 시간 복잡도는 O(nlogn)이다.

2. 각 데이터마다 정렬 전 index와 정렬 후 index 값을 빼고 최댓값을 찾는다. 그리고 swap이 일어나지 않는 반복문이 한 번 더 실행되는 것을 감안해 최댓값에 1을 더한다.

 

[정답]

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

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());
        mData[] A = new mData[N];
        for (int i = 0; i < N; i++) {
            A[i] = new mData(Integer.parseInt(br.readLine()), i);
        }
        Arrays.sort(A);                  // A 배열 정렬 (O(nlogn))
        int max = 0;
        for (int i = 0; i < N; i++) {
            if(max < A[i].index - i)    // 정렬 전 index - 정렬 후 index
                max = A[i].index - i;   // 의 최댓값 저장
        }
        System.out.println(max + 1);
    }
}

class mData implements Comparable<mData> {
    int value;
    int index;

    public mData(int value, int index) {
        super();
        this.value = value;
        this.index = index;
    }

    @Override
    public int compareTo(mData o) {     // value 기준 오름차순 정렬
        return this.value - o.value;
    }
}

 

 

 

 

 

[참고자료]

- Do it! 알고리즘 코딩 테스트 자바편