Merge Sort : 두 개의 sorting된 배열을 비교하여 더 작은것부터 정렬하여 전체 sortingint sort(int a[], int n){ int h; int b[n]; h = n/2; //copy a[] to b[] sort(b,h); // 왼쪽 sorting sort(b+h, n-h); //오른쪽 sorting // merge two halves in b to a return ;} Proof of invariantsorting의 정의 (invariant)sorting이 끝난 후 배열에 저장된 값들을 b[0], b[1] …b[n-1]라고 부르자 (같은 배열이지만 구별하기 위해)조건 1 : {a[0], a[1], … a[n-1]} = {b[0], b[1] … b[n]} 집합으로 같음조건 2 ..

proof of correctness of sorting (정렬에 대한 증명, 정렬이란 무엇인가)입력 : 정수 집합 {a[0], a[1], ... a[n-1]}sorting이 끝난 후 배열에 저장된 값들을 {b[0], b[1], ... b[n-1]}이라고 하자 (같은 배열이지만 구별하기 위함조건 1 : {a[0], a[1], ... a[n-1]} = {b[0], b[1], ... b[n-1]} 집합으로 같음조건 2 : b[0] Selection sort (선택 정렬) int sort(int a[], int n){ int i, j, m, t; for(i = 0; i a[j]) m = j; t = a[i]; a[i]=a[m]; a[m]=t; } return;}proof of..