Selection-Sort(선택 정렬)

시간 복잡도 : O(n²)

1. 가장 큰 수를 찾는다

2. 가장 큰 수와 맨 오른쪽 수를 교환한다

3. 맨 오른쪽을 제외한다

4. 위 과정을 숫자 하나 남을 때까지 반복한다

예)

[5,9,8,3,4,6] - 처음 수를 잡고 다음 수와 비교

[5,9,8,3,4,6] - 잡고 있는 수보다 다음 수가 크기에 다음 수를 잡는다

[5,9,8,3,4,6] - 다시 다음 수와 비교

[5,9,8,3,4,6] - 잡고 있는 수가 더 크기에 그다음 수와 비교

[5,9,8,3,4,6] - 잡고 있는 수가 더 크기에 그다음 수와 비교

[5,9,8,3,4,6] - 잡고 있는 수가 더 크기에 그다음 수와 비교

[5,6,8,3,4,9] - 잡고 있는 수가 가장 크다는 것을 찾음, 가장 오른쪽에 있는 수와 교환

위의 과정을 숫자 하나 남을 때까지 반복

소스 - c언어

#include <stdio.h>
#include <stdlib.h>
#define MAX 100000

int main()
{
    int n,k,max;
    int a[MAX];
    int i,j;

    scanf("%d",&n);

    k=n;
    for(i=1;i<=n;i++)
    {
        a[i] = 0;
    }

    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }

    for(i=1;i<=n;i++)
    {
        max=1;
        for(j=2;j<=k;j++)
        {
            if(a[j]>a[max])
            {
                max = j;
            }
        }
        int temp;
        temp=a[k];
        a[k]=a[max];
        a[max]=temp;

        k--;
    }

    for(i=1;i<=n;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

피드백 환영