자료구조(정렬 알고리즘) - 선택 정렬(Selection Sort) C언어 코드

안녕하세요, 츄르 사려고 코딩하는 집사 코집사입니다.

버블 정렬과 칵테일 정렬에 이어 이번엔 선택 정렬 입니다.

선택 정렬(Selection Sort)이란?

제자리 정렬 알고리즘 중 하나로, 단순하며 사용할 수 있는 메모리가 제한적인 경우 성능을 발휘할 수 있는 알고리즘입니다.

버블 정렬보다 성능이 좋고, 삽입 정렬보다는 좋지 않습니다.

선택 정렬의 알고리즘

1) 주어진 리스트 중에 최소값을 찾는다.

2) 그 값을 맨 앞에 위치한 값과 교체한다.

3) 바꾼 위치의 값을 제외하고 다시 반복한다.

선택 정렬의 시간 복잡도

버블 정렬과 같이, n(n-1)/2 이다.

n^2-n / 2 이므로, 시간 복잡도는 O(n^2)이다.

선택 정렬 C언어 소스 코드

배열의 크기를 입력 받아 정렬 

#include<stdio.h>

int A[10000];

int SelectionSort(int A[],int n);

int main()

{

int number;

printf("배열 크기 입력 : ");

scanf("%d",&number);

for(int i=0;i<number;i++)

{

printf("%d번째 배열 입력 : ",i);

scanf("%d",&A[i]);

}

SelectionSort(A,number);

}

int SelectionSort(int A[],int n)

{

int MIN,temp;

for(int i=0;i<n-1;i++)

{

MIN=i;

for(int j=i+1;j<n;j++)

{

if(A[MIN]>A[j])

{

MIN=j;

}

}

temp = A[MIN];

A[MIN] = A[i];

A[i] = temp;

}

for(int a=0;a<n;a++)

{

printf("%d",A[a]);

}

}