19 11 ( ) 2019.4.20 1 / 1.1 ( n n O(n 2 O(n 2 ) ( 1 d n 1 n logn O(nlogn n ( n logn C 1.2 ( ( merge 2 1 1 3 1 4 5 4 2 3 7 9 7 1 2 3 4 5 7 9 1: 2 ivec merge int *ivec_new(int size) { int *a = (int*)malloc((size+1) * sizeof(int)); a[0] = size; return a; int *ivec_merge(int *b, int *c) { int ib = 1, ic = 1, ia = 1, *a = ivec_new(b[0]+c[0]); while(ia <= a[0]) { 1
if(ib > b[0]) { a[ia++] = c[ic++]; else if(ic > c[0]) { a[ia++] = b[ib++]; else if(c[ic] < b[ib]) { a[ia++] = c[ic++]; else { a[ia++] = b[ib++]; return a; 2 a ia a ib ic b c ( 1 a b c ( c b ( 2 ( a ( a 1.3 1 1 ( 1 2 2 deq 1 enq 7 1 13 4 4 enq 10 18 19 8 12 22 11 15 9 20 3 5 deq x 2 21 17 13 17 21 2: 1 1 // mergesort1 --- merge sort unsing queue #include <stdlib.h> #include "pqueue.h" (ivec_new, ivec_merge ) void mergesort1(int *a, int n) { pqueuep q = pqueue_new(n+1); int *v, *w; for(int i = 0; i < n; ++i) { v = ivec_new(1); v[1] = a[i]; pqueue_enq(q, v); while(true) { v = (int*)pqueue_deq(q); if(pqueue_isempty(q)) { break; w = (int*)pqueue_deq(q); pqueue_enq(q, ivec_merge(v, w)); free(v); free(w); for(int i = 0; i < n; ++i) { a[i] = v[i+1]; 2
( ( ( n 1 enq 2 deq enq ( 2 free 1 1 ( ( pstack expect sort iarray ( 2 1 ( 1.4 1 n 2 // mergesort2 --- merge sort with recuresive division #include <stdlib.h> (merge ) static void ms(int *a, int i, int j, int *b) { if(i >= j) { return; int k = (i + j) / 2; ms(a, i, k, b); ms(a, k+1, j, b); merge(b, a+i, k-i+1, a+k+1, j-k); for(k = 0; k < j-i+1; ++k) { a[i+k] = b[k]; void mergesort2(int *a, int n) { int *b = (int*)malloc(n * sizeof(int)); ms(a, 0, n-1, b); free(b); mergesort2 ms ms ms (i j b 1 k i k k+1 j 1 2 1 2 a+i a+k+1 b a 3 merge ( n 3
1.5 2 ( 2 1 ( 3 p (partition ( p p p ( 3 (quick sort p merge sort quick sort p sorted sorted partition merge x < p p x > p sorted sorted p sorted 3: quicksort qs qs p // quicksort --- quick sort with recuresive division static void iswap(int *a, int i, int j) { int x = a[i]; a[i] = a[j]; a[j] = x; void qs(int *a, int i, int j) { if(j <= i) { return; int s = i, pivot = a[j]; for(int k = i; k < j; ++k) { if(a[k] < pivot) { iswap(a, s++, k); iswap(a, j, s); qs(a, i, s-1); qs(a, s+1, j); void quicksort(int *a, int n) { qs(a, 0, n-1); s p k p s s s 1 p s p p p ( 4 ( ( ( : ) 1.6 (bogo sort 4
5 (10 ( 6 ( 2 2 2.1 2 (tree ( (root (node ( (parent (child ( 0 (leaf 2 2 (binary tree3 (N-ary tree 2 2 2 2 (full binary tree 2 (complete binary tree (1 2 ( 2 n 1 (2 N 2 4 ( 2 1 N-ary tree root binary tree full binary tree complete binary tree (1) complete binary tree (2) (array rep.) 0 1 2 leaf 3 4 5 6 7 8 9 4: 2 2 (2) 0 i( i 2i+1 2i+2 ( i (i 1)/2 4 2 1 2.2 2 (heap malloc 1 (maximum heap ( 1 C 0 1 2i 2i+1 i/2 5
( (heap sort 1 ( logn 5 8 ( 5 8 15 8 13 11 13 11? 13 11 8 7 9 6 4 7 9 6 4 7 9 6 4 3 5 8 3 5 3 5 5: 8 2 ( ) 8 OK ( 5 8 (pushdown n 2 ( log 2 n logn O(nlogn 1 ( OK n logn O(nlogn 2.3 P L R define define i iswap k if 1 k (k ( 6
k k // heapsort1 --- heap sort using balanced bin-tree #define P(i) ((i-1)/2) #define L(i) (2*i+1) #define R(i) (2*i+2) static void iswap(int *a, int i, int j) { int x = a[i]; a[i] = a[j]; a[j] = x; void pd(int *a, int i, int j) { for(int k = L(i); k <= j; ) { if(k < j && a[k] < a[k+1]) { ++k; if(a[p(k)] >= a[k]) { break; iswap(a, P(k), k); k = L(k); void heapsort1(int *a, int n) { for(int i = n-1; i >= 0; --i) { pd(a, i, n-1); for(int i = n-1; i > 0; --i) { iswap(a, 0, i); pd(a, 0, i-1); 1 1 ( 7 maxbuf ( n n ( 1 2 ( (push up 2.4? option 2 2 _0_ 1 2 3 4 5 6 0 ( 7
q l r p / x s m ( s % gcc8 heapgame.c -lncurses %./a.out 7 // heapgame.c --- construct heap and remove max screen game. #include <stdio.h> #include <stdbool.h> #include <ncurses.h> #include <stdlib.h> #include <time.h> #define P(i) ((i-1)/2) #define L(i) (2*i+1) #define R(i) (2*i+2) #define MAXARR 128 static int a[maxarr]; static int max, cur = 0; static void pos(int n, int *x, int *y) { int y1 = 0, x1 = 0; for(int i = 1; i <= n; ++i) { if(i==1 i==3 i==7 i==15 i==31 i==63) { ++y1; x1 = 0; else { ++x1; *x = x1; *y = y1; static void upd() { char buf[10]; int x, y; for(int i = 0; i < max; ++i) { pos(i, &x, &y); move(y*2+1, x*3+1); sprintf(buf, "%3d", a[i]); addstr(buf); pos(cur, &x, &y); move(y*2+1, x*3+3); void iswap(int *a, int i, int j) { int x = a[i]; a[i] = a[j]; a[j] = x; 8
void shuffle(int *a, int size) { for(int i = 0; i < size; ++i) { iswap(a, i, rand()%(size-i)); bool checkheap(int *a, int size) { for(int i = 1; i < size; ++i) { if(a[p(i)] < a[i]) { return false; return true; int main(int argc, char *argv[]) { max = atoi(argv[1]); if(max > MAXARR) { max = MAXARR; for(int i = 0; i < max; ++i) { a[i] = i; srand(time(null)); initscr(); noecho(); cbreak(); system("stty raw"); clear(); while(true) { upd(); refresh(); int ch = getch(); switch(ch) { case q : endwin(); return 0; // quit case p : if(cur > 0) { cur = P(cur); break; // parent case l : if(l(cur) < max) { cur = L(cur); break; // left-child case r : if(r(cur) < max) { cur = R(cur); break; // right-chlid case x : if(cur > 0) { iswap(a, cur, P(cur)); break; // excange case s : shuffle(a, max); break; // shuffle case m : char *msg = "NG"; // move top elt if(max <= 1) { msg = "GOAL!"; else if(checkheap(a, max)) { iswap(a, 0, max-1); --max; msg = "MOVED"; cur = 0; clear(); move(15, 5); addstr(msg); clrtoeol(); break; default: break; 8 a. b. ( c. ( ncurses getch timeout d. ncurses 9
3 6 ( 3 3 9 3 2 3 3 5 2 3 3 3 5 9 stable 2 3 3 3 5 9 non-stable 6: ( (unsigned short 65536 struct sortval { unsigned short key, seq; ; key seq 9 ( 11A 1 9 1 ( 23:59 1. sol CED /home3/staff/ka002689/prog19upload 11a 2. ( @@@ 3. 1 4. ( ( 5. Q1. Q2. Q3. ( 10
11B : B 11B A 11B 1 1 9 ( 11A ( 2 13 23:69 1. sol CED /home3/staff/ka002689/prog19upload 11b 2. ( @@@ 3. 1 ( ( 4. 2 5. Q1. Q2. Q3. ( 11