정렬 - 선택정렬, 삽입정렬

선택정렬

• 가장 작은 것을 선택해 앞으로 보내는 정렬 기법
• 가장 작은 것을 선택하는 데 N번, 앞으로 보내는 데 N번 0(N^2)의 시간복잡도

int main(void)
{
    int n, min, index;
    scanf("%d", &n);
    for (int i= 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = 0; i < n; i++)
    {
        if (min > a[j])
        {
            min = a[j];
            index = j;
        }
        swap(&a[i], &a[index]);
    }
}

 

 

 

삽입정렬

• 각 숫자를 적절한 위치에 삽입하는 정렬 기법
• 들어갈 위치를 선텍하는 데 N번, 선택하는 횟수로 N번 총 O(N^2)의 시간 복잡도

int main(void)
{
    int n, min, index;
    scanf("%d", &n);
    for (int i= 0; i < n; i++)
        scanf("%d", &a[i]);

    for (int i = 0; i < n; i++)
    {
        int j = i;
        while (j >= 0 && a[j] > a[j + 1])
        {
            swqp(&a[j], &a[j + 1]);
            j--;
        }
    }
}