summaryrefslogtreecommitdiff
path: root/Year_1/Programming_2/algorithms
diff options
context:
space:
mode:
Diffstat (limited to 'Year_1/Programming_2/algorithms')
-rw-r--r--Year_1/Programming_2/algorithms/binarysearch.cc33
-rw-r--r--Year_1/Programming_2/algorithms/cbrt.cc37
-rw-r--r--Year_1/Programming_2/algorithms/insertionsort.cc42
-rw-r--r--Year_1/Programming_2/algorithms/log.cc25
-rw-r--r--Year_1/Programming_2/algorithms/mergesort.cc52
-rw-r--r--Year_1/Programming_2/algorithms/pow.cc25
-rw-r--r--Year_1/Programming_2/algorithms/quicksort.cc38
-rw-r--r--Year_1/Programming_2/algorithms/selectionsort.cc46
-rw-r--r--Year_1/Programming_2/algorithms/sqrt.cc46
9 files changed, 344 insertions, 0 deletions
diff --git a/Year_1/Programming_2/algorithms/binarysearch.cc b/Year_1/Programming_2/algorithms/binarysearch.cc
new file mode 100644
index 0000000..c9b4cd7
--- /dev/null
+++ b/Year_1/Programming_2/algorithms/binarysearch.cc
@@ -0,0 +1,33 @@
+#include<iostream>
+
+using namespace std;
+
+bool bs(int a[], int i, int j, int x) {
+ if(j<i) return false;
+ int mid = i+(j-i)/2;
+ if(a[mid] == x)
+ return true;
+ if(a[mid] > x)
+ return bs(a, i, mid-1, x);
+ return bs(a, mid+1, j, x);
+}
+
+bool bs2(int a[], int i, int j, int x) {
+ while(i <= j) {
+ int mid = i+(j-i)/2;
+ if(a[mid] == x) return true;
+ if(a[mid] < x)
+ i = mid+1;
+ else
+ j = mid-1;
+ }
+ return false;
+}
+
+int main() {
+ int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+ for(int i = 0; i < 12; ++i)
+ cout << i << ' '<<bs(a, 0, 9, i) << ' ' << bs2(a, 0, 9, i) << endl;
+ return 0;
+}
+
diff --git a/Year_1/Programming_2/algorithms/cbrt.cc b/Year_1/Programming_2/algorithms/cbrt.cc
new file mode 100644
index 0000000..30c7792
--- /dev/null
+++ b/Year_1/Programming_2/algorithms/cbrt.cc
@@ -0,0 +1,37 @@
+#include<iostream>
+
+using namespace std;
+
+int cbrt(int n) {
+ int i = 0;
+ int j = n;
+ int q = (i+j)/2;
+ while(q*q*q != n) {
+ q = (i+j)/2;
+ if(q*q*q < n)
+ i=q;
+ else
+ j=q;
+ }
+ return q;
+}
+
+double cbrt2(int n) {
+ int i = 1;
+ while(i*i*i <= n)
+ ++i;
+ // precision
+
+ --i;
+ while(i*i*i < n)
+ i+=0.000001;
+
+ return i;
+}
+
+int main() {
+ int i;
+ cin >> i;
+ cout << i << ' ' << cbrt(i) << endl;
+ return 0;
+}
diff --git a/Year_1/Programming_2/algorithms/insertionsort.cc b/Year_1/Programming_2/algorithms/insertionsort.cc
new file mode 100644
index 0000000..9b309d6
--- /dev/null
+++ b/Year_1/Programming_2/algorithms/insertionsort.cc
@@ -0,0 +1,42 @@
+#include<iostream>
+
+using namespace std;
+
+void insertionsort(int a[], int n) {
+ for(int i = 1; i < n; ++i) {
+ int j = i-1;
+ int key = a[i];
+ while(j > -1 && a[j] > key) {
+ swap(a[j+1], a[j]);
+ --j;
+ }
+ a[j+1] = key;
+ }
+}
+
+void insertionsort_rec(int a[], int n) {
+ if(n < 2) return;
+ insertionsort_rec(a, n-1);
+
+ int key = a[n-1];
+ int j = n-2;
+
+ while(j > -1 && a[j] > key) {
+ swap(a[j+1], a[j]);
+ --j;
+ }
+
+ a[j+1] = key;
+
+}
+
+int main() {
+ int arr[10] = {3, 450, 12, 4, -1, 0, 24, 95, 123, 0};
+ for(int i = 0; i < 10; ++i)
+ cout << *(arr+i) << ' ';
+ cout << endl;
+ insertionsort_rec(arr, 10);
+ for(int i = 0; i < 10; ++i)
+ cout << *(arr+i) << ' ';
+ return 0;
+}
diff --git a/Year_1/Programming_2/algorithms/log.cc b/Year_1/Programming_2/algorithms/log.cc
new file mode 100644
index 0000000..1e49a2e
--- /dev/null
+++ b/Year_1/Programming_2/algorithms/log.cc
@@ -0,0 +1,25 @@
+#include<iostream>
+
+using namespace std;
+
+double log(double n) {
+ if(n <= 2) return 1.0;
+ return 1.0 + log(n/2);
+}
+
+int log2(double n) {
+ int a = 1;
+
+ while(n > 2) {
+ n /= 2;
+ ++a;
+ }
+
+ return a;
+}
+
+int main() {
+ for(int i = 0; i < 25; ++i)
+ cout << i << ' ' << log(i) << ' ' << log2(i) << endl;
+ return 0;
+}
diff --git a/Year_1/Programming_2/algorithms/mergesort.cc b/Year_1/Programming_2/algorithms/mergesort.cc
new file mode 100644
index 0000000..68d28cb
--- /dev/null
+++ b/Year_1/Programming_2/algorithms/mergesort.cc
@@ -0,0 +1,52 @@
+#include<iostream>
+
+using namespace std;
+
+void merge(int A[], int l, int q, int r) {
+ int i = l;
+ int j = q+1;
+ int k = l;
+ int B[r];
+
+ while((i <= q) && (j <= r)) {
+ if(A[i] <= A[j])
+ B[k] = A[i++];
+ else
+ B[k] = A[j++];
+
+ k++;
+ }
+
+ while(i <= q)
+ B[k++] = A[i++];
+
+ while(j <= r)
+ B[k++] = A[j++];
+
+ for(k = l; k <= r; ++k)
+ A[k] = B[k];
+}
+
+void mergesort(int A[], int l, int r) {
+ if(l < r) {
+ int q = (l+r)/2;
+ mergesort(A, l, q);
+ mergesort(A, q+1, r);
+ merge(A, l, q, r);
+ }
+}
+
+
+int main() {
+ int a[] = {7,1,22,3,2,12,27,31,6};
+ for(int i = 0; i < 9; ++i) {
+ cout << a[i] << ' ';
+ }
+ cout << endl;
+ mergesort(a, 0, 8);
+ for(int i = 0; i < 9; ++i) {
+ cout << a[i] << ' ';
+ }
+
+ return 0;
+}
diff --git a/Year_1/Programming_2/algorithms/pow.cc b/Year_1/Programming_2/algorithms/pow.cc
new file mode 100644
index 0000000..16cf419
--- /dev/null
+++ b/Year_1/Programming_2/algorithms/pow.cc
@@ -0,0 +1,25 @@
+#include<iostream>
+
+using namespace std;
+
+int pow(int x, int y) {
+ int a = 1;
+
+ for(int i = 0; i < y; ++i)
+ a*=x;
+
+ return a;
+}
+
+
+int pow2(int x, int y) {
+ if(y < 1) return 1;
+
+ return x*pow(x, y-1);
+}
+
+int main() {
+ cout << pow(2, 5) << endl;
+ cout << pow2(2, 5) << endl;
+ return 0;
+}
diff --git a/Year_1/Programming_2/algorithms/quicksort.cc b/Year_1/Programming_2/algorithms/quicksort.cc
new file mode 100644
index 0000000..795bd7b
--- /dev/null
+++ b/Year_1/Programming_2/algorithms/quicksort.cc
@@ -0,0 +1,38 @@
+#include<iostream>
+
+using namespace std;
+
+int partition(int A[], int l, int r) {
+ int x = A[r];
+ int i = l-1;
+
+ for(int j = l; j < r; ++j) {
+ if(A[j] <= x) {
+ swap(A[++i], A[j]);
+ }
+ }
+ swap(A[++i], A[r]);
+ return i;
+}
+
+void quicksort(int A[], int l, int r) {
+ if(l < r) {
+ int q = partition(A, l, r);
+ quicksort(A, l, q-1);
+ quicksort(A, q+1, r);
+ }
+}
+
+int main() {
+ int a[] = {7,1,22,3,2,12,27,31,6};
+ for(int i = 0; i < 9; ++i) {
+ cout << a[i] << ' ';
+ }
+ cout << endl;
+ quicksort(a, 0, 8);
+ for(int i = 0; i < 9; ++i) {
+ cout << a[i] << ' ';
+ }
+
+ return 0;
+}
diff --git a/Year_1/Programming_2/algorithms/selectionsort.cc b/Year_1/Programming_2/algorithms/selectionsort.cc
new file mode 100644
index 0000000..57dcc17
--- /dev/null
+++ b/Year_1/Programming_2/algorithms/selectionsort.cc
@@ -0,0 +1,46 @@
+#include<iostream>
+#include<algorithm>
+
+using namespace std;
+
+void selectionsort(int a[], int n) {
+ for(int i = 0; i < n-1; ++i) {
+ int min = i;
+ for(int j = i+1; j < n; ++j) {
+ if(a[j] < a[min])
+ min = j;
+ }
+
+ swap(a[min], a[i]);
+ }
+}
+
+int min_i(int a[], int i, int j) {
+ if(i == j) return i;
+
+ int k = min_i(a, i+1, j);
+ return (a[i] < a[k]) ? i : k;
+}
+
+void selectionsort_rec(int* a, int b, int e=0) {
+ if(b == e) return;
+
+ int key = min_i(a, e, b-1);
+ if(key != e)
+ swap(a[key], a[e]);
+
+ selectionsort_rec(a, b, e+1);
+}
+
+int main() {
+ int arr[] = {3,450,12,4,-1,0,24,95,123,0};
+ for(int i = 0; i < 10; ++i) {
+ cout << *(arr+i) << ' ';
+ }
+ cout << endl;
+ selectionsort_rec(arr, 10);
+ for(int i = 0; i < 10; ++i) {
+ cout << *(arr+i) << ' ';
+ }
+ return 0;
+}
diff --git a/Year_1/Programming_2/algorithms/sqrt.cc b/Year_1/Programming_2/algorithms/sqrt.cc
new file mode 100644
index 0000000..aa6b032
--- /dev/null
+++ b/Year_1/Programming_2/algorithms/sqrt.cc
@@ -0,0 +1,46 @@
+#include<iostream>
+
+using namespace std;
+
+double abs(double n) {
+ if(n < 0) return -n;
+
+ return n;
+}
+
+
+double sq(int n) {
+ double x = n;
+ double y = 1;
+ while(x-y > 0.0000001) {
+ x = (x+y)/2;
+ y = n/x;
+ }
+ return x;
+}
+
+double sq2_n(double n, double a) {
+ if(abs(a*a - n) <= 0.000001) {
+ return a;
+ }
+
+ return sq2_n(n, (a+n/a)/2);
+}
+
+double sq2(int n) {
+ return sq2_n(n, n/2);
+}
+
+double sqrt_d(int n) {
+ double x = 1;
+ while(abs(x*x-n)>=0.0000001) {
+ x = ((n/x)+x)/2;
+ }
+ return x;
+}
+
+int main() {
+ cout << sq(81) << endl;
+ cout << sq2(81) << endl;
+ return 0;
+}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-10 02:51:26 +0000