[Day05 - 2750번] 수 정렬하기

버블 정렬 파트에서 나온 내용이니 버블 정렬로 풀어보려 한다. N의 최대 범위가 1000으로 매우 작기 때문에 O(n^2)의 시간복잡도를 가진 버블 정렬로 문제를 해결할 수 있다.

 

먼저 슈도코드를 작성하면 다음과 같다.

N(정렬할 수의 개수)

A(수를 저장할 배열)

for (i: 0 ~ N-1) {

   for (j: 0 ~ N-i-1) {

      현재 A배열의 값보다 1칸 오른쪽 배열의 값이 더 작으면 swap

   }

}

 

코드로 구현하면 다음과 같다.

<hide/>
import java.util.*;

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-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]);
      }
   }
}

 

여기서 주의해야 할 부분은 바로 반복문에서 인덱스 범위인데,

각 라운드는 N-1번 반복되기 때문에 바깥쪽 반복문의 범위는 0 ~ N-2이고, 각 라운드 별 비교 횟수는 배열 크기에서 현재 라운드 횟수만큼 뺀 값이므로 0 ~ N-i-1 만큼 반복한다.