[알고리즘] selection sort (선택 정렬)

선택정렬

입력 배열 전체에서 최솟값을 '선택'하여 배열의 0번 원소와 자리를 바꾸고, 다음엔 0번 원소를 제외한 나머지 원소에서 최솟값을 선택하여 배열의 1번 원소와 자리를 바꾸고 이러한 방식을 반복하는 정렬하는 알고리즘

• 불안정 정렬(동일한 키 값의 요소 순서가 정렬후 유지x)
  • 이유 : 

• 대용량 데이터에서는 비효율. (비교하는 횟수가 많음)
• 최선의 경우와 최악의 경우 시간복잡도가 같다.

수도코드 및 시간복잡도

입력 : 크기가 n인 배열 A
출력 : 정렬된 배열 A
for i = 0 to n-2
{
	min = i
	for  j=i+1 to n-1{
		if A[j] < A[min]
			min = j
}
	A[i] <-> A[min]
}
return 배열A

• i for 루프가 n-1번 수행되는데, i = 0일때 n-1번 비교, i = 1일때 n-2번 비교... 이므로, 선택정렬의 시간복잡도는 n(n-1)/2 O(1) = O(n^2) 이다

구현 코드 (c)

/*
입력 : 크기가 n인 배열 A
출력 : 정렬된 배열 A
for i = 0 to n-2
{
min = i
for  j=i+1 to n-1{
if A[i] < A[min]
min = j
}
A[i] <-> A[min]
}
return 배열A
*/
#include <stdio.h>
void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void selectionsort(int a[], int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int min = i;
		for (int j = i + 1; j < n; j++)
		{
			if (a[j] < a[min])
				min = j;
		}
		swap(&a[i], &a[min]);
	}

	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}

int main()
{
	int a[] = { 40,10,50,90,20,80,30,60 };
	int n = sizeof(a) / sizeof(int);
	selectionsort(a,n);
	return 0;
}

BOJ (백준)

23882 (C++)

https://www.acmicpc.net/problem/23882

23882번: 알고리즘 수업 - 선택 정렬 2

위의 코드에서는 min을 먼저 정렬했다면 아래 코드에서는 max를 먼저 정렬하도록 하여 순서를 다르게하였다.

/*
입력 : 배열 크기N, 교환 횟수,K
출력 : K번 교환후, 배열 출력
selectionsort ( A, K )
{
for i =0 to n-2
{
count = 0
min= i
	for j = i+1 to n-1
		if A[min] > A[j]
			min = j

}
if (i != min)
	swap A[min] <-> A[i]
	count++;
if count == K
	break
}
*/
#include <iostream>
using namespace std;
void swap(int& a, int& b)
{
	int tmp = b;
	b = a;
	a = tmp;
}
void selectionsort(int a[], int n, int K)
{
	int count = 0;
	for ( int i = n-1 ; i >= 1 ; i--)
	{
		int max = i;
		for (int j = i-1; j >= 0 ; j--)
		{
			if (a[max] < a[j])
				max = j;
		}
		if (i != max) {
			swap(a[max], a[i]);
			count++;
		}
		if (count == K)
		{
			for (int i = 0; i < n; i++)
				cout << a[i] << " ";
			break;
		}
		

	}
	if (count < K)
	{
		cout << "-1";
	
	}

	
}
int main()
{
	int N,K;
	cin >> N;
	cin >> K;
	int* a = new int[N];
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
	}
	selectionsort(a,N, K);
	return 0;
}

 

23899 (c++)

https://www.acmicpc.net/problem/23899

23899번: 알고리즘 수업 - 선택 정렬 5

아래는 맨 처음에 입력한 배열이 처음부터 같은 경우가 있을 수 있어서, 그 부분을 고려한 거 빼고 나머지 과정은 선택정렬이다.

/*
입력 : 배열 크기N, 교환 횟수,K
출력 : K번 교환후, 배열 출력
selectionsort ( A, K )
{
for i =0 to n-2
{
count = 0
min= i
	for j = i+1 to n-1
		if A[min] > A[j]
			min = j

}
if (i != min)
	swap A[min] <-> A[i]
	count++;
if count == K
	break
}
*/
#include <iostream>
using namespace std;
void swap(int& a, int& b)
{
	int tmp = b;
	b = a;
	a = tmp;
}
int isSame(int a[], int b[], int n)
{
	int count = 0;
	for (int i = 0; i < n; i++)
	{
		if (a[i] == b[i])
			count++;
	}
	if (count == n)
		return 1;
	return 0;
}
void selectionsort(int a[], int b[],int n)
{
	int result = 0;
	for (int i = n - 1; i >= 1; i--)
	{
		int count = 0;
		int max = i;
		for (int j = i - 1; j >= 0; j--)
		{
			if (a[max] < a[j])
				max = j;
		}
		swap(a[max], a[i]);
		//같은지 비교
		for (int i = 0; i < n; i++)
		{
			if (a[i] == b[i])
				count += 1;
		}
		if (count == n)//모두 같다면
		{
			result = 1;
			break;
		}
	
	}
	cout << result;


}
int main()
{
	int N;
	cin >> N;
	int* a = new int[N];
	int* b = new int[N];
	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
	}
	for (int i = 0; i < N; i++)
	{
		cin >> b[i];
	}
	if (isSame(a, b, N)) {
		cout << "1";//처음 같은 배열
		return 0;
	}
	selectionsort(a,b, N);
	return 0;
}