[Java]삽입정렬(Insertion Sort)

삽입 정렬(Insertion Sort)

배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열이라는 가정하에 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하며. 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

 

-정렬 방식삽입 

• 정렬은 두 번째 자료부터 시작하며 왼쪽 값과 비교하여 왼쪽 값보다 작다면 교환한다. 하지만 앞쪽은 이미 정렬되어있다는 가정하에 비교하므로 왼쪽 값과 비교하여 왼쪽 값이 더 작다면 교환하지 않고 끝낸다.

 

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {7, 5, 2, 4, 3, 1, 9, 6, 0, 8};
        insertionSort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }
        public static void insertionSort(int[] arr) {
            for (int i = 1; i < arr.length; i++) {
                int j=i;
                int temp=arr[i];
                while(j>=1&&temp<arr[j-1]){
                    arr[j]=arr[--j];
                    }
                arr[j]=temp;
                }
            }
        }

- 장점

• 추가적인 메모리 소비가 거의 없다.
• 거의 정렬 된 배열의 경우 선택 정렬, 버블 정렬의 비해 효율이 좋다. O(n)까지 가능.
• 안정 정렬이 가능하다.

- 단점

• 최대 O(n^2)의 시간 복잡도를 갖기 때문에 상황에 따라 비효율적이다. 

 

 

참고

- https://st-lab.tistory.com/179