자료의 정렬 - 삽입 정렬(Insertion sorting)

삽입 정렬(Insertion sorting)

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써

정렬을 완성하는 알고리즘.

삽입 정렬(Insertion sorting)의 방법

  ① 두수를 비교하여 큰수를 오른쪽으로 이동

  ② 새로운 수가 들어오면 왼쪽 값과 차례대로 비교하면서, 값이 크면 오른쪽으로 이동

  ③ 비교 값보다 작은 값이 나오면 멈춘다.

삽입 정렬(Insertion sorting) 예시

 

 

두 수를 비교하여 큰 수를 오른쪽으로 이동

 

왼쪽 값과 차례대로 비교하면서, 값이 크면

오른쪽으로 이동

 

 

 

 

 

 

 

 

 

 

위 사진으로는 뭔가 감이 잘 오지않는다.

쫌더 자세히 살펴보자.

 

일단, 무작위 숫자 3, 10, 41, 21, 42, 34, 13, 1, 43, 12를 정렬해보자.

첫번째로 제일 작은 숫자 3을 기준으로 우측으로 순서대로 탐색하며 최솟값을 찾아본다.

 

탐색하여 얻은 최솟값인 1과 첫번째 값의 위치를 바꾼다.

 

그리고 1을 제외한 첫번째 값인 10을 기준으로 다시 순서대로 탐색하며 기준으로한 10과 이미 정렬된

1을 제외한 최솟값인 3을 기준으로 삼은 10과 자리를 바꾼다.

 

그 다음으로 첫번째 값인 41을 기준으로 순서대로 탐색하여 최솟값인 10과 위치를 바꾼다.

위에서 설명한것을 계속 반복하면서 21과 최솟값인 12의 위치를 바꾼다.

 

42와 13의 위치를 바꾼다.

 

34와 21의 위치를 바꾼다.

 

42와 34의 위치를 바꾼다.

 

현재로썬 41이 최솟값이므로 그냥 두고, 43과 최솟값인 42와 바꾼다.

 

profit!  정렬완료.

삽입정렬(Insertion sorting) 알고리즘

//삽입정렬 알고리즘// void insertion_sort (int *data, int n) {    int i, j, remember; //반복문에서 사용할 변수와 두 값을 바꿀 때 사용할 변수    for(i = 1; i < n; i++)    {       remember = data[ (j = i) ];       while { --j >= 0 && remember < data[ j ] )       {          data[ j + 1] = data[ j ];          data[ j ] = remember;       }    } }

삽입정렬(Insertion sorting) 특징

  -일단 구현이 간단하며, 안정적이다.

  -적은 비교와 많은 교환이 필요한 방법으로 자료의 수가 적을수록 효과적이다.

    →배열이 길어질수록 효율이 떨어진다.

  -별도의 기억 공간을 필요로 하지 않기 때문에, 자료의 크기만큼의 기억공간이 있으면 된다.

  -후에 포스팅할 선택정렬이나 거품정렬과 같은 O(n²) 알고리즘에 비교하여 빠르며, 안정 정렬이다.

삽입정렬(Insertion sorting) 비교횟수

  -순서대로 정렬된 경우 비교 횟수 ⇒ n

  -자료가 부분적으로 정렬된 경우 ⇒ n + d(정렬되지 않는 수의 개수)

  -최대 비교횟수 ⇒ n(n - 1) / 2

 

 

도움되는 사이트

  - https://visualgo.net/en/sorting

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

정렬되는 모습을 실시간으로 보여주는 사이트이다.

사진으로 보는것보다 직접 정렬되는 모습을 보면 이해하기 더욱 쉽다.