C언어 sort 알고리즘 - ceon-eo sort algolijeum

선택 정렬 알고리즘의 시간 복잡도는 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번: 수 정렬하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

www.acmicpc.net

#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]);
	}
}

알고리즘 훈련중에 제일 먼저 하게되는 연습은 정렬(Sort)알고리즘 이라고 한다. 그 이유는 정렬 알고리즘 만큼 효율성의 차이를 극명하게 보여주는 것이 없다고 한다. 그래서 정렬알고리즘부터 공부를 시작해봐야겠다.

선택 정렬(Selection Sort) 알고리즘 개념 

- 제자리 정렬(in-place sorting)의 알고리즘 중 한종류

  > 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법

선택 정렬 알고리즘 동작 원리 

- 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

  > 첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다.

  > 두 번째 순서에는 두 번째 위치에 남은 값 중에서 최솟값을 넣는다.

  > 그렇게 N번까지 반복 후 N번(마지막)자리에는 제일 큰값을 넣는다.

이미지로 보는 동작 절차

1) [3, 4, 1, 9, 7, 5] 중에서 제일 작은 값을 1번 값으로 교환한다.

> 이미지상 : 1번 값 = 1

2) [1, 4, 3, 9, 7, 5] 중에서 2번 값에 2번째로 작은 값으로 교환한다.

> 이미지상 : 2번 값 = 3

3) 위의 방식의 N번 반복한다. 

> 이미지상 결과물 : [1, 3, 4, 5, 7, 9]결과가 나온다.

셀렉 정렬 C언어 코드 : 

베타존 : 네이버쇼핑 스마트스토어

나를 꾸미다 - 인테리어소품 베타존

smartstore.naver.com