시간복잡도는 인터넷에서 찾아보니 최소 O($n^2$)의 시간복잡도를 가진다고 한다. 이는 for문이 두개 이상 반복될때의 복잡도로, 어떻게 만들어도 내가 만든 수준으로 가는 듯… 다만 코드를 더 줄일 수 있지 않을까?

홍정모님의 코드와 비교하면서 선택정렬코드를 구현할때의 몇가지 아이디어를 획득했음.

내 코드와 홍정모님의 코드의 가장 큰 차이점은 내 코드에 쓸데없는 동작 2가지가 더 추가되어있다는 것임.

//홍정모 님의 코드
void selectionSort(int arr[], int n)
{
	int i, j, min_idx;

	for (i = 0; i < n - 1; i++)
	{
		min_idx = i;

		for (j = i + 1; j < n; j++)
		{
			if (arr[j] < arr[min_idx])
				min_idx = j;
		}	
		swap(&arr[min_idx], &arr[i]);
	}
	
}

// 내 코드
void sel_sort(int* ar, int n)
{
	for (int i = 0; i < n; i++)
	{
		int* min_index = &ar[i];
		int* count = &ar[i];

		for (int j = i; j < n; j++)
		{
			if (*min_index <= *count)
				;
			else
			{
				min_index = count;
			}
			count++;
		}
		swap(&ar[i], min_index);
	}
}

우선 첫번째로, 가장 바깥쪽 for문은 n까지 탐색할 필요가 없음. n-1해도 충분하다. why? 비교라는건 두가지 항이 필요함. 근데 마지막 하나만 남았을때는 이를 자기 자신과 비교하는 것과 마찬가지임. 내 코드를 보면 j = i이기 때문

두번째로 안쪽 for문은 i+1부터 탐색하면 됨. j=i 이면 안쪽에서 첫 시행은 자기 자신과 비교하는 꼴임. 따라서 j = i+1이 진짜 쪼금 더 최적화 한 방식

이상 모든 선택정렬 알고리즘에서 써먹어야 할 아이디어였고, 홍정모님과 나의 핵심 아이디어 차이는 min_idx를 아예 주소로 주냐, 아님 int형 변수로 써먹을것이냐 차이인듯. 기능상은 동일.

다만 내 방식에서는 마지막에 swap을 위해 원본 arr배열의 주소를 망치기 싫어서 min_idx와 비교할때 필요한 count라는 포인터 변수를 하나 더 만들었어야 했음. 여러모로 홍정모 교수님 코드가 조금 더 최적화 되어있는 듯.

이렇듯 for문을 이용할땐 어째나 저째나 for문을 위해 대부분 사용하는 횟수를 위한 int형 변수들을 잘 써먹는게 변수선언을 최소화 하는 방법인듯.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

문자열의 포인터를 정렬하기

swap이 이해가 안되서 포인터 주소들을 하나하나 나열하면서 디버그 해보려고 한다.

arr