Insertion_Sort(삽입 정렬)

 

➡️Insertion_Sort(삽입 정렬)이란

• 삽입 정렬은 현재 비교하고자 하는 target과 그 이전 원소들과 비교하여 자리를 교환하는 정렬 방법이다.
• 삽입 정렬은 테이터를 비교하면서 찾기 때문에 비교정렬이다.
• 삽입 정렬은 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 제자리 정렬이다.

https://ko.wikipedia.org/wiki/삽입_정렬

 

 

➡️Insertion_Sort(삽입 정렬)과정

1. 현재 타켓이 되는 숫자와 이전 위치에 있는 원소들을 비교한다.(첫번째 타겟은 두번째 원소부터 시작한다.)
2. 타겟이 되는 숫자가 이전 위치에 있던 원소보다 작다면 서로 위치를 교환한다.
3. 다음 타겟을 찾아 위 과정을 반복한다.

 

➡️Insertion_Sort(삽입 정렬)장단점 

장점

• 이미 정렬되어 있는 경우 매우 효율적이다.
• 안정 정렬이 가능하다.
• 추가적인 메모리 소비가 적다.

단점

• 배열이 길수록 효율성이 떨어진다.
• 역순에 가까울 수록 비효율적이다.

 

➡️Insertion_Sort(삽입 정렬)구현 코드 

public class Insertion_Sort {
 
 public static void sort(int[] arr) {
 
        for (int i = 1; i < arr.length; i++) {
 
           int target = i;
 
            while (i > 0 && arr[target - 1] > arr[target]) {
 
                swap(arr, target - 1, target );
 
                target--;
            }
        }
    }
 
    private static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }    }
}

 

 

 

---

😎REFERENCE

• https://danidani-de.tistory.com/43
• https://st-lab.tistory.com/179?category=892973
• https://www.daleseo.com/sort-insertion/