삽입정렬 삽입소트 insertSort 자바구현

삽입정렬 삽입소트 insertSort 자바구현

---

삽입정렬을 배열로 구현하는 경우 삽입 후 요소의 위치이동에 따른 연산이 복잡하기 때문에 리스트로 구현하는게 훨씬 간단하고 효율도 좋다. 아래는 배열로 구현하는 경우와 리스트로 구현하는 경우 두 가지 소스를 작성해 보았다.

배열로 구현하는 경우

public static void insertSort(int[] arr) {
    for(int i = 1; i < arr.length; i++) {
        for(int j = i; j > 0; j--) {
            if(arr[j-1] > arr[j]) {
                int temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

리스트로 구현하는 경우(추천)

public static List<Integer> insertSort(List<Integer> input) {
    LinkedList<Integer> list = new LinkedList<Integer>(input);
 
    for(int i = 0 ; i < list.size() ; i++) {
        for(int j = i ; j < list.size() ; j++) {
            if(list.get(i) > list.get(j)) {
                Integer temp = list.remove(j);
                list.add(i, temp);
            }
        }
    }
    
    return list;
}