선택정렬

1. 정렬이란,

특정 기준을 적용하여 나열하는 것입니다.
ex) 3 4 1 2 →오름차순 정렬→ 1 2 3 4

 

2. 정렬 알고리즘의 효율성을 판단하는 기준

• 비교 횟수
• 데이터가 정렬될 때 이동하는 횟수
• 사용되는 메모리 양

 

선택정렬

1) 원리:

• 정렬이 완료 된 것(bar 왼쪽)과 아닌 것(bar 오른 쪽)을 나누는 기준인 bar가 시작할 때 맨 앞에 있다고 생각합니다.
• 즉, 시작 할 때는 bar 왼쪽에 아무 원소도 없으니 '아 아직 정렬 된 게 아무 것도 없구나' 라는 의미가 되는 것입니다.
• 본격적으로 (오름차순)정렬 시에는 그 bar의 오른쪽에 있는 원소들 중 가장 최소 값을 찾고,
• 찾은 최소값을 bar가 있는 원소의 자리와 바꾸어줍니다.
• 이렇게 원소 하나의 자리를 찾아 주었다면 bar를 한 칸 옆으로 이동시킵니다.

 

이렇게 '최소값을 찾고→ 자리 바꿔주고 → bar밀고'의 과정을 반복하여 bar를 맨 끝으로 이동시키는 것으로 선택 정렬은 마무리됩니다.

2) 구현

1. bar에 해당하는 것을 변수 i로 둡니다. 이는 'i 가 가리키고 있는 곳에 최소값을 위치 시켜라'의 의미입니다. 그리고 i가 0부터 정렬시켜야 하는 배열의 원소 끝까지 아래의 과정을 반복하며 정렬시켜야 하므로 for문을 사용합니다.
2. i가 위치한 곳에서부터 마지막 원소 중 가장 최소값을 찾습니다.
3. 찾은 최소값과 i가 가리키는 원소를 바꿉니다.
4. i를 한 칸 옆으로 이동시킵니다.

#include <stdio.h>

int main(){
	//선택정렬의 구현 
	/* 10(입력) 개의 숫자를 정렬
	1 5 6 8 3 4 5 9 2 10 (입력)을 선택 정렬하면
	1 2 3 4 5 5 6 8 9 10 을 출력
	*/
	int n;
	int data[100]; //정렬해야할 원소들이 들어갈 배열 선언
	
	scanf("%d", n);
	for(int i=0; i<n; i++){
		scanf("%d", &data[i]);
	}//정렬해야 할 원소 개수와 원소들 입력받기

	//본격적인 선택 정렬
	for(int i=0; i<n; i++){
		int inx = i;
		for(int j=i; j<n; j++){ //i(bar가 가리키고 있는 것)부터 맨 끝까지의 값 중 '최소값'찾아서
			if(data[inx] > data[j]){
				inx = j; //최소값의 위치(inx) 찾고
			}
		} //이게 다 종료되면 inx가 i 번째부터 맨 끝까지의 값 중 최소값의 인덱스 값을 가지고 있다. 
		//그리고 i가 가리키는 값이랑 inx가 가리키는 값을 바꾸면 된다. 
		int temp;
		temp = data[i];
		data[i] = data[inx];
		data[inx] = temp;
	}
	// 선택정렬 끝

	//결과 출력
	for(int i=0; i<n; i++){
		printf("%d", data[i]);
	}
	printf("\n");
    
}

3) 시간복잡도

1. 비교 횟수

   • 2개의 for loop 가 실행된다.
   • 외부 loop는 n-1번
   • 내부 loop는 외부의 i에 따라 시작점이 달라지니까 n-1, n-2, n-3,..., 2, 1

2. 데이터가 정렬될 때 이동하는 횟수

   • 총 외부 loop 실행 횟수(n-1)번 만큼 실행되는데 한 번 실행될 때 3번의 이동이 되니까 3(n-1)번

    

3. 시간복잡도 계산

   데이터의 개수가 n개라고 했을 때,

   첫 번째 최소값찾기 비교횟수 : 1 ~ n-1 => n-1

   두번째 최소값찾기 비교횟수 : 2 ~ n-1 => n-2

   .

   .

   .

   (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

   이기때문에 O**(n2)만큼의 시간복잡도를 가집니다.