선택 정렬(Selection Sort)

선택 정렬

선택 정렬(Selection Sort)은 원소를 나머지 원소와 비교해서 가장 작은 원소를 찾고 그 원소와 자리를 교환하는 알고리즘입니다.

첫 번째 원소를 두 번째 원소부터 마지막 원소까지 차례대로 비교하면서 가장 값이 작은 원소를 찾고 첫 번째 원소와 가장 값이 작은 원소를 교환합니다. 다음에는 두 번째 원소를 세 번째 원소부터 마지막 원소까지 차례대로 비교하면서 가장 값이 작은 원소를 찾고 교환합니다. 이렇게 마지막에는 뒤에서 두 번째 원소와 첫 번째 원소를 비교하고 교환하면서 정렬이 완료됩니다.

 

선택 정렬 예시

 

선택 정렬 C++ 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>

void Swap(int* a, int* b);

int main()
{
	int number;
	int numbers[1000];

	memset(numbers, 0, sizeof(numbers));

	scanf("%d", &number);

	for (int i = 0; i < number; i++)
	{
		scanf("%d", &numbers[i]);
	}

	int min;

	for (int i = 0; i < number - 1; i++)
	{
		min = i;

		for (int j = i + 1; j < number; j++)
		{
			if (numbers[j] < numbers[min])
				min = j;
		}

		Swap(&numbers[i], &numbers[min]);
	}

	for (int i = 0; i < number; i++)
	{
		printf("%d\n", numbers[i]);
	}
}

void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

 

선택 정렬 시간복잡도

최선	평균	최악
n2	n2	n2