아래 자료는 한국방송통신대학교 인천지역 컴퓨터 과학과
2학년 과대표님께서 작성하신 소스코드를 수정한 것입니다.
출처 : http://cafe.daum.net/ICCS/LcpH/20
- 위 사이트는 가입이 필요하며, 등업이 되어야 보실 수 있습니다.
※ for문 내에서 변수선언이 가능하도록 하기 위해 C++로 작성하였습니다. 따라서 아래 소스코드를 실행시키기 위해서 파일의 확장자를 *.cpp로 하셔야 합니다.
-----------------------------------------------------------------------------------------------------------------------
#include<stdio.h>
#include<Windows.h>
/*
선택정렬 함수
- arr : 정렬할 대상의 배열
- length : 배열의 크기(배열원소의 갯수)
*/
void SelectionSort(int arr[], int length)
{
int min = 0;
int temp = 0;
//배열의 갯수만큼 반복동작
for(int i=0 ; i<length ; i++)
{
/*
i번째 이후의 원소들 중에서 가장 작은 값을 가진 원소를 찾는다.
(단, min의 초기값은 i로 설정하고, 아래 반복문을 통해서 min의 값이 변한다.)
min인덱스의 원소값과 그 이후의 모든 원소의 값을 비교하여
더 작은 원소값을 가진 원소를 찾고, 그 원소의 인덱스를 min에 저장한다.
즉 아래 반복문이 끝나면 가장 작은 원소값을 가진 원소의 인덱스가 min에 저장되는 것이다.
예를 들어서,
만약 [3]-[1]-[2] 이라는 배열이 있다고 가정합니다.
** 반복문 1회 반복시 **
[1]-[3]-[2]
** 반복문 2회 반복시 **
[1]-[2]-[3]
** 반복문 3회 반복시 **
[1]-[2]-[3]
※ 배열원소의 갯수만큼 반복동작한다.
그런데, 매 반복시 가장 작은 값을 가진 원소값을 찾아야 하므로 2중 for문을 사용합니다.
따라서 시간복잡도에 의해 O(n2)을 가진다.
*/
min = i;
for(int j=i+1 ; j<length ; j++)
{
if(arr[min] > arr[j]) min = j;
}
//i번째 원소와 min번째 원소값을 교환
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
int main()
{
//배열 선언
int arr[]={30, 20, 40, 35, 5, 10, 45, 50, 25, 15};
//위 배열의 길이
int length = sizeof(arr) / sizeof(*arr);
//선택정렬 함수 호출
SelectionSort(arr, length);
//배열에 담긴 원소를 순차적으로 출력
for(int i=0; i<length ; i++)
{
printf("%d ",arr[i]);
}
system("pause");
return 0;
}
/* 선택정렬 특징
1. 안정적이지 않다.
2. 제자리 정렬이다.
3. 시간복잡도 (최적, 최악, 평균 O(n2))이다
*/
'기타' 카테고리의 다른 글
윈도우8 갑자기 느려질때 대처법 (0) | 2014.02.04 |
---|---|
C언어로 구현한 삽입정렬 (0) | 2013.10.24 |
C언어로 구현한 버블정렬 (0) | 2013.10.24 |
C언어로 구현한 단순연결리스트 (0) | 2013.10.21 |
C언어로 구현한 원형 큐 소스코드 (0) | 2013.10.08 |