C언어로 구현한 선택정렬

아래 자료는 한국방송통신대학교 인천지역 컴퓨터 과학과

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))이다

*/