배열에 정수를 입력할 때마다 정렬하여 출력하기

<문제>

사용자로부터 n개의 정수를 입력받는다. 정수가 하나씩 입력될 때마다 현재까지 입력된 정수들을 오름차순으로 정렬하여 출력하라.

 

<Solution 1>

새로 정수를 입력받을 때마다 배열 전체에 대해서 정렬을 하는 방법(버블 정렬)

비효율적인 부분이 존재하지만, 직관적이다.

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int tmp = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            if (i == 0) {
                System.out.print(arr[0]);
            } 
            else {
                for (int j = 0; j < i; j++) {
                    for (int k = 0; k < i - j; k++) {
                        if (arr[k] > arr[k + 1]) {
                            tmp = arr[k + 1];
                            arr[k + 1] = arr[k];
                            arr[k] = tmp;
                        }
                    }
                }
                for (int j = 0; j <= i; j++) {
                    System.out.print(arr[j] + " ");
                }
            }
        }
        sc.close();
    }
}

 

<Solution 2>

첫번째 Solution의 비효율적인 부분은 무엇인가?

이미 이전 단계에서 오름차순으로 정렬이 되어 있음에도 불구하고 전체에 대해 다시 오름차순으로 정렬하는 것을 반복하고 있다. 추가로 입력된 값에 대해서만 고려해주는 방법을 생각해보자.

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
 
        for (int i = 0; i < n; i++) {
            int tmp = sc.nextInt();
            
            int j = i-1;
            while(j>=0 && arr[j]>tmp) {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = tmp;
            
            /*
            <for문을 통한 풀이>
            if (i == 0) {
                arr[i] = tmp;
            } 
            else {
                for (int j = i - 1; j >= 0; j--) {
                    if (arr[j] > tmp) {
                        arr[j + 1] = arr[j];
                        arr[j] = tmp;
                    } else {
                        arr[j+1] = tmp;
                        break;
                    }
                }
            }
            
            */
            for (int k = 0; k <= i; k++) {
                System.out.print(arr[k] + " ");
            }
            System.out.println();
            
        }
 
    }
}

<결과>