[문제풀이] 06-03. 삽입 정렬

인프런, 자바(Java) 알고리즘 문제풀이

Sorting and Searching - 0603. 삽입 정렬

🗒️ 문제

🎈 나의 풀이

	private static int[] solution(int[] arr) {
        int j;
        for(int i=1; i<arr.length; i++){
            int tmp = arr[i];

            for(j=i-1; j>=0; j--) {
                if(tmp<arr[j]) arr[j+1] = arr[j];
                else break;
            }

            arr[j + 1] = tmp;
        }


        return arr;
    }
    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++) arr[i] = sc.nextInt();

        arr = solution(arr);

        for(int i : arr) System.out.print(i + " ");
    }

🖍️ 강의 풀이

  public int[] solution(int n, int[] arr){
		for(int i=1; i<n; i++){
			int tmp=arr[i], j;
			for(j=i-1; j>=0; j--){
				if(arr[j]>tmp) arr[j+1]=arr[j];
				else break;
			}
			arr[j+1]=tmp;
		}
		return arr;
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int[] arr=new int[n];
		for(int i=0; i<n; i++) arr[i]=kb.nextInt();
		for(int x : T.solution(n, arr)) System.out.print(x+" ");
	}

💬 짚어가기

해당 문제는 정렬 알고리즘 중 하나인 삽입 정렬이다.
배열의 앞에서부터 순회하며 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬한다.

거의 정렬 된 경우 매우 효율적인 알고리즘이다. 최선의 경우 $O(n)$의 시간복잡도를 갖는다.
그러나 역순에 가까울수록 비효율적이다. 최악의 경우 $O(n^2)$의 시간 복잡도를 갖는다.