삽입정렬 insertion sort

삽입정렬

삽입정렬이란?

• 자료의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
• 즉 주어진 배열에서 앞에서부터 하나의 인덱스를 뽑아 자신의 위치를 찾아서 넣는 것이다.

특징

• 삽입정렬은 배열의 맨 처음, 0번째 인덱스는 정렬이 되어있는 상태라고 가정한다.
• 따라서 두번째 자료, 1번째 인덱스부터 뽑아서 앞의 정렬된 부분과 비교한다.
• 1번을 뽑아서 0과 비교를 하고, 0번째 인덱스가 만약 1번보다 크다면 swap 해주면된다.

예제

• 배열에 8,5,6,2,4가 저장되어있다
• 해당 배열을 오름차순으로 삽입정렬을 사용하여 정렬해볼 것이다.

1. 8 5 6 2 4
   • 1번째 인덱스인 5를 뽑아서 해당 인덱스 바로 앞에 있는 (정렬된) 인덱스부터 0번째 인덱스까지 비교한다.
   • 이번 회차는 1회차이므로 앞의 인덱스가 0번밖에 없다.
   • arr[j-1] > arr[j] 이므로 swap해준다.
   • j번째 인덱스 앞의 인덱스가 없으므로 i를 키워준다.
   • 즉, 2번째 인덱스를 뽑는다.
2. 5 8 6 2 4
   • 2번째 인덱스인 6(arr[j])을 뽑는다.
   • 6또한 앞의 8부터 시작하여 자신의 자리를 찾아준다.
   • 6(arr[j]) 과 8(arr[j-1])을 비교하여 6이 8보다 작으므로 swap한다.
3. 5 6 8 2 4
   • 이제 6이 arr[j-1]이 되어버렸으므로 j--를 해줘서 우리가 뽑은 인덱스를 유지시킨다.
   • 다시 6의 앞에 있는 인덱스와 비교하기 위해서 j와 j-1을 비교한다.
   • 5가 6보다 작으므로 swap하지 않고 for문을 빠져나와 다음 카드(8) 를 뽑기 위해서 i를 증가시켜준다.

위의 로직은 다음 코드로 정리할 수 있다.

void insertionSort(int length){
    
    for(int i=0; i<length-1; i++){
        //정렬할 부분
        for(int j= i+1; j>=0; j--){
            if(numbers[j-1]>numbers[j]) //j의 앞 부분과 비교하여 자신의 자리를 찾기
                swap(numbers[j-1], numbers[j]); //j가 j-1보다 작으면 swap
        }
    }
}

참고

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html