삽입 정렬 의사코드와 구현

삽입 정렬 의사코드

앞선 글에서 하위 배열에 값을 삽입하는 방법을 배웠습니다. 그럼 다음으로 삽입 정렬을 구현하는 일이 남았는데 아래와 같은 의사코드를 참고하겠습니다.

 

1. insert를 호출하여 인덱스 0의 정렬된 하위 배열에 인덱스 1부터 시작하는 요소를 삽입합니다.

2. insert를 호출하여 인덱스 0에서 1까지 정렬된 하위 배열에 인덱스 2부터 시작하는 요소를 삽입합니다.

3. insert를 호출하여 인덱스 0부터 2까지 정렬된 하위 배열에 인덱스 3부터 시작하는 요소를 삽입합니다.

4. --반복--

5. 마지막으로 insert를 호출하여 인덱스 0에서 n-2까지 정렬된 하위 배열에 인덱스 n-1부터 시작하는 요소를 삽입합니다.

 

삽입 정렬의 구현

var array = [22, 11, 99, 88, 9, 7, 42]; 을 삽입정렬해보겠습니다.

 

앞서 구현했던 Insert 함수입니다.

 

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;
}

위 Insert 함수를 그대로 반복하면 선택 정렬이 됩니다.

 

static void InsertSort(int[] array)
{
    for (int i = 0; i < array.Length-1; i++)
    {
        Insert(array, i, array[i + 1]);
    }
}

선택 정렬 함수입니다.

 

static void Main(string[] args)
{
    int[] array = new int[7] { 22, 11, 99, 88, 9, 7, 42 };
    InsertSort(array);
    WriteArray(array);
}

바로 메인함수에 선택 정렬 함수를 넣고 실제 테스트를 해보겠습니다.

 

정상적으로 정렬이 됐습니다. 선택 정렬을 구현했습니다.