정렬알고리즘_선택정렬 [1/8]

[ 선택정렬이란? ]

• 전체 데이터를 모두 검색하는 과정을 반복해서 특정 기준으로 정렬하는 방법
• 쉽게 사용할 수 있으나, O(n^2)의 시간 복잡도를 가지는만큼 매우 비효율적인 정렬 방식
• 수행횟수 : 9 + 8 + 7 + ... + 1 = 9(9+1)/2 = n(n+1)/2

​[ 오름차순 vs 내림차순 ]

왜 항상 헷갈리는 걸까요..

• 내림차순 : 큰 것 → 작은 것 (높은 고도(500)에서 내려간다 (1))
• 오름차순 : 작은 것 → 큰 것 (낮은 고도(1)에서 올라간다(500))

---

 

1. arr[0] ~ arr[9] 중 가장 작은 값을 찾아 "arr[0]"과 바꿔줌
2. arr[1] ~ arr[9] 중 가장 작은 값을 찾아 "arr[1]"과 바꿔줌
3. arr[2] ~ arr[9] 중 가장 작은 값을 찾아 "arr[2]"와 바꿔줌
4. ...반복...
5. arr[8] ~ arr[9] 둘 중 작은 값을 찾아 "arr[8]"과 바꿔줌

 

인터넷에 있는 코드들을 보면 "j = i" 로 시작하는 경우도 있고 "i < SIZE" 로 범위를 잡는 경우가 있습니다. 하지만 그렇게 되면 굳이 수행하지 않아도 될 내용을 수행하게 되기 때문에 이런 세세한 부분들에 신경을 써주는 것이 중요할 듯합니다. C를 배우는 이유가 세세한 로직 컨트롤을 배우기 위함이니까요. min값도 굳이 99999 같은 큰 값을 줘서 첫 값부터 비교를 시작하는 경우도 많습니다만 굳이 그럴 필요 없이 현재 기준값(arr[i])을 넣어서 그 다음값부터 비교시키면 됩니다.

 

#include <stdio.h>
#define SIZE 10

// 오름차순 정렬
void main()
{
	int arr[SIZE] = { 5,4,9,3,6,7,8,1,2,10 };

	for (int i = 0; i < SIZE - 1; i++) // 마지막 값은 비교할 필요가 없음
	{
		int min = arr[i]; // 가장 첫 값을 기준으로 더 작은 값을 검색함
		int order = i; // 기준은 현재 값
                // 기준값 직후 다음값부터 더 작은값이 있는지 확인
		for (int j = i + 1; j < SIZE; j++) 
		{			
			if (arr[j] < min)
			{
				min = arr[j];
				order = j;
			}
		}

		// i == order일 경우 현재 값이 가장 작다는 뜻이므로 아무것도 수행하지 않음
		if (i != order)
		{
			int temp = arr[i];
			arr[i] = arr[order];
			arr[order] = temp;
		}
	}
	
	for (int i = 0; i < SIZE; ++i)
		printf("%d ", arr[i]);

}