[C언어/기초알고리즘] 선택 정렬 (Selection sort)

선택 정렬 알고리즘의 시간 복잡도는 O(N^2)이다.

 

 

선택 정렬 알고리즘을 C언어로 작성 한 것이다.

 

#include <stdio.h>

int main(void){
	int i, j, min, index, temp;
	int array[10] = {1, 10, 5, 8, 7 , 6, 4, 3, 2, 9};
	for(i = 0; i< 10; i++){
		min = 100;
		for(j = i; j < 10; j++){
			if( min> array[j]) {
				min = array[j];
				index = j;
			}
		}
		temp = array[i];
		array[i] = array[index];
		array[index] = temp;
	}
	
	for(i = 0; i<10; i++){
		printf("%d ", array[i]);
	}
}

 

여기서 스와핑 코드를 사용하였습니다. 

배열에서 1번째 자리와 2번째 자리를 바꿀때

int array[2] = {1, 10};
int temp;

temp = array[0];
array[0] = array[1];
array[1] = temp;

이런 식으로 사용합니다.

 

 

 

따라서 백준 2750은 이러한 방식으로 해결 할 수 있습니다.

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

2750번: 수 정렬하기

#include <stdio.h>

int main(void){
	int i, j, min, index, temp;
	int array[1001];
	int n;
	scanf("%d", &n);
	
	for(i = 0; i < n; i++){
		scanf("%d", &array[i]);
	}
	
	for(i=0; i<n; i++){
		min = 1001;
		for(j = i; j<n; j++){
			if(min > array[j]){
				min = array[j];
				index = j;
			}
		}
		temp = array[i];
		array[i] = array[index];
		array[index] = temp;
	}
	
	for(i = 0; i< n; i++){
		printf("%d\n", array[i]);
	}
}