정렬문제
n개의 숫자들이 주어졌을 때 점점 커지는 오름차순이나 내림차순으로 배열하여 출력하는 문제
.출력
입력된 숫자들의 배열이 조건을 만족하도록 다시 나열한 결과
숫자가 점점 커지는 순서=오름차순
숫자가 점점 작아지는 순서=내림차순
ex)오름차순
input: 5,2,4,6,1,3 일때
출력이
output1,2,3,4,5,6
이어야 문제가 해결되었다고 볼 수 있음
선택 정렬 알고리즘
선택정렬은 무엇인가?
선택하여 정렬하는 알고리즘
무엇을 선택할 것인가?
1. 최소값 선택정렬= 오름차순
a.정렬되지않은 숫자중에 가장 작은 숫자를 선택한다.
b.선택한 숫자를 정렬되지 않은숫자들중 첫번째 숫자와 자리를 바꾸면 선택된 숫자는 정렬된 것이다.
c.이과정을 반복한다.
ex) input 5,4,3,2,1일 경우
a단계 정렬되지 않은 숫자 중 가장작은 숫자인 1을 선택
b.단계 정렬되지 않은 숫자의 첫번째 숫자인 5와 1의 자리를 바꾼다.(14325)
c.단계 2를 선택 해서 4와 변경한다(12345)
정확성 증명
수학적 귀납법을 이용
i번째 선택한 숫자가i번째로 작은 숫자인지 증명
성능분석
주요 함수는 ?
작은 숫자를 찾기 위한 가장 쉬운 방법은?
비교 함수 n개가 있을때 작은수를 뽑는 방법은n-1 n-1일 때는 n-2
입력받은 숫자들의 배열이 어떤 형태면
최악의 경우가 되는가?
최선의 경우가 되는가?
최소만 구하면 되기 때문에 이번의 경우 최악이나 최선은 없다.
2. 최대값 선택정렬= 내림차순