[Java] 백준 2750번: 오름차순 정렬하기

 백준 2750번은 배열을 오름차순으로 정렬하면 되는 문제이다. Arrays.sort() 메서드로 쉽게 풀 수 있는 문제지만, 공부 목적으로 해당 메서드를 사용하지 않고 풀어보도록 하겠다.

---

내 코드

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[] numbers = new int[N];

        for (int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(br.readLine());
        }
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (numbers[i] > numbers[j]) {
                    int temp = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = temp;
                }
            }
        }
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

 

 배열 내 i번 인덱스 값과 j번 인덱스 값을 비교하고, 작은 값이 발견될 때마다 값을 서로 교환하는 방식이다. 작은 값들이 배열의 앞으로 오게 되는 구조기 때문에 오름차순으로 정렬된다.

 

 그리고 이건 우연히 알게 된 내용인데, 기존 코드를 int j = i + 1에서 int j = 0으로 수정하여 내림차순으로 정렬할 수도 있다.

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (numbers[i] > numbers[j]) {
            int temp = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = temp;
        }
    }
}

---

그러나!

 

 두 방식 모두 오름차순/내림차순 정렬 기능 자체에는 문제가 없지만, 과연 이게 합리적인 코드인가에 대한 의문이 생겼다. 그래서 찾아보니 거품 정렬 방식이 언급되었다.

---

거품 정렬

Bubble Sort

 거품 정렬이란, 인접한 두 원소를 비교하여 크기 순서대로 정렬하는 정렬 방식이다. 물속 기포가 표면으로 올라오는 것처럼 각 요소가 배열의 끝으로 이동한다고 하여 거품 정렬이라고 부르는 듯하다.

 

 이외에도 선택 정렬, 삽입 정렬, 셀 정렬, 힙 정렬, 병합 정렬, 퀵 정렬, 카운팅 정렬 등이 언급되었는데, 자세히 알아보자니 시간이 너무 많이 소요될 듯하여, 관련 내용을 싹 다 모아 다음 포스팅에서 한 번에 다루도록 하겠다.