C자료구조 선택정렬 알고리즘(Selection Sort)
- 프로그래밍/알고리즘
- 2019. 4. 13.
c언어로 만든 선택정렬 알고리즘(Selection Sort).
-특정한 일을 수행하기 위한 명령의 유한집합.
-만족 조건.
1.입력: 입력하는 데이터가 하나이상이 있어야한다.
2.출력: 적어도 하나의 결과가 있어야한다
3.명확성: 명령이 명확해야한다.
4.유한성: 반드시 종료되어야한다.
5.유효성: 반드시 실행가능해야한다.
선택정렬 알고리즘
-최소정수를 찾을 수 있어야한다.
-최소정수와 다른값을 교환한다.
-O(n^2)
swap(말 그대로 바꿔주는 함수)
void SWAP(int *x, int *y)
{
int z=*x; //z를 선언하고 z에 x가 가르키는 주소의 내용을 넣는다.
*x=*y; // x의 주소에 y가 가르키는 주소의 내용을 넣는다.
*y=z; //y의 주소에 z의 내용을 넣는다.
}
swap 매크로.
#define SWAP(x,y,z) ((z)=(x), (x)=(y),(y)=(z))
선택정렬.(코드 및 분석)
주어진 리스트 안의 숫자를 작은수에서 큰수로 정렬하는 알고리즘입니다.
이 알고리즘은 앞부분부터 차례대로 정렬합니다.
ex. list[5]={30,20,15,11,24};
이걸로 예시를 하겠습니다.
그전에 먼저 C언어 코드입니다.
void sort (int list[], int n){ //sort함수
int i, j, min, temp;
for(i=0; i<n-1; i++){
min=i;
for(j=i+1;j<n;j++)
if(list[j]<list[min])//비교
min=j; //조건에 맞면 교체
SWAP(list[i],list[min],temp); //위치 교체
}
}그림그리기 귀찮아서 글로 설명합니다.
위의 list[5]={30,20,15,11,24};
1. min=i <--0
2. for문이라 j<n번 반복 (4번까지)
3. list[j]와 list[0]비교.-참
4. 교체. -11-20-15-30-24
5. min=i<--1
6. for문반복 (3번까지)
7.list[j]와 list[1]비교.-참
8.교체 -11-15-20-30-24
9. min=i <<---2
10. for문 반복 (2번까지)
11. list[j]와 list[2]비교 -거짓.
12. 거짓이라 swap넘어감.
13. min=i<----3
14. for문반복 (1번)
15. list[j]와 list[3]비교-참
16. 교체-11-15-20-24-30
...
정렬완료됨.