[알고리즘 2단계] 선택 정렬(Selection Sort)

[출처 : Goorm 사이트 - 기쁜 초밥]

문제

Selection Sort는 정렬되지 않은 전체 자료들의 위치를 맞추어가며 교환하며 정렬하는 알고리즘입니다. Selection Sort를 통해 입력된 수열을 오름차순으로 정렬하면서 입력한 단계에서의 상태를 출력하는 프로그램을 작성하십시오.

입력

첫 줄에 수열의 개수 n과 진행 단계 s를 입력한다. (1<=s<=n). 다음 줄에 수열을 입력한다.

 

출력

Selection Sort 해당 단계의 상태

 

예시

 

---

풀이

선택 정렬 알고리즘에 대해 복습하고 직접 코드를 작성하며 연습하기 적절한 문제였다.

먼저 선택 정렬 알고리즘에 대해 알아보자면, heejeong Kwon 님의 블로그 를 참고하였다. 선택 정렬 외 다양한 알고리즘을 공부하기 아주 좋게 정리해주셨다!

• 선택정렬 : 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.
• 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다.
• 시간 복잡도 : O(N^2)

 

- 입력받은 배열을 선택 정렬하는 코드.(선택 정렬 코드)

//선택정렬
#include <stdio.h>
//swap define 은 정말 편리하다!
#define swap(x, y, temp)	((temp = x), (x = y), (y = temp))

void s_sort(int *p, int n);

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

//선택정렬 알고리즘 시간복잡도 O(n^2)
void s_sort(int *p, int n){
	int least, temp;
	for(int i=0; i<n-1; i++){ //마지막 숫자는 자동으로 정렬되므로 n-1번 반복한다.
		least=i;
		for(int j=i+1; j<n; j++){
			if(p[j]<p[least])	least=j;
		}
		if(i!=least)	swap(p[i], p[least], temp);
	}
}

 

- 정답 코드

#include <stdio.h>
//swap define 은 정말 편리하다!
#define swap(x, y, temp)	((temp = x), (x = y), (y = temp))

void s_sort(int *p, int n, int s);

int main() {
	int n, s;
	int arr[100];
	scanf("%d %d", &n, &s);
	for(int i=0; i<n; i++){
		scanf("%d", &arr[i]);
	}
	
	s_sort(arr, n, s);
	
	for(int i=0; i<n; i++){
		printf("%d ", arr[i]);
	}
	return 0;
}

//선택정렬 함수.시간복잡도 O(n^2)
void s_sort(int *p, int n, int s){
	int least, temp;
	//마지막 숫자는 자동으로 정렬되므로 n-1번 반복한다.
	for(int i=0; i<s; i++){ 
		least=i;
		//최솟값 탐색
		for(int j=i+1; j<n; j++){
			if(p[j]<p[least])	least=j;
		}
		//앞에있는 i가 최솟값이 아니면 최솟값과 자료를 이동한다.
		if(i!=least)	swap(p[i], p[least], temp);
	}
}

- 입력 변수 S의 단계에서 선택 정렬을 과정 단계를 종료하고 출력해야 하므로 for문을 S 번만큼만 반복하게 했다.

결과

 

 

 

 

 

 

---

* 개인적인 학습 목적으로 작성한 글이기에 내용에 잘못된 정보가 있을 수 있습니다.

* 문제 출처 - level.goorm.io/exam/43265/selection-sort/quiz/1