[백준] 수 정렬하기(2750)

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

sort() 함수를 사용하면 쉽게 정렬할 수 있지만, 버블 정렬을 사용하여 구현해보자.

버블 정렬은 이중 for문을 사용하므로 $O(N^2)$의 시간 복잡도를 가진다. N의 최대크기가 1,000으로 매우 작기 때문에 버블 정렬을 그대로 사용하면 된다.

버블 정렬 알고리즘을 슈도코드로 적으면 아래와 같다.

배열 A

for i=0부터 ~ N-1까지:
	for j=0부터 ~ N - 1 - i까지:
    	 if A[j] < A[j + 1]:
         	swap(A[j], A[j+1])

이중 for문의 안쪽 for문의 범위를 바깥 for문이 이미 반복한 횟수만큼 빼줘야 한다는 점만 유의하면 크게 어려울게 없을 것이다.
(이미 정렬된 원소는 접근하면 안된다는 점을 생각해보자.)

Python

따라서 파이썬으로 작성한 코드는 아래와 같다.

import sys

input = sys.stdin.readline

N = int(input())
A = [0] * N

for i in range(N):
    A[i] = int(input())

# 버블정렬 알고리즘
# 배열의 길이만큼 반복하면서
for i in range(N):
    # 이미 정렬되어 배열의 가장 끝부분으로 간 원소들은 제외
    for j in range(N - 1 - i):
        # 값 비교 후 swap 
        if A[j] > A[j + 1]:
            temp = A[j + 1]
            A[j + 1] = A[j]
            A[j] = temp

for i in range(N):
    print(A[i])

Java

따라서 자바로 작성한 코드는 다음과 같다.

import java.util.Scanner;

public class P_2750 {
    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; i++) {
        	// 이미 정렬되어 배열의 가장 끝부분으로 간 원소들은 제외하도록 - i 만큼 빼줌
            for (int j = 0; j < N - i - 1; j++) {
                if (A[j] > A[j + 1]) {
                    int temp = A[j];
                    A[j] = A[j + 1];
                    A[j + 1] = temp;
                }
            }
        }

        for (int i : A) {
            System.out.println(i);
        }
    }
}