이번 포스팅에서는 선택정렬(Selection Sort) 알고리즘을 증명해보자. selection sort 는 알고리즘을 처음 접하면 알게 되는 녀석이다. 하지만 이 역시 수학적으로 엄밀하게 증명해본 적이 없어 이를 증명해보고자 한다. selection sort 소스코드 // Selection Sort int sort(int a[], int n){ int i, j, m, t; for(i=0;i k-1 이라면 a[k-1] < a[x] 가 성립한다. Proof Invariant 수학적 귀납법을 이용해 불변조건을 증명해보자. Base k=0일 때 (1)은 null condition, true. (2)도 null이므로, true. 성립할 조건이 아예 없으면 true이다. 따라서 Invariant 는 성립한다. S..

다음 숫자들을 오름차순으로 정렬하는 알고리즘을 작성하시오. 1 10 5 8 7 6 4 3 2 9 가장 간단하면서도 쉽게 떠오르는 방법으로 알고리즘을 작성해봅시다. 배열을 탐색하여 가장 작은 값을 앞으로 보내면 어떨까? 순차적으로 가장 작은 숫자를 탐색해 맨 앞쪽과 자리를 바꾸어 줍니다. 가장 기초적이고 원시적인 선택정렬 알고리즘입니다. 소스코드 public class TestMain { public static void main(String[] args) { int[] array = {1,10,5,8,7,6,4,3,2,9}; for(int i=0;i