[알고리즘] 삽입정렬

삽입정렬

삽입정렬은 앞에서부터 정렬시켜 나아가는 알고리즘이다. 

데이터를 정렬할 때 앞에서부터 순차적으로 하나씩 비교하면서 위치를 찾아 삽입하는 방식으로,  적은 양의 데이터를 정렬하거나 이미 정렬된 부분이 많을 때 효율적이다.

앞의 정렬된 데이터의 수만큼 순회하고 이를 N-1번 반복하므로 시간복잡도는 N^2이다.

 

삽입정렬의 진행과정

 

 

1. 두 번째 요소부터 시작하여 현재 요소를 앞의 정렬된 부분과 비교.
2. 현재 요소보다 큰 값을 만나면 그 값을 오른쪽으로 밀어 공간을 만든다.
3. 정렬된 부분에 맞는 위치에 현재 요소를 삽입.
4. 이 과정을 리스트의 마지막 요소까지 반복.

 

 

 

코드 구현

Scanner sc = new Scanner(System.in);

int n = Integer.parseInt(sc.next());
int[] arr = new int[n];

for(int i=0; i<n; i++){
    arr[i] = sc.nextInt();
}

// 삽입정렬 구현
for(int i=1; i<n; i++){
    int tmp = arr[i], j; // i번째를 위로 올리고
    for(j=i-1; j>=0; j--){
        if (arr[j] > tmp) arr[j+1] = arr[j]; // j번째가 i번째수보다 크다면 오른쪽으로 한칸이동
        else break;
    }
    arr[j+1] = tmp; // 방금비교한 수의 앞에 tmp 삽입
}

// 정렬된 배열 출력
for(int i=0; i<n; i++){
    System.out.print(arr[i] + " ");
}