<자료구조 알고리즘> 정렬 (선택정렬)

 

정렬이란?

선형 자료구조(배열 등)의 원소들을 특정한 순서(오름차순 내림차순등)로 나열하는 것을 이야기 한다.  정렬 자체가 목적일 때도 있겠지만 대부분 검색등의 다른 알고리즘의 전처리 과정으로 사용되는 경우가 많다. 

 

정렬알고리즘 종류

Permutaion Sort, Selection Sort , Bubble Sort , Quick Sort , Insertion Sort , Merge Sort 등 굉장히 많은 종류의 정렬알고리즘이 있다. 

각 알고리즘의 방식과 구현방법, 시간복잡도를 알아보도록 하자. 

이 글에서는 오름차순을 기준으로 설명하도록 하겠다. 

1. Permutation Sort

모든 경우를 다 확인해보는 정렬 알고리즘이다. 즉 n개의 원소로 만들 수 있는 서로 다른 순열들을 모두 만들면서 정렬이 되어있는지 확인하는 과정을 거쳐서 정렬된 순열을 찾는 알고리즘이다. 

n개의 원소로 만들 수 있는 순열의 개수는 n!이고 그 순열이 정렬된 상태인지 확인하기 위해서는 모든 원소를 한번 씩 보아야 하기 때문에 선형 시간이 걸린다. 따라서 시간복잡도는 $O(n \times n!)$이다. 

 

2. Selection Sort (선택 정렬)

정렬 되지 않은 순열 중 가장 작은 원소를 찾아 첫번째 원소와 위를 바꾸는 방식으로 정렬을 하는 알고리즘이다. 

 

글을 다 읽고 나서 잘 이해가 되지 않는다면 다음 영상을 참고하면 도움이 될 것이다. (속도가 답답하면 2배속으로 ^^)

https://youtu.be/2NeNKvpH-EM

 

각 단계미다 정렬되지 않은 부분에서 가장 작은 원소를 찾아 맨 앞 원소와 위치를 바꾸어 준다. 단계를 한번 진행 할 때마다 원소가 하나씩 정렬 되므로 전체 배열이 정렬되기 위해서는 배열의 길이 만큼 반복해 주면 된다.

 

 

687539를 이 방법을 사용해서 같이 한 번 정렬해 보도록 하자.

그림에서 붉은 색은 (정렬되지 않은 원소들 중) 가장 작은 원소이며

초록색은 정렬된 부분이다.

맨 처음에는 배열의 모든 상태가 정렬되어 있지 않다. 전체 배열에서 가장 작은 값은 3이다.

 

가장 작은 값 3을 맨 앞의 값 6과 위치를 바꾼다. 이제 한개의 원소가 정렬되었다. 

 

이제 정렬되지 않은 원소가 5개가 되었다. 이중에 가장 작은 값 5를 찾는다. 

가장 작은 값 5와 정렬된 배열 바로 뒤 자리의 값 8의 위치를 바꾼다. 이제 두개의 원소가 정렬되었다. 

 

이제 정렬되지 않은 원소가 4개가 되었다. 이중에 가장 작은 값 6을 찾는다. 

가장 작은 값 6과 정렬된 배열 바로 뒤 자리의 값 7의 위치를 바꾼다. 이제 세개의 원소가 정렬되었다. 

이제 정렬되지 않은 원소가 3개가 되었다. 이중에 가장 작은 값 7을 찾는다.  

가장 작은 값 7과 정렬된 배열 바로 뒤 자리의 값 8의 위치를 바꾼다. 이제 두개의 원소가 정렬되었다. 

이제 정렬되지 않은 원소가 2개가 되었다. 이중에 가장 작은 값 8을 찾는다. 

8의 위치가 이미 정렬된 원소들 바로 뒤에 있기 때문에 자리를 바꿀 필요가 없다.

마지막 원소는 자동으로 가장 큰 원소가 남기 때문에 정렬이 완료되었다. 

 

시간복잡도

가장 작은 원소를 찾기 위해서는 모든 원소를 살펴 봐야 하고 이를 배열의 길이 만큼 반복 해야 한다. 한 단계마다 정렬되지 않은 배열의 길이가 하나씩 줄어들기 때문에 총 살펴봐야 하는 횟수는 $\sum^{n}_{i=0}i = \frac{n(n+1)}{2}$이다.

따라서 시간 복잡도는 $O(n^2)$이다. 느리지만 원리가 간단하고 구현이 쉽다는 장점이 있다.

 

 

 

구현

	int smallest;
	for(int i = 0; i < v.size()-1; i++){
		smallest = i;
		
		for(int j = i + 1; j < v.size(); j++){
			if(v[smallest] > v[j]){
				smallest = j;
			}
		}
		
		int tmp = v[smallest];
		v[smallest] = v[i];
		v[i] = tmp;
	}	
}