선택 정렬(Selection Sort)

 선택 정렬이란 배열을 반복적으로 순회하며 가장 작은(또는 큰) 원소를 찾아서 정렬되지 않은 부분의 시작 위치와 교환하는 것입니다.

선택 정렬 구조 예시

선택 정렬은 배열 전체를 한 번 읽고 거기서 가장 작은(큰) 값을 맨 왼쪽으로 옮기는 형태의 정렬 방식입니다. 배열의 크기 만큼 반복한 결과값을 가져오는 정렬입니다. 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_LEN 5

void SelectionSort(int* _pArr);

void main()
{
	// 선택정렬(Selection Sort)
	// 빅-오 표기법(Big-O Notation)
	srand(time(NULL));			//srand: 난수 생성 함수 //time(NULL) 현재 시간

	int arr[MAX_LEN] = { 0 };		//5 크기의 정적 배열 arr 모두 0으로 초기화
	for (int i = 0; i < MAX_LEN; ++i) 
    {
		arr[i] = (rand() % 100) + 1;	//arr[0, 1, 2, 3, 4] = 0 ~ 100까지의 값 랜덤 + 1
		printf("[%d] - ", arr[i]);		//ex) [22] - [36] - [5] - [81] - [5]
	}
	printf("(%d)\n", MAX_LEN);			//[22] - [36] - [5] - [81] - [5] - (5)

	// 정렬
	printf("\n");
	SelectionSort(arr);			//SelectionSort(arr) 함수 호출
	printf("\n");

	for (int i = 0; i < MAX_LEN; ++i)	
		printf("[%d] - ", arr[i]);	//[22] - [36] - [5] - [81] - [5] - (5)
	printf("(%d)\n", MAX_LEN);
}

void SelectionSort(int* _pArr)
{
	if (_pArr == NULL) return;		//NULL 예외 처리

	// 3. 정렬이 된 위치 다음 부터 시작해서 반복
	for (int j = 0; j < MAX_LEN - 1; ++j)	//j는 최소 인덱스이므로 MAX_LEN보다 -1 조건
	{
		//1. 최솟값 찾기
		int minIdx = j;
		for (int i = j + 1; i < MAX_LEN; ++i)	// i는 배열 요소 변수이므로 j+1
		{
			if (_pArr[minIdx] > _pArr[i])	//만약 최소 인덱스값이 특정 배열보다 크면
				minIdx = i;		//최소 인덱스값은 i가 된다.
		}
		//printf("Selected Min [%d]: %d\n",
		//	minIdx, _pArr[minIdx]);

		//2. 정렬이 되어야 하는 위치 값과 교환
		//Swap
		int tmp = _pArr[j];		//tmp 임시 변수에 _pArr[j]의 값을 넣기
		_pArr[j] = _pArr[minIdx];	//
		_pArr[minIdx] = tmp;		//_pArr[minIdx]에 _pArr[j]의 값 tmp를 대입
	
		for (int k = 0; k < MAX_LEN; ++k)
		{
			if (k <= j)
				printf("[%d] - ", _pArr[k]);
			else
				printf(" %d  - ", _pArr[k]);
		}
		printf("\n");
	}
}

 <빅-오 표기법> (Big-O Notation)

 빅-오 표기법은 시간, 공간 복잡도에 따른 함수 결과값의 그래프에 대해 다루는 표기법인데 정렬에 따라 달라진다.

빅-오 표기법 표

 

끝