알고리즘 - 삽입정렬(insertion sort) c#

삽입정렬(insertion sort)

---

각 숫자를 적절한 위치에 삽입하면 어떨까? 해서 나온 답이 >> 삽입 정렬은 앞의 숫자가 나보다 큰지 비교하면서 자신의 위치에 삽입하는 정렬 방법

삽입정렬 과정

1. 첫 번째 원소는 이미 정렬된 것으로 간주하고, 두 번째 원소부터 시작합니다.
2. 현재 정렬된 부분과 비교하면서 적절한 위치에 삽입합니다.
3. 배열의 끝까지 이 과정을 반복합니다.

 

삽입정렬(insertion sort) 이론

---

이제 아래 사진과 함께 설명해보겠습니다.

그림 출처 : https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

그림에 있는 빨간색을 기준으로 보면서 위에 글을  확인하시고
각 숫자를 적절한 위치에 삽입하면 어떨까? 를 기억하시면 이해가 잘 될 겁니다.

 

삽입정렬(insertion sort) 코드

---

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        // 배열을 [3, 7, 2, 5, 1, 4]로 수정
        List<int> list = new List<int> { 3, 7, 2, 5, 1, 4 };
        Console.WriteLine("정렬 하기 전 리스트 안:");
        PrintList(list);

        InsertionSort(list);

        Console.WriteLine("정렬 하기 후 리스트 안:");
        PrintList(list);
    }

    static void InsertionSort(List<int> list)
    {
        int n = list.Count;
        for (int i = 1; i < n; i++)
        {
            int key = list[i];
            int j = i - 1;

            // key보다 큰 값들은 오른쪽으로 이동
            while (j >= 0 && list[j] > key)
            {
                list[j + 1] = list[j];
                j--;
            }
            // key를 적절한 위치에 삽입
            list[j + 1] = key;
        }
    }

    static void PrintList(List<int> list)
    {
        foreach (int item in list)
        {
            Console.Write(item + " ");
        }
        Console.WriteLine();
    }
}