단순 선택 정렬 & 단순 삽입 정렬

단순 선택 정렬(Straight Selection Sort)

가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘

 

배열의 첫번째부터 검색하면서 더 작은수(큰 수를 찾는다면 큰 수)가 있다면 , 스왑을 해주어 정렬을 한다.

 

바로 코드로 보자.

void Selection(int a[], int element)
{
	int i, j;
	for (i = 0; i < element - 1; i++) {
		int min = i;
		for (j = i + 1; j < element; j++)
		{
			if (a[j] < a[min]){
				min = j;
			}
		}
		int temp = a[i];
		a[i] = a[min];
		a[min] = temp;
}

 

1. 첫번째 for문은 총 요소의 -1만큼 돌려준다.

버블정렬때와 마찬가지의 이유로 요소수의 -1만큼만 돌면 전부를 탐색 가능하다.

 

2. 두번째 for문으로 들어가기 전에 최소값이 있는 인덱스를 넣어줄 min에 i값을 넣어준다. 

 

3. 우리는 최소값에 i를 넣어놨으니 j에는 i+1을 넣어서 for문을 돌려주며 요소의 끝까지 탐색한다.

처음에는 a[i] 가 최소값으로 들어가 있으니 a[i] 와 그 다음 인덱스들을 계속 비교해준다.

a[i]보다 작은 값을 만나면 min에는 더 작은 인덱스인 j가 들어간다.

 

4. 두번째 for문이 다 끝나면 min에는 최소값이 들어있는 인덱스가 들어가있다.

처음 설정한 a[i]보다 더 작은값이 있다면 min이 바뀌었을 것이고, 아니라면 min은 a[i] 그대로일 것이다.

 

단순 삽입 정렬(Straight Insertion Sort)

선택한 요소를 그 보다 더 앞쪽의 알맞은 위치에 '삽입하는'작업을 반복하여 정렬하는 알고리즘

 

단순 선택정렬이 위치를 스왑하는 거라면 단순 삽입정렬은 들어가야할 위치에 삽입을 시켜 정렬을 시킨다.

 

이것도 코드로 한번 알아보자.

 

void insertion(int a[], int element)
{
	int i, j;
	for (i = 1; i < element; i++) {
		int tmp = a[i];
		for (j = i; j > 0 && a[j-1] > tmp; j--)
		{
			a[j] = a[j - 1];
		}
		a[j] = tmp;
	}
}

 

1.  첫번째 for문은 i의 1부터 요소의 끝까지 돈다.(비교 대상이 있어야 하기 때문에 1부터 돈다)

 

2. tmp 변수에 a[i]의 값을 넣어준다.

 

3. 두번째 for문은 i부터 돌면서  j가 0보다 크거나, tmp가 앞의 인덱스가 더 클때까지 j를 1씩 빼면서 돈다.

 

4. 조건에 부합하여 for문이 돌아가면 a[ j ] 에 a[ j - 1] (바로 앞 인덱스)를 넣어준다.

 

5. for문이 다시 돌고 조건에 부합하지 않으면, j가 1개 마이너스 되면서 a[ j ]에 처음 설정했던 tmp가 들어가며 정렬된다.

 

시간 복잡도

 

버블정렬, 단순 선택,삽입정렬의 시간 복잡도는 O(n^2)으로 효율이 좋지는 않다.