삽입 정렬(Insert Sort)

삽입 정렬(insert sort)

삽입 정렬(insert sort)은 왼쪽부터 순서대로 정렬하는 정렬 방법입니다.

좌측에는 정렬된 데이터를 모아주고 우측에는 정렬되지 않은 데이터가 남게 되는 구조입니다.

우측에 정렬되지 않은 숫자를 하나씩 꺼내어 정렬이 끝난 좌측의 알맞는 위치에 삽입해서 정렬하는 방식입니다.

{5,2,3,10,7,1,8,4,6,9,14,11}

위의 나열된 수열을 가지고 삽입 정렬(insert sort)를 진행해 보도록 하겠습니다.

먼저 첫번째 수 5는 정렬이 끝난 수로 처리합니다.

5,2,3,10,7,1,8,4,6,9,14,11

5의 정렬이 끝났기 때문에 정렬되지 않은 수열의 첫번째 수 2를 가지고 정렬된 수와 비교를 합니다.

5 > 2

정렬되지 않은 첫번째 수 2가 정렬된 수보다 작습니다.

5와 2의 위치를 바꾸어 줍니다.

2,5,3,10,7,1,8,4,6,9,14,11

그리고 그 다음의 정렬된 수가 없는 수열의 가장 좌측 끝이기때문에 이대로 정렬을 종료합니다.

이 과정으로 정렬되지 않았던 수 2는 자기 자리를 찾아갔습니다.

2,5,3,10,7,1,8,4,6,9,14,11

같은 원리로 정렬되지 않은 수열에서 첫번째인 3을 위와 같은 방법으로 정렬합니다.

3과 정렬된 수를 비교합니다.

5 > 3

3이 작습니다.

3과 5를 교환해줍니다.

3은 그 다음으로 2와 비교를합니다.

2 > 3

3이 크기 때문에 2와 교환하지 않습니다.

2,3,5,10,7,1,8,4,6,9,14,11

이 과정을 통해서 3은 자기 자리를 찾아갑니다.

이 과정을 배열의 n번째까지 반복하면 됩니다.

위의 과정처럼 정렬되지 않은 수열의 첫번째 수를 정렬된 수열을 하나하나 비교하며 자기가 있어야 할 위치를 찾는 정렬 방법입니다. 

아래는 삽입 정렬(insert sort)을 구현한 간단한 예제입니다.

import java.util.Arrays;

public class InsertSort {

       int[] array = null;

       

       public void setData(int[] arr) {

              array = new int[arr.length];

              System.arraycopy(arr, 0, array, 0, arr.length);

       }

       

       public void insertSorting() {

              for(int j=0; j<array.length; j++) {

                     for(int i=j; i>=0; i--) {  

                           int targetIndex = i + 1;

                           

                           if(targetIndex > array.length - 1) {

                                  System.out.println("배열의 맨 우측 끝입니다.");

                                  return;

                           }

                           

                           if(array[targetIndex] < array[i]) {

                                  int temp = array[targetIndex];

                                  array[targetIndex] = array[i];

                                  array[i] = temp;

                           }

                     }

              }

       }

       

       public void printArray() {

              System.out.println(Arrays.toString(array));

       }

}