# Bibeknam/programming-techniques

Switch branches/tags
Nothing to show
Fetching contributors…
Cannot retrieve contributors at this time
221 lines (201 sloc) 3.4 KB
 #include #include #include void swap(int* a, int* b) { int temp; temp = *a; *a = *b; *b = temp; } int median_1(int a[]) { return a[0]; } int median_2(int a[]) { return a[1]; } int median_3(int a[]) { int temp; if (a[0] < a[1]) { swap(&a[0], &a[1]); } if (a[0] > a[2]) { a[0] = a[1]; a[1] = a[2]; } else { return a[0]; } if (a[0] > a[1]) { return a[0]; } else { return a[1]; } } int median_4(int a[]) { int temp1, temp2; if (a[0] < a[1]) { swap(&a[0], &a[1]); } if (a[2] > a[3]) { swap(&a[1], &a[2]); } else { temp1 = a[1]; temp2 = a[2]; a[1] = a[3]; a[2] = temp1; a[3] = temp2; } if (a[0] > a[1]) { a[0] = a[1]; a[1] = a[2]; } else { a[1] = a[3]; } if (a[0] > a[1]) { return a[0]; } else { return a[1]; } } // six comparisions int median_5(int a[]) { int temp1, temp2; if (a[0] < a[1]) { swap(&a[0], &a[1]); } if (a[2] > a[3]) { swap(&a[1], &a[2]); } else { temp1 = a[1]; temp2 = a[2]; a[1] = a[3]; a[2] = temp1; a[3] = temp2; } if (a[0] > a[1]) { a[0] = a[1]; a[1] = a[3]; a[3] = a[4]; } else { a[1] = a[2]; a[2] = a[3]; a[3] = a[4]; } if (a[2] > a[3]) { swap(&a[1], &a[2]); } else { temp1 = a[1]; temp2 = a[2]; a[1] = a[3]; a[2] = temp1; a[3] = temp2; } if (a[0] > a[1]) { a[0] = a[1]; a[1] = a[2]; } else { a[1] = a[3]; } if(a[0] > a[1]) { return a[0]; } else { return a[1]; } } int median(int a[], int n){ switch(n) { case 1: return median_1(a); break; case 2: return median_2(a); break; case 3: return median_3(a); break; case 4: return median_4(a); break; case 5: return median_5(a); break; default: break; } return -1; } // select method returns the kth smallest element // median is the n/2 th smallest element // This function runs in linear time int select(int k, int a[], int n) { int **subarrays, *medians, *left, *right; int i, j, l, m,columns, pivot, len_l = 0, len_r = 0; if (n == 1) { return a[0]; } columns = ceil(n / 5.0); subarrays = (int**)malloc(sizeof(int*)*columns); for (i=0;i pivot) { len_r++; } if (a[i] < pivot) { len_l++; } } left = (int*) malloc(sizeof(int*) * len_l); right = (int*) malloc(sizeof(int*) * len_r); l = 0, m = 0; for (i = 0; i < n; i++) { if (a[i] > pivot){ right[l] = a[i]; l++; } if (a[i] < pivot) { left[m] = a[i]; m++; } } if (len_l == k - 1) { return a[0]; } if (len_l > k - 1) { return select(k, left, len_l); } if (len_l < k - 1) { return select(k - len_l - 1, right, len_r); } return -1; } int main() { int array[] = {8,7,12,13,3,4,5,6,19,20,9,10,11,14,15,16,17,18,1,2}; printf("Median is %d\n", select(10, array, 20)); }