[Java] 삽입정렬 코드 /insertion sort (자바 예제, 시간복잡도 )

---

삽입 정렬 시간복잡도

Best	Avg	Worst
n	n^2	n^2

 

 

 

자바로 삽입정렬을 구현한 코드입니다. 

/**
 * 전제 조건:  x[0 ~ i -1] 까지 정렬되어 있고 i는 x의 크기 보다 작다.
 * x[i]가 x[0 ~ i -1]사이 올바른 위치에 들어가게 해준다.
 * @param x 배열
 * @param i 올바른 위치를 찾아줄 원소의 인덱스
 */
public static void insert(int[] x, int i){
    int temp, j =0;
    temp = x[i];
    for(j = i-1; j>=0 && temp<x[j]; j--){
        x[j+1] = x[j];
    }
    x[j+1] = temp;

}

/**
 * 배열 x를 정렬한다.
 * @param x 배열
 */
public static void sort(int[] x){

    for (int i = 1; i < x.length; i++){
        insert(x, i);
    }
}

 

코드 사용 예시 

import java.util.Arrays;

public class Test{
    public static void main(String[] args) {
        int[] a = {5,1,2,3,4,8,6,9,4,5};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));


    }

    /**
     * 전제 조건:  x[0 ~ i -1] 까지 정렬되어 있고 i는 x의 크기 보다 작다.
     * x[i]가 x[0 ~ i -1]사이 올바른 위치에 들어가게 해준다.
     * @param x 배열
     * @param i 올바른 위치를 찾아줄 원소의 인덱스
     */
    public static void insert(int[] x, int i){
        int temp, j =0;
        temp = x[i];
        for(j = i-1; j>=0 && temp<x[j]; j--){
            x[j+1] = x[j];
        }
        x[j+1] = temp;

    }

    /**
     * 배열 x를 정렬한다.
     * @param x 배열
     */
    public static void sort(int[] x){
        for (int i = 1; i < x.length; i++){
            insert(x, i);
        }
    }
}

 

결과 

배열 a가 오름차순으로 잘 정리된 모습을 볼 수 있습니다.