6-3장 단순 선택 정렬

1. 단순 선택 정렬 알아보기 

 

단순 선택 정렬 (straight selection sort)

 

- 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬

- 교환 과정

 1) 아직 정렬하지 않은 부분에서 가장 작은 키의 값 (a[min])을 선택

 2) a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환

 

 ex) 배열 {6,4,8,3,1,9,7}을 선택 정렬 

 - 아직 정렬하지 않은 부분에서 값이 가장 작은 요소를 선택하고

 - 아직 정렬하지 않은 부분의 첫번째 요소와 교환

 

- 단순 선택 정렬 프로그램

//단순 선택 정렬  
#include <stdio.h> 
#include <stdlib.h>
#define swap(type,x,y) do {type t=x; x=y; y=t;} while(0)

void selection(int a[],int n)
{
	for(int i=0; i < n-1; i++)
	{
		int min =i; //a[i]~a[i-1]중에서 가장 작은 값을 가지는 요소의 인덱스 
		//i+1부터 n까지 가면서 최소값의 인덱스를 찾음
		for(int j=i+1; j<n; j++) 
			if(a[j]<a[min])
				min=j;
		swap(int,a[i], a[min]);
	}
}

int main()
{
	int nx;
	
	puts("단순 선택 정렬 ");
	printf("요소 개수:");
	scanf("%d",&nx);
	int *x=(int*)calloc(nx, sizeof(int));
	
	for(int i=0; i<nx; i++)
	{
		printf("x[%d]:",i);
		scanf("%d",&x[i]);
	}
	
	selection(x,nx); //배열 x를 선택정렬  
	
	puts("오름차순으로 정렬했습니다.");
	for(int i=0; i<nx; i++)
		printf("x[%d]=%d\n",i,x[i]);
		
	free(x); //배열 해제 
	
	return 0; 
}

 

 - 요솟값의 비교하는 횟수 

 (n^2-n)/2회 

 

- 불안정 정렬

 -> 중복된 값이 있을떄  입력순서와 동일하지 않게 정렬