https://easy-h.github.io/ 이전하였습니다.

알고리즘 기초 (삽입정렬) 본문

Algorithm

알고리즘 기초 (삽입정렬)

>_ Easy-h 2019.04.18 21:51

Harvard CS50 x Edwith 강의를 학습하며 정리한 내용입니다.

삽입정렬


삽입정렬은 자료를 정렬하는 알고리즘중 하나로 자료가 정렬된 부분과 정렬되지 않은 부분으로 나누어 정렬되지 않은 부분의 자료가 정렬된 부분의 자리로 삽입되는 형태의 정렬 방법입니다. 그렇기 때문에 자료를 여러 번 비교하거나 교환할 필요가 없으며 배열이 길수록 효율이 떨어지지만 구현은 간단한 방법입니다.

예제


3, 6, 2, 5, 1, 4 의 배열을 정렬해보자.
  1. [3] | 6 | 2 | 5 | 1 | 4
  2. [3] | [6] | 2 | 5 | 1 | 4
  3. [2] | [3] | [6] | 5 | 1 | 4
  4. [2] | [3] | [5] | [6] | 1 | 4
  5. [1] | [2] | [3] | [5] | [6] | 4
  6. [1] | [2] | [3] | [4] | [5] | [6]

배열의 정렬된 부분은 [] 로 표기하였고 정렬되지 않은 부분은 그냥 숫자로 표기하였습니다.

  • 프로그램이 실행되었을때 배열의 첫번째 자리는 이미 정렬된 부분으로 간주합니다.
  • 정렬되지 않은 부분의 6은 3보다 크기 때문에 이동할 필요가 없습니다.
  • 다음 정렬되지 않은 2는 3과 6보다 작기 때문에 2가 자리를 비우고 3과 6이 오른쪽으로 이동 후 맨 앞자리로 2가 들어옵니다.
  • 다음 정렬되지 않은 5는 정렬된 2,3,6에서 2,3은 제외한 6의 기준에서만 작기때문에 5 와 6 은 자리를 교환합니다.

이런식으로 같은 방식을 반복하면 전체의 모든 값이 정렬되는 것을 볼 수 있습니다.

코드(Java)


static void insertionSort(int[] arr)
    {
        int i, temp, j;
        for(i = 1 ; i < arr.length ; i++){

            temp = arr[i];
            j = i - 1;

            while( (j >= 0) && ( arr[j] > temp ) ) {

                arr[j+1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;

            System.out.print("\n삽입정렬 "+i+" 번 : ");
            for (int z = 0; z < arr.length; z++) {
                System.out.print(arr[z]+" ");
            }
        }
    }

    public static void main(String[] args) {
        int arr [] = {3,6,2,5,1,4};
        insertionSort(arr);
    }

결과


스크린샷 2019-04-18 오후 10 14 14

정리


삽입정렬은 특정 실행 단계에서 한 원소가 정렬된 배열의 자리를 이동하거나 찾았다 해도 그것이 최종적인 자리인 보장을 할 수 없습니다. 즉 정렬이 끝나기 전까지는 확실한 보장을 하지 못한다는 의미입니다. 그렇기에 삽입정렬은 자료의 양이 많을 수록 성능이 떨어질 수 밖에 없으며 또한 많은 자료가 정렬이 되어 있는 경우라도 정렬이 된 많은 자료들을 이동시켜야 하기 때문에 안정성도 떨어집니다. 결과적으로 자료의 양이 적거나 자료가 대부분 정렬이 되어 있는 경우 효율적인 정렬이라고 볼 수 있습니다.

참고


cs50 x edwith
위키백과

0 Comments
댓글쓰기 폼