버블 정렬 - 자바 백준 수 정렬하기: 2750, 버블 소트: 1377

알고리즘에서의 정렬은 크게 아래와 같습니다.

 

• 버블(bubble) 정렬: 데이터의 인접 요소끼리 비교하고 swap 연산을 수행하며 정렬
• 선택(selection) 정렬: 대상에서 가장 크거나 작은 데이터를 찾아가 반복하면서 정렬
• 삽입(insertion)정렬: 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬
• 퀵(quick) 정렬: pivot 값을 선정해 해당 값을 기준으로 정렬
• 병합(merge) 정렬: 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬
• 기수(radix) 정렬: 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬

 

이 중에서 버블 정렬을 알아보고 문제를 풀어봅시다.

 

버블 정렬

버블 정렬(bubble sort) 는 두 인접한 데이터의 크기를 비교해 정렬합니다. 매우 간단하지만 시간 복잡도는 O(n²) 으로 다른 정렬보다 느린 편입니다.

아래 그림처럼 루프(loop) 을 돌면서 인접한 데이터 간의 swap 연산으로 정렬합니다.

 

 

 

버블 정렬 과정

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

 

만약 특정한 루프의 전체 영역에서 swap 이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬되었다는 의미입니다. 즉, 프로세스를 종료해도 됩니다.

 

백준 2750 수 정렬하기

2750번: 수 정렬하기

2750번: 수 정렬하기

1. 문제 분석

자바에서는 sort() 함수를 이용해 쉽게 정렬을 할 수 있지만 이번에는 정렬을 직접 구현해야 합니다.

N 의 최대범위가 1,000 으로 매우 작기 때문에 O(n²) 시간 복잡도 알고리즘으로 풀 수 있습니다.

버블 정렬이 가장 구현하기 쉬우면서 O(n²) 시간 복잡도이므로 이것으로 해결해봅시다.

 

2. 손으로 풀기

 

 

위 그림을 보았을 때 두 개의 루프를 중첩시켜야 함을 알 수 있습니다.

큰 루프는 비교하고 swap 할 전체 범위(빨간 글씨)에 관한 것이고, 작은 루프는 배열의 값을 직접 비교하고 swap 할 때 일어나는 것입니다.

 

3. 슈도코드

슈도 코드

N (정렬할 수 개수)
A (정렬할 배열 선언)

for (i: 0 ~ N-1)
    for (j: - ~ N-1-i)
        현재 배열의 값보다 1칸 오른쪽 배열의 값이 더 작으면 두 수 바꾸기

A 배열 출력

 

4. 코드

import java.util.Scanner;

/**
 * 문제 - 백준 2750 수 정렬하
 * 링크 - https://www.acmicpc.net/problem/2750
 * 등급 -  Bronze 2
 * 특이사항 - Do it Java 알고리즘 책 문제 015 101page
 */
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 - 1; i++) {
            for (int j = 0; j < N - 1 -i; j++) {
                if (A[j] > A[j + 1]) {
                    int temp = A[j];
                    A[j] = A[j + 1];
                    A[j + 1] = temp;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            System.out.println(A[i]);
        }

    }

}

 

백준 1377 버블 소트

1377번: 버블 소트

1377번: 버블 소트

 

1. 문제 분석

문제에서 제시하는 코드를 잘 살펴보면 어떤 것이 출력되는지 알 수 있습니다. 버블 정렬의 swap 이 한 번도 일어나지 않은 루프가 언제인지 알아내는 문제입니다.

 

‘버블 정렬의 이중 for 문에서 안쪽 for 문 전체를 돌 때 swap 이 일어나지 않았다.’ 라는 것은 ‘이미 모든 데이터가 정렬되어 있다’ 는 의미입니다. 이 때 프로세스를 바로 종료하면 시간복잡도를 줄일 수 있습니다.

 

하지만 이 문제에서 N 의 최대 범위는 500,000 이므로 버블 정렬로 문제를 풀면 시간을 초과할 수 있습니다. 안쪽 for 문이 몇번 수행되었는지 구하는 다른 아이디어가 필요합니다.

 

안쪽 루프는 1 에서 n-i 까지 swap 을 수행합니다. 왼쪽에서 오른쪽으로 이동하면서 swap 을 수행하는 것이지요. 이는 특정 데이터가 안쪽 루프에서 swap 의 왼쪽으로 이동할 수 있는 최대 거리가 1이라는 뜻입니다.

 

 

위 그림을 보면 각 데이터는 안쪽 루프에서 왼쪽으로 최대 1 까지만 이동할 수 있습니다. 혹은 이동을 아예 하지 않을 수도 있겠죠.

 

즉, 데이터의 정렬 전 index 와 정렬 후 index 을 비교해서 왼쪽으로 가장 많이 이동한 값을 찾으면 ‘몇번의 Loop 만의 정렬이 완료 되었는지 = swap 이 일어나지 않은 안쪽 루프가 몇번째였는지’ 의 답을 찾을 수 있어 이 문제를 해결할 수 있습니다.

 

2. 손으로 풀기

            a. 자바에서 기본적으로 제공하는 함수 sort() 의 시간 복잡도는 O(n㏒n) 입니다.

 

 

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

 

 

3. 슈도 코드

N(데이터 개수) A(데이터 배열, 클래스를 데이터로 담음)
for(N만큼 반복){
    A 배열 저장
}
A 배열 정렬

for(N만큼 반복){
    A[i] 의 정렬 전 index - 정렬 후 index 계산의 최대값을 찾아 저장
}

최대값 + 1 이 정답.

------
별도 클래스 선언
mData(데이터 표현){
    index, value 값을 가짐.
    value 기준으로 오름차순 정렬 함수 Comparable 구현
}

 

4. 코드

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

        IndexAndValue[] A = new IndexAndValue[N];

        for (int i = 0; i < N; i++) {
            A[i] = new IndexAndValue(Integer.parseInt(reader.readLine()), i);
        }

        Arrays.sort(A); // A 배열 정렬 (O(nlogn))

        int maxIndexDifference = 0;

        // 정렬 전 index - 정렬 후 index 계산의 최댓값 저장하기
        for (int i = 0; i < N; i++) {
            if (maxIndexDifference < A[i].index - i) {
                maxIndexDifference = A[i].index - i;
            }
        }
        System.out.println(maxIndexDifference + 1);
    }

}

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

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

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

 

Comparable와 Comparator 에 대한 정리는 아래 링크에 있습니다.

https://sh1mj1-log.tistory.com/124