삽입정렬에서 삽입 함수 구현하기

삽입 정렬을 구현하기 전에 필요한 기능은 삽입 입니다. 우측에 있는 새로운 값을 좌측의 하위 배열에 밀어넣는 작업을 하는 함수를 만들어야합니다. 이를 Insert 함수라고 이름 짓겠습니다.

 

Insert 함수에는 매게변수로 array, rightIndex, value 총 세 가지가 필요합니다.

 

Insert 함수가 실행되기 전에 주의해야 할 점은 array[0]에서 array[rightIndex]까지 수가 오름차순으로 정렬되어 있어야 한다는 점입니다.

 

Insert 함수의 구현

static void Insert(int[] array, int rightIndex, int value)
{
    int i;

    for (i = rightIndex; i>=0 && array[i] > value; i--)
    {

    }
}

우선 for문에서 쓸 int i 를 선언해줘야합니다. 왜냐하면 삽입에서 반복문이 멈춘 지점을 알아야 그 지점에 마지막으로 value를 채워 줄 수 있기 때문입니다.

 

그리고 for문에 조건을 답니다. 만약 value가 왼쪽 끝에 도달하면 반복이 멈춰야 합니다. 그리고 array[rightIndex]가 value보다 작아도 반복이 멈춰야합니다. 

 

for문의 내용에는 아래 코드가 들어갑니다.

 

array[rightIndex + 1] = array[rightIndex];

계속 배열의 값을 오른쪽으로 밀어주는 작업입니다.

 

array[i + 1] = value;

마지막으로 반복문을 빠져나온 뒤 해당지점의 오른쪽에 value값을 넣어주면 됩니다.

 

static void Insert(int[] array, int rightIndex, int value)
{
    int i;

    for (i = rightIndex; i >= 0 && array[i] > value; i--)
    {
        array[i + 1] = array[i];
    }

    array[i + 1] = value;
}

최종적으로 위와 같은 코드가 나옵니다. 그럼 콘솔앱에서 테스트를 해보겠습니다.

 

int[] array = new int[5] { 5, 8, 13, 2, 9};

이렇게 5개의 숫자를 가진 배열을 만들었습니다. array[3] = 2 와 array[4] = 9 에 해당하는 수를 Insert 해보겠습니다.

 

static void Main(string[] args)
{
    int[] array = new int[5] { 5, 8, 13, 2, 9};

    Insert(array, 2, 2);
    Insert(array, 3, 9);

    WriteArray(array);
}

 

 

이렇게 테스트를 해보면

 

2,5,8,9,13 이 정렬되어 나옵니다.