백준 풀이 2750번 - 수 정렬하기 (+ 삽입정렬 개념)

 

2070번 문제 

 

 

 

여러 정렬알고리즘 중에 삽입정렬 알고리즘을 이용하여 문제를 풀어보았습니다.

 

 

삽입정렬이란 ?

 

• 삽입 정렬은 말그대로 삽입 (꽂아 넣는 정렬)하는 정렬입니다.

• 자신보다 앞의 원소가 큰지 작은지 비교해야 하기 때문에 arr[1] ~ arr[n] 까지 진행됩니다.

  (두번째 원소인 arr[1]부터 시작.)

• 삽입을 하면 데이터가 하나씩 밀려야 하기 때문에 배열이 길어질수록 효율이 떨어집니다.

 

 

추가 특징 ?

 

• 버블 소트와 비슷하게 리스트 크기가 크면 불리합니다. (계속 처음부터 끝까지 비교를 하여야 함.)

• 정렬의 거의 된 데이터일 경우 유리합니다. (교환이 적게 일어남) (이것도 버블과 비슷)

• 데이터가 역순인 경우 최악의 경우(Worst Case)에는 시간이 엄청 느립니다. (버블)

• 버블정렬과 다른점

  • 버블정렬은 n번째와 n+1번째만 비교해서 자리를 바꾸지만

  • 삽입정렬은 n+1번째의 데이터를 0~n번째 까지중 어디에 들어가야할지 자리를 찾아서 집어넣음

 

 

 

삽입정렬 그림표 (좋은 손코드 자료 참조)

 

 

 

 

 

시간복잡도 비교

 

버블정렬과 비슷한 분포를 보이지만 특이한 점은 정렬됬을 경우 시간이 극단적으로 짧게 걸린다는 특징이 있습니다.

 

즉 정렬된 배열의 경우에 유리합니다.

 

 

ex)

 

 

 

 

JAVA로 된 문제 풀이

 

JAVA언어로 문제를 풀어 보았습니다. 코드에서 부족한 부분있으면 알려주시면 감사드리겠습니다. :) 

 

import java.io.*;

public class Main {

    public static void main(String[] args) {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String line1 = "";

        

        try{

            line1 = br.readLine();

        } catch(Exception e) {

            

        }

        // 입력 갯수

        int N = Integer.valueOf(line1);



        int [] array;

        if(N<1 || N>1000)

            return ;

        else {

            array = new int[N];

        }





        for(int i=0; i<N; i++) {

            try{

               array[i] = Integer.valueOf(br.readLine());

            } catch(Exception e) {}

        }



        int comp = 0;

        for(int i=1; i<N; i++) {

            comp = array[i];

            for(int j=i-1; j>=0; j--) {

                if(comp >= array[j]) {

                    break;                

                } else {

                    int temp = array[j];

                    array[j] = comp;

                    array[j+1] = temp;

                }

            }   

        }



        for(int k=0; k<N ;k++) {

            System.out.println(array[k]);   

        }

    }

}

 

참고)

 

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

https://dpdpwl.tistory.com/18

https://blockdmask.tistory.com/98

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html