-
Selection-Sort(선택 정렬)알고리즘/정렬 2018. 12. 17. 19:35
시간 복잡도 : O(n2)
1. 가장 큰 수를 찾는다
2. 가장 큰 수와 맨 오른쪽 수를 교환한다
3. 맨 오른쪽을 제외한다
4. 위 과정을 숫자 하나 남을 때까지 반복한다
예)
[,,8,3,4,6] - 처음 수를 잡고 다음 수와 비교
[5,,8,3,4,6] - 잡고 있는 수보다 다음 수가 크기에 다음 수를 잡는다
[5,,,3,4,6] - 다시 다음 수와 비교
[5,,8,,4,6] - 잡고 있는 수가 더 크기에 그다음 수와 비교
[5,,8,3,,6] - 잡고 있는 수가 더 크기에 그다음 수와 비교
[5,,8,3,4,] - 잡고 있는 수가 더 크기에 그다음 수와 비교
[5,,8,3,4,] - 잡고 있는 수가 가장 크다는 것을 찾음, 가장 오른쪽에 있는 수와 교환
위의 과정을 숫자 하나 남을 때까지 반복
소스 - c언어
#include <stdio.h> #include <stdlib.h> #define MAX 100000 int main() { int n,k,max; int a[MAX]; int i,j; scanf("%d",&n); k=n; for(i=1;i<=n;i++) { a[i] = 0; } for(i=1;i<=n;i++) { scanf("%d",&a[i]); } for(i=1;i<=n;i++) { max=1; for(j=2;j<=k;j++) { if(a[j]>a[max]) { max = j; } } int temp; temp=a[k]; a[k]=a[max]; a[max]=temp; k--; } for(i=1;i<=n;i++) { printf("%d ",a[i]); } return 0; }
피드백 환영
'알고리즘 > 정렬' 카테고리의 다른 글
Bubble-Sort(버블 정렬) (0) 2018.12.17