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

선택정렬 (Selection Sort)

: 가장 작은 값(또는 가장 큰 값)을 선택하여 배열의 앞쪽에 차례대로 정렬하는 방식 

 

동작방식 

1. 배열의 첫번째 위치부터 전체 배열까지 가장 작은 값 찾기
2. 첫번째 위치 값과 가장 작은 값을 바꿈 (스와핑) 
3. 두번째 위치로 이동하고 같은 과정 반복
4. 배열의 끝까지 반복 

 

 

시간복잡도

• 배열이 정렬된 상태든, 정렬되지 않은 상태든, 항상 같은 시간 복잡도 → O(n^2)

 

 

스와핑 (Swapping)

: 두 변수의 값을 교환하는 작업

// 배열로 바꿔야 함
int a = 1;
int b = 3;
int tmp;

tmp = a;
a = b;
b = tmp;

a의 값은  3, b의 값은 1로 교환

 

로또 번호 예제 - 중복 제거 후 정렬 

C언어

#define _CRT_SECURE_NO_WARNINGS
#define SIZE 6
#include <stdio.h>
#include <stdlib.h>

int main(void) {

	// 로또 번호 추출 
	// 선택정렬 (Selection Sort) 알고리즘

	int lotto[SIZE]; // 로또 배열
	int randNo; // 랜덤번호
	int flag; // 중복 여부 플래그 
	int index = 0; // 로또 인덱스 

	srand((unsigned)time(NULL));

	// 1. 중복 제거 
	for (int i = 0; i < SIZE; ++i) {
		randNo = rand() % 45 + 1;
		flag = 0;

		for (int j = 0; j < index; ++j) {
			// 중복일 경우 
			if (lotto[j] == randNo) {
				flag = 1;
				i--; // 중복일 경우 다시 뽑도록 
				printf("중복입니다. 다시 뽑습니다. \n");
				break;
			}
		}

		// 중복이 아닌 경우
		if (flag == 0) {
			lotto[index] = randNo;
			index++;
		}
	}

	// 1-1. 중복제거 후 로또 번호 출력
	for (int i = 0; i < SIZE; ++i) {
		printf("%d\t", lotto[i]);
	}

	// 2. 정렬 
	int lastIndex = SIZE - 1; // 총 반복횟수 
	int nextIndex; // 다음 인덱스 
	int minIdx; // 최솟값의 인덱스 

	for (int i = 0; i < lastIndex; ++i) {
		nextIndex = i + 1;
		minIdx = i;
		for (int j = nextIndex; j < SIZE; ++j) {
			if (lotto[j] < lotto[minIdx]) {
				minIdx = j; // 최솟값 인덱스 저장
			}
		}
		if (minIdx != i) {
			int tmp = lotto[minIdx];
			lotto[minIdx] = lotto[i];
			lotto[i] = tmp;
		}
	}

	printf("\n");

	// 2-1. 정렬 후 로또 번호 출력
	for (int i = 0; i < SIZE; ++i) {
		printf("%d\t", lotto[i]);
	}

	return 0;
}

 

정렬 시 아래와 같이 순회하며 정렬

반복 횟수 (i)	생성된 randNo	lotto 배열 상태	index 값	flag 값	동작
0	12	{}	0	0	12을 lotto[0]에 추가
1	24	{12}	1	0	24를 lotto[1]에 추가
2	36	{12, 24}	2	0	36을 lotto[2]에 추가
3	24	{12, 24, 36}	3	1	중복 발생, i--
3 (반복 재수행)	45	{12, 24, 36}	3	0	45를 lotto[3]에 추가
4	12	{12, 24, 36, 45}	4	1	중복 발생, i--
4 (반복 재수행)	7	{12, 24, 36, 45}	4	0	7을 lotto[4]에 추가
5	19	{12, 24, 36, 45, 7}	5	0	19를 lotto[5]에 추가