[백준 2750번][C++] 수 정렬하기 - 2. 선택 정렬

<문제 소개>

---

<소스 코드>

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;

int main()
{	
	int N; 
	cin >> N;

	vector<int> v;

	// 원소 입력
	while (N > 0)
	{
		int x;
		cin >> x;

		v.push_back(x);
		N--;
	}

	// 2. 선택정렬
	for (int i = 0; i < v.size() - 1; i++) // 마지막 원소는 정렬할 필요없음(이미정렬되어있으므로)
	{
		// 최소값의 인덱스와 값을 저장할 공간 생성
		int minVal = v[i];
		int minIndex = i;

		for (int j = i + 1; j < v.size(); j++)
		{			
			// 최소값과 해당 인덱스를 찾음
			if (minVal > v[j])
			{
				minVal = v[j];
				minIndex = j;
			}
		}

		// swap
		int temp = v[i];
		v[i] = v[minIndex];
		v[minIndex] = temp;
	}
    
    /* 처음에 잘못 푼 방식
	for (int i = 0; i < v.size() - 1; i++) // 마지막 원소는 정렬할 필요없음(이미정렬되어있으므로)
	{
		// 맨 앞부터 차례대로 정렬
		for (int j = i + 1; j < v.size(); j++)
		{
			// 현재 선택한 인덱스의 원소보다 작은 수인 경우 자리교체
			if (v[i] > v[j])
			{
				int temp = v[i];				
				v[i] = v[j];
				v[j] = temp;
			}
		}
	}
	*/
    
	// 원소 출력
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << endl;
	}

	return 0;
}

 

---

<풀이과정>

1. 첫번째 원소를 선택하고 첫번째 원소와 그 이후의 원소들 중 가장 작은 값과 해당 인덱스를 저장

2. 첫번째 원소와 해당 값의 자리를 교환 -> 첫번째 자리 정렬 완료

3. 다음으로 두번째 자리를 선택 후 두번째 이후 원소들에 대해서 위의 과정을 진행 -> 두번째 자리 정렬 완료

4. 세번째 이후의 자리도 같은 방식으로 자리를 교환하여 정렬

---

<코멘트>

이번엔 두번째 방법인 선택정렬로 풀어보았다!

처음에는 최소값이랑 현재 인덱스랑 계속 바꾸면서 했는데 그게 아니라 인덱스와 값을 찾고 마지막에 교환하는 것이었다.

 

- 선택 정렬 -

장점 

- 버블정렬과 마찬가지로 구현이 쉬움

- 정렬을 위한 비교 횟수는 많지만 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 효율적으로 사용됨

- 버블정렬과 똑같이 O(n^2)의 시간복잡도를 갖지만 실제로 측정하면 조금 더 빠름

 

단점

- 시간복잡도가 항상 O(n^2)을 갖기에 시간이 오래걸리는 정렬 방식

 

특징 

1. 시간복잡도 O(n^2)

2. 공간복잡도 O(1)

3. in-place정렬 

4. not-stable정렬 -> 중복된 값이 순서대로 바뀌지 않을 수 있음(ex { 7,7,1 })

 

<cf>

1. stable vs not-stable

- stable 정렬은 중복된 키 값이 있을 때 이를 순서대로 정렬하는 알고리즘을 뜻함

- 즉 , 정렬했을 때 중복된 키 값이 원래 순서대로 정렬되어있으면 stable 아니면 not-stable이다.

2. in-place vs not in-place

- in- place 정렬은 원소들의 개수에 비해 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘을 뜻함.

- not in-place 정렬은 원소들의 개수에 비례하여 저장 공간을 더 사용하는 정렬 알고리즘을 뜻함.

---

<제출 결과>

<선택 정렬> - 버블정렬에 비해 조금 더 빠르다는 것을 알 수 있음

<비교 - 버블 정렬>