[JAVA] 삽입 정렬 (Insertion Sort)

삽입정렬은 2번째 원소부터 n번째 원소까지 차례로 해당 원소가 위치할 인덱스에 원소를 삽입하는 방식이다.

오름차순으로 정렬할 때, 삽입정렬은 2번째 원소부터 앞의 원소와 비교하는 과정을 통해 적절한 위치에 삽입하고 n번째 원소까지 이 방식을 반복하며 정렬을 진행한다.

 

import java.util.Arrays;
class InsertionSort {
  
  public static void main(String[] args) {
    int []arr = {3,7,6,8,4,5,0,2};
    int temp;
    int prev;
    
   	for (int i = 1; i < arr.length; i++) {
      //현재 선택된 원소의 값을 임시 변수에 저장
      temp = arr[i];
      //현재 원소를 기준으로 이전 원소를 탐색하기 위한 index 변수
      prev = i - 1;
      //현재 선택된 원소가 이전 원소보다 작은 경우까지만 반복 (단, 0번째 원소까지만 비교)
      while(prev >= 0 && arr[prev] > temp) {
        //현재 선택된 원소가 현재 탐색중인 원소보다 작다면, 해당 원소는 다음 인덱스로 미뤄버림
        arr[prev + 1] = arr[prev];
        //다음 대상 원소를 탐색
        prev--;
      }
      //탐색이 종료된 지점에 현재 선택되었던 변수의 값을 삽입
      arr[prev + 1] = temp;
    }
    System.out.println(Arrays.toString(arr));
  }
  
}

최악의 경우에는 (5,4,3,2,1) 각각의 탐색에서 무조건 앞의 모든 원소를 뒤로 미뤄버려야 하기 때문에 시간 복잡도는 O(n^2)다. 최선의 경우 O(n)의 시간복잡도를 갖는다.

 

출처 url: https://sskl660.tistory.com/81

[Java]삽입 정렬(Insertion Sort)