Chap 6-2. 선택 정렬(selection sort)

선택 정렬이란? 

입력 배열 전체에서 최솟값을 선택하여 배열의 0번 원소와 자리를 바꾸고, 다음엔 0번 원소를 제외한 나머지 원소에서 최솟값을 선택하여, 배열의 1번 원소와 자리를 바꾼다.

 

-이러한 방식으로 마지막에 2개의 원소 중 작은 것을 선택하여 자리를 바꾼다.

 

 

[의사코드]

입력: 크기가 n인 배열 A
출력: 정렬된 배열 A

1. for i = 0 to n-2 //n-1로 한다면 j = i+1 => j = n -1 +1 = n이 되므로 배열을 벗어난다. 
2.    min = i //최솟값의 인덱스 
3.    for j = i+1 to n-1 // A[i]~A[n-1]에서 최솟값을 찾는다.
4.      if A[j] < A[min]
5.        min = j //작은 부분으로 업데이트 하자 
6.     A[i] ↔ A[min] // min이 최솟값이 있는 원소의 인덱스이므로 위치를 swap
7. return A

 

[코드 구현]

최솟값을 고르는 방법 

#include <stdio.h>
#include <stdlib.h>

#define N 8
#define FALSE 0
#define TRUE 1
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

void selectionSort(int A[])
{
	int temp, min;

	printf("Before Sort : ");
	for (int j = 0; j < 0; j++) //배열 출력 
		printf("%d", A[j]);
	printf("\\n");

	printf("\\n <<<<<<<<<<<<<<<<< Selection Sorting .... >>>>>>>>>>>>>>>>>>\\n");
	for (int i= 0; i  <= N - 2; i++) //정렬 과정 
	{
		min = i;

		for (int j = i + 1; j <= N - 1; j++)
			if (A[j] < A[min])
			{
				min = j;
				
			}
		SWAP(A[i], A[min], temp);

		printf(" %d pass >> ", i + 1);

		for (int j = 0; j < N; j++) //배열 출력 
			printf("%d", A[j]);
		printf("\\n");
	}

}

int main()
{
	int A[N] = { 40, 10, 50, 90, 20, 80, 30, 60 };
	selectionSort(A);

	return 0;
}

 

[역방향]

최댓값을 고르는 방법 

#include <stdio.h>
#include <stdlib.h>

#define N 8
#define FALSE 0
#define TRUE 1
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

void selectionSort(int A[])
{
	int temp, max;

	printf("Before Sort : ");
	for (int j = 0; j < 0; j++) //배열 출력 
		printf("%d", A[j]);
	printf("\\n");

	printf("\\n <<<<<<<<<<<<<<<<< Selection Sorting .... >>>>>>>>>>>>>>>>>>\\n");
	for (int i= 0; i  <= N - 2; i++) //정렬 과정 
	{
		max = 0;

		for (int j = 1; j <= N - 1 - i; j++)
			if (A[j] > A[max])
			{
				max = j;
				
			}
		SWAP(A[N-1-i], A[max], temp);

		printf(" %d pass >> ", i + 1);

		for (int j = 0; j < N; j++) //배열 출력 
			printf("%d", A[j]);
		printf("\\n");
	}

}

int main()
{
	int A[N] = { 40, 10, 50, 90, 20, 80, 30, 60 };
	selectionSort(A);

	return 0;
}

 

선택 정렬의 특징

(1) 입력이 거의 정렬되어 있든지, 역으로 정렬되어 있든지, 랜덤하게 되어 있든지 상관없이 평균적으로 항상 일정한 시간 복잡도를 나타낸다.

→ 입력에 민감하지 않은(input insensitive) 알고리즘

 

(2) 원소 간의 자리 바꿈 횟수가 최소인 정렬이다.  → step당 1번의 자리 바꿈

(3) 안정성을 만족하지 않는다. 

 

시간복잡도 

비교 횟수 = (n-1) + (n-2) + .. + 1 = n(n-1)/2 = O(n^2)

이동횟수 = 3(n-1)

-> 여기서 3은 한 번 swap할 때 3번 이동한다는 의미이다. 

전체 시간적 복잡도 O(n^2)