[알고리즘] Insertion Sort(삽입 정렬) / C# 풀이

해당 문제는 코딩도장에 나온 문제입니다.

그치만 머.. 삽입 정렬이야 워낙 많이 나오는 문제니.. 간단하게 개념만 정리하고 풀이 들어가겠습니다.

삽입 정렬은 배열에서 2개의 수를 비교하여 배열 사이에 변수를 삽입하여 정렬하는 방식입니다.

예를 들어볼까요.

[1, 4, 2, 3] 이 있는 경우 1번 인덱스부터 시작합니다.

여기선 4가 되겠죠.

4를 비교해서 1번 인덱스보다 적은 숫자의 인덱스부터 검색을 시작합니다.

즉 0번 인덱스를 검사하죠.

이런식으로 반복적으로 검사를 하게 되면

1번째 index 0번

2번째 index에서는 0, 1

3번째 index에서는 0, 1, 2를 비교하여 삽입하겠네요.

이런식으로 비교해서 자기보다 크면 비교한 숫자보다 왼쪽으로 자신이 크면 그냥 원래 자리에 있는 방식으로 진행됩니다.

위의 예제를 순차적으로 풀어나가보면

[1, 4, 2, 3] -> [1, 2, 4, 3] -> [1, 2, 3, 4] 순이 되겠네요.(여기서 중간 비교 과정은 생략했습니다.)

생각보다 금방끝나서 다행입니다.ㅎㅎ;;;;;;;;;

    public class InsertionSort

    {

        static int [] arr = new int[10] { 1,4,2,3,5,7,6,9,8,0 }; // 배열을 선언하고

// 정렬함수입니다.

        public static void Sort()

        {

// 1번 인덱스부터 검사하니까 i도 1번부터 시작합니다.

            for (int i = 1; i < arr.Length; i++)

            {

                for (int j = 0; j < i; j++) // 0에서부터 기준 인덱스까지 검사를 해야하므로 j < i가 됩니다.

                {

                    if (arr[i] < arr[j]) // 비교했을때 기준 숫자보다 비교대상이 더 크면 바꿔야하니까

                    {

                        Swap(i, j); // 치환함수로 바꿔줍니다.

                    }                    

                }

            }

            foreach (int i in arr) // 출력해줍니다.

            {

                Console.Write(i + " ");

            }

        }

// 인덱스 번호를 넣어주면 배열상에서 서로 바꿔주는 함수입니다. 많이들 사용하시죠?

        public static void Swap(int i, int j)

        {

            int temp = arr[i];

            arr[i] = arr[j];

            arr[j] = temp;

        }

    }