삽입정렬

현재 선택한(정렬되지않은) 데이터를 기존 정렬된 데이터의 적절한 위치에 삽입시켜 정렬하는 방식

시간 복잡도는 O(n²) 이고 구현하기 쉬운편

 

 

문제

https://www.acmicpc.net/problem/11399

11399번: ATM

 

풀이

int count = int.Parse(Console.ReadLine());
int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);

for (int i = 1; i < count; i++)
{
    int selectedData = arr[i];
    int insertPointer = i;

    for (int j = i-1; j >= 0; j--)
    {
        if(arr[j] > selectedData)
        {
            insertPointer--;
            arr[j+1] = arr[j];
        }
        else
            break;
    }

    arr[insertPointer] = selectedData;
}

for (int i = 1; i < count; i++)
{
    arr[i] += arr[i-1];
}

System.Console.WriteLine(arr.Sum());