삽입정렬

앞의 숫자가 나보다 큰지 비교하면서 자신의 위치에 삽입하는 정렬 방법
앞의 값과 비교를 하기 때문에 전체 배열 중 0번 인덱스가 아닌 1번 인덱스부터 앞의 값과 비교

 

시간복잡도 : O(n) = n

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace InsertionSort
{
    internal class InsertionSort
    {
        static void Main(string[] args)
        {
            Console.Write("삽입정렬");
            int[] data = { 20, 15, 1, 5, 10 };

            for (int i = 1; i < data.Length; i++)
            {
                int key = i;
                for (int j = i - 1; j >= 0; j--) // 기준 숫자(key)와 앞 숫자의 크기 비교
                {
                    if (data[key] < data[j]) // key값의 데이터 앞에 값이 작다면 밑의 코드 실행
                    {
                        int temp = data[j]; // temp 변수에 앞 데이터의 변수를 담는다.
                        data[j] = data[key]; // 앞 데이터에 기준숫자를 넣어줌
                        data[key] = temp; // 기준숫자에 앞 데이터를 넣어서 서로 바꿔준다
                        key = j;
                    }
                    else
                    {
                        break;
                    }
                }

                for (int j = 0; j < data.Length; j++)
                {
                    Console.Write(data[j] + ",");
                }
                Console.WriteLine();
            }
        }
    }
}