선택 정렬 (Selection Sort)

선택 정렬 : 선택 정렬은 0번 인덱스부터 n - 2의 인덱스에 대하여 해당 인덱스에 들어가야 할 원소를 선택하는 알고리즘입니다. 리스트에서 가장 작은(또는 가장 큰) 원소를 찾아 첫 번째 원소와 교환하고, 그 다음 두 번째로 작은 원소를 찾아 두 번째 원소와 교환하는 과정을 n - 1번 반복합니다. n - 1번인 이유는 마지막에 남은 원소는 마지막이 제자리이기 때문!

 - 선택 정렬은 O(n^2)의 시간 복잡도를 가집니다.

 - 선택 정렬은 불안정 정렬입니다. 동일한 값의 원소들이 입력 순서와 다르게 배치될 수 있습니다.

 - 선택 정렬은 추가적인 메모리를 거의 사용하지 않기 때문에 제자리 정렬(In Place Sort, O(1)의 공간 복잡도)입니다.

 

오름차순 예시

소스 코드

struct Num
{
	int idx;
	int num;

	Num(int idx, int num)
		: idx(idx), num(num) {};
};

void AscendingSelectionSort(vector<Num>& arr)
{
	for (int i = 0; i < arr.size() - 1; ++i)
	{
		int minIndex = i;
		for (int j = i; j < arr.size(); ++j)
		{
			if (arr[minIndex].num > arr[j].num)
			{
				minIndex = j;
			}
		}

		swap(arr[i], arr[minIndex]);
	}
}

void DscendingSelectionSort(vector<Num>& arr)
{
	for (int i = 0; i < arr.size() - 1; ++i)
	{
		int minIndex = i;
		for (int j = i; j < arr.size(); ++j)
		{
			if (arr[minIndex].num < arr[j].num)
			{
				minIndex = j;
			}
		}

		swap(arr[i], arr[minIndex]);
	}
}

int main(void)
{
	srand(static_cast<unsigned int>(time(NULL)));
	vector<Num> v1;
	vector<Num> v2;
	for (int i = 0; i < 10; ++i)
	{
		v1.push_back(Num(i, rand() % 6));
		v2.push_back(Num(i, rand() % 6));
	}

	cout << "오름차순 정렬 전 : ";
	PrintVector(v1);
	AscendingSelectionSort(v1);
	cout << "오름차순 정렬 후 : ";
	PrintVector(v1);
	cout << "정렬 후 idx \t : ";
	printVectorIdx(v1);
	
	cout << endl;

	cout << "내림차순 정렬 전 : ";
	PrintVector(v2);
	DscendingSelectionSort(v2);
	cout << "내림차순 정렬 후 : ";
	PrintVector(v2);
	cout << "정렬 후 idx \t : ";
	printVectorIdx(v2);

	return 0;
}

 

출력