selection sort(선택 정렬)

#include <stdio.h>
#define SIZE 100

void selection_sort(int arr[],int n,int maxIndex);
int findmin(int arr[],int start, int last);

int main(){
	int n;
	int arr[SIZE]={0, };
	int i;
	
	scanf("%d",&n);
	
	for(i=0;i<n;i++)
		scanf("%d",&arr[i]);
	
	selection_sort(arr,0,n-1);
	
	for(i=0;i<n;i++)
		printf("%d ",arr[i]);
	return 0;
}


void selection_sort(int arr[],int startIndex,int lastIndex){ 
	int tmp;
	int minIndex;
	
	if(startIndex == lastIndex)
		return ;
	
	
	minIndex=findmin(arr,startIndex,lastIndex);
			
	tmp=arr[minIndex];
	arr[minIndex]=arr[startIndex];
	arr[startIndex]=tmp;
		
	selection_sort(arr,++startIndex,lastIndex);		
}

int findmin(int arr[],int start, int last){ //최솟값이 들어있는 index 찾는 함수 
	if(start==last)
		return last;
	else {
		if(arr[start]>arr[findmin(arr,start+1,last)])
			return findmin(arr,start+1,last);
		else
			return start;
	}
}

---

재귀함수를 이용하여 선택정렬을 하였다.

 

1. 배열에서 최솟값을 찾는다.

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

3. 처음 위치를 뒤로 한칸씩 옮기면서 1~2 과정을 반복한다.

4. 이 과정은 하나의 원소가 남을 때 까지 동작된다.

---

 

2020/04/10 - [Algorithm/Problems] - n개의 수의 총합을 계산하기

n개의 수의 총합을 계산하기