[C언어] 선택 정렬

선택 정렬(Selection Sort) 알고리즘 이란

#include <stdio.h>

// 9, 6, 7, 3, 5 	> 초기값 
// 3, 6, 7, 9, 5 	> 1회 
// 3, 5, 7, 9, 6	> 2회 
// 3, 5, 6, 9, 7	> 3회 
// 3, 5, 6, 7, 9	> 4회 

// 배열의 처음 부터 끝까지 탐색 -> 최솟값 탐색 
// 찾은 최솟값은 첫번째 위치에 배정시킵니다.
// 배정이 끝났으면 두번째 위치부터 탐색 시작.
// 위와 같은 방법으로 n-1번 반복 
 
void SelectionSort(int arr[], int n) {
	int i, j, k;
	int temp, minIdx;
	
	for(i = 0; i < (n - 1); i++) {
		minIdx = i;
		
		printf("[%d 번] ", i);
		
		for(j = 0; j < n; j++) {
			printf("%d ", arr[j]);
		}
		
		printf("\n");
		
		for(k = (1 + i); k < n; k++) {
			if(arr[minIdx] > arr[k]) {
				minIdx = k;
			}
		}
		
		temp = arr[i];
		arr[i] = arr[minIdx];
		arr[minIdx] = temp;
	}
}

int main(void) {	

	
	int arr[5] = {9, 6, 7, 3, 5};
	
	SelectionSort(arr, sizeof(arr)/sizeof(int));
	
	int i;
	
	printf("\n[선택 정렬] ");
	for(i = 0; i < 5; i++) {
		printf("%d ", arr[i]);
	}
	
	
	return 0;
}

 

---

선택 정렬(Selection Sort) 알고리즘의 특징

• 장점
  • 자료 이동 횟수가 미리 결정된다.
• 단점
  • 안정성을 만족하지 않는다.
  • 즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.

 

선택 정렬(selection sort)의 시간복잡도

시간복잡도를 계산한다면

• 비교 횟수
  • 두 개의 for 루프의 실행 횟수
  • 외부 루프: (n-1)번
  • 내부 루프(최솟값 찾기): n-1, n-2, … , 2, 1 번
• 교환 횟수
  • 외부 루프의 실행 횟수와 동일. 즉, 상수 시간 작업
  • 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 3(n-1)번
• T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)

• 단순(구현 간단)하지만 비효율적인 방법
  • 삽입 정렬, 선택 정렬, 버블 정렬
• 복잡하지만 효율적인 방법
  • 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

 

- 내용 출처

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html