aboutsummaryrefslogtreecommitdiff
path: root/impls
diff options
context:
space:
mode:
Diffstat (limited to 'impls')
-rw-r--r--impls/bsearch-gen.el9
-rw-r--r--impls/bsearch.cpp62
-rw-r--r--impls/num-gen.el10
-rw-r--r--impls/pingala.cpp62
-rw-r--r--impls/qsort.cpp130
-rw-r--r--impls/vec.c2
6 files changed, 157 insertions, 118 deletions
diff --git a/impls/bsearch-gen.el b/impls/bsearch-gen.el
deleted file mode 100644
index 79aac56..0000000
--- a/impls/bsearch-gen.el
+++ /dev/null
@@ -1,9 +0,0 @@
-(defconst *LIST-SIZE* 128)
-(defconst *UPPER-BOUND* 1024)
-(with-current-buffer (find-file "bsearch.txt")
- (mapcar
- #'(lambda (res) (insert (format "%s\n" res)))
- (cl-loop
- for i from 0 to *LIST-SIZE*
- collect
- (random *UPPER-BOUND*))))
diff --git a/impls/bsearch.cpp b/impls/bsearch.cpp
index 6172b15..cc7b8e8 100644
--- a/impls/bsearch.cpp
+++ b/impls/bsearch.cpp
@@ -4,6 +4,7 @@
*/
#include <algorithm>
+#include <cassert>
#include <cstdlib>
#include <fstream>
#include <iostream>
@@ -17,9 +18,7 @@ using std::ostream;
using std::string;
using std::vector;
-vector<int> arr;
-
-ostream &print_arr(ostream &os)
+ostream &print_arr(ostream &os, std::vector<int> &arr)
{
os << "[";
for (size_t i = 0; i < arr.size(); ++i)
@@ -27,31 +26,46 @@ ostream &print_arr(ostream &os)
return os << "]";
}
-int bsearch(int n, int l = 0, int u = arr.size() - 1)
+int bsearch(int n, std::vector<int> arr)
{
- int midpoint = ((u + l) / 2);
- if (l >= u || u <= 0)
- return -1;
- int val = arr[midpoint];
- if (val == n)
- return midpoint;
- else if (val > n)
- return bsearch(n, l, midpoint - 1);
- else
- return bsearch(n, midpoint + 1, u);
+ int l = 0;
+ int u = arr.size() - 1;
+ while (l <= u)
+ {
+ int midpoint = l + ((u - l) / 2);
+ int val = arr[midpoint];
+
+ if (val == n)
+ {
+ return midpoint;
+ }
+ else if (val > n)
+ {
+ u = midpoint - 1;
+ }
+ else
+ {
+ l = midpoint + 1;
+ }
+ }
+ return -1;
}
-int main(void)
+int main(int argc, char *argv[])
{
- std::ifstream input("bsearch.txt");
- string line;
- while (std::getline(input, line))
- arr.push_back(std::stoi(line));
+ std::ifstream input(argc > 1 ? argv[1] : "bsearch.txt");
+ std::vector<int> arr;
+
+ for (std::string line; std::getline(input, line);
+ arr.push_back(std::stoi(line)))
+ continue;
+
std::sort(std::begin(arr), std::end(arr));
- string inp;
- cout << "Enter number to search: ";
- cin >> inp;
- int to_search = std::stoi(inp);
- cout << bsearch(to_search) << endl;
+
+ for (size_t i = 0; i < arr.size(); ++i)
+ {
+ int index = bsearch(arr[i], arr);
+ assert(index == (int)i);
+ }
return 0;
}
diff --git a/impls/num-gen.el b/impls/num-gen.el
new file mode 100644
index 0000000..e0ba7e0
--- /dev/null
+++ b/impls/num-gen.el
@@ -0,0 +1,10 @@
+(defconst *LIST-SIZE* 128)
+(defconst *UPPER-BOUND* 1024)
+(with-current-buffer (find-file "nums.txt")
+ (mapcar
+ #'(lambda (res) (insert (format "%s\n" res)))
+ (cl-remove-duplicates
+ (cl-loop
+ for i from 0 to *LIST-SIZE*
+ collect
+ (random *UPPER-BOUND*)))))
diff --git a/impls/pingala.cpp b/impls/pingala.cpp
index 510aa50..dc14f60 100644
--- a/impls/pingala.cpp
+++ b/impls/pingala.cpp
@@ -4,38 +4,39 @@
*/
#include <cstdio>
+#include <iostream>
+#include <sstream>
#include <string>
#include <vector>
-void padding(size_t n, size_t depth)
-{
- for (size_t i = 0; i < ((depth - n) / 2); ++i)
- printf("\t");
-}
-
-void generate_triangle(const size_t depth)
+std::vector<std::string> generate_triangle(const size_t depth)
{
+ std::vector<std::string> levels;
std::vector<size_t> items;
- items.reserve(depth * depth);
+ std::stringstream ss;
+ levels.reserve(depth);
+ items.resize(depth * depth);
+
#define AT(i, j) items[((i) * depth) + (j)]
AT(0, 0) = 1;
- padding(0, depth);
- printf("%lu\n", items[0]);
+ levels.push_back("1");
for (size_t i = 1; i < depth; ++i)
{
AT(i, 0) = 1;
- padding(i, depth);
- printf("%lu,\t", AT(i, 0));
+ ss << "1 ";
for (size_t j = 1; j < i; ++j)
{
- // Recurrence relation
AT(i, j) = AT(i - 1, j - 1) + AT(i - 1, j);
- printf("%lu,\t", AT(i, j));
+ ss << AT(i, j) << " ";
}
AT(i, i) = 1;
- printf("%lu\n", AT(i, i));
+ ss << "1";
+ levels.push_back(ss.str());
+ ss.str(std::string{});
}
#undef AT
+
+ return levels;
}
void usage(FILE *fp)
@@ -46,18 +47,29 @@ void usage(FILE *fp)
int main(int argc, char *argv[])
{
+ // Variable declarations
+ std::vector<std::string> levels;
+ int depth = 0;
+
if (argc < 2)
+ goto error;
+ depth = std::stoi(argv[1]);
+ if (depth <= 0)
+ goto error;
+
+ levels = generate_triangle(depth);
+
+ for (const auto &level : levels)
{
- usage(stderr);
- return 1;
- }
- int arg = std::stoi(argv[1]);
- if (arg <= 0)
- {
- usage(stderr);
- return 1;
+ for (size_t i = 0;
+ i < (levels[levels.size() - 1].size() - level.size()) / 2; ++i)
+ {
+ printf(" ");
+ }
+ printf("%s\n", level.c_str());
}
-
- generate_triangle(arg);
return 0;
+error:
+ usage(stderr);
+ return 1;
}
diff --git a/impls/qsort.cpp b/impls/qsort.cpp
index d3e8c1d..22efbfe 100644
--- a/impls/qsort.cpp
+++ b/impls/qsort.cpp
@@ -4,8 +4,15 @@
* Commentary: The inplace O(nlog(n)) sortitng algorithm. Originally designed
* in C, hence the lack of iostream.
*/
+#include <cstdint>
#include <cstdio>
#include <cstdlib>
+#include <fstream>
+#include <iostream>
+#include <stack>
+#include <vector>
+
+using u64 = uint64_t;
#define ARR_SIZE(XS) (sizeof(XS) / sizeof((XS)[0]))
#define SWAP(A, B) \
@@ -16,85 +23,90 @@
(A) ^= (B); \
} while (0)
-#define TEST_SIZE 20
-
-void print_arr(int *arr, int size)
+void print_arr(u64 *arr, u64 size)
{
- printf("{");
- for (int i = 0; i < size - 1; ++i)
- printf("%d, ", arr[i]);
- printf("%d}", arr[size - 1]);
+ printf("{\n");
+ for (u64 i = 0; i < size; ++i)
+ printf(" %lu,\n", arr[i]);
+ printf("}\n");
}
-void quicksort(int *arr, int arr_size)
+struct Partition
{
-#ifdef TRACE
- printf("before, arr=");
- print_arr(arr, arr_size);
- printf("\n");
-#endif
- // Optimisation: for small arr_size, a different sort like the
- // bubble sort may be better, instead of initialising new stack
- // frames.
- if (arr_size < 2)
- return;
- // Optimisation: Use some heuristics to figure out a better pivot
- // than some constant choice of element.
- int pivot = 0;
- int pivot_value = arr[0];
- for (int i = 1; i < arr_size; ++i)
+ u64 *arr;
+ u64 arr_size;
+};
+
+void quicksort(u64 *arr, u64 arr_size)
+{
+ std::stack<Partition> partitions;
+ partitions.push({arr, arr_size});
+
+ while (!partitions.empty())
{
- if (arr[i] <= pivot_value)
+ const auto partition = partitions.top();
+ arr = partition.arr;
+ arr_size = partition.arr_size;
+ partitions.pop();
+
+ // TODO: Use a different sort for small enough sizes?
+ if (arr_size > 1)
{
- if (i != pivot)
- SWAP(arr[i], arr[pivot]);
- ++pivot;
+ // TODO: Choose a better pivot maybe?
+ u64 pivot = arr[arr_size - 1]; // Choose the last element as pivot
+ u64 pivot_index = -1;
+
+ for (u64 j = 0; j < arr_size; ++j)
+ {
+ if (arr[j] < pivot)
+ {
+ ++pivot_index;
+ std::swap(arr[pivot_index], arr[j]);
+ }
+ }
+
+ std::swap(arr[pivot_index + 1], arr[arr_size - 1]);
+
+ partitions.push({arr, pivot_index + 1});
+ partitions.push({arr + pivot_index + 1, arr_size - pivot_index - 1});
}
}
-
-#ifdef TRACE
- printf("after, arr=");
- print_arr(arr, arr_size);
- printf("\n");
-#endif
- // Optimisation: Use a stack to do this instead of recursion.
- //
- // This algorithm is similar to a pre order traversal/dfs, in this
- // case on an array where left and right partition are children
- // nodes to the original array node. Also with recursion there's a
- // real risk for very large ARR_SIZE of running out of space in the
- // call stack.
- if (pivot != 0)
- quicksort(arr, pivot);
- if (pivot < arr_size - 1)
- quicksort(arr + pivot + 1, arr_size - pivot - 1);
}
-int main(void)
+int main(int argc, char *argv[])
{
- int arr[TEST_SIZE] = {0};
- const int size = TEST_SIZE;
+ (void)argc;
+ (void)argv;
+
+#define TEST_SIZE 10
+ // randomly generate some numbers
+ // u64 *arr = new u64[TEST_SIZE];
+ // u64 arr_size = TEST_SIZE;
- // Generate a completely reverse ordered list
- /*for (size_t i = 0; i < size; ++i) */
- /* arr[TEST_SIZE - i - 1] = i;*/
+ // for (size_t i = 0; i < TEST_SIZE; ++i)
+ // arr[i] = rand() % (2L << 30);
- // Generate a list where the first half is completely sorted and the
- // other half is in reverse order.
- for (size_t i = 0; i < size / 2; ++i)
- arr[i] = i;
- for (size_t i = size / 2; i < size; ++i)
- arr[TEST_SIZE - (i - size / 2) - 1] = i;
+ // Use nums.txt
+ std::ifstream input(argc > 1 ? argv[1] : "nums.txt");
+ std::vector<u64> num_vec;
+
+ for (std::string line; std::getline(input, line);
+ num_vec.push_back(std::stoi(line)))
+ continue;
+ u64 *arr = &num_vec[0];
+ u64 arr_size = num_vec.size();
printf("Before: ");
- print_arr(arr, size);
+ print_arr(arr, arr_size);
printf("\n");
- quicksort(arr, size);
+ quicksort(arr, arr_size);
printf("After: ");
- print_arr(arr, size);
+ print_arr(arr, arr_size);
printf("\n");
+ // delete[] arr;
+
return 0;
}
diff --git a/impls/vec.c b/impls/vec.c
index f73b9fc..442b1cf 100644
--- a/impls/vec.c
+++ b/impls/vec.c
@@ -16,7 +16,7 @@
@brief A vector, consisting of a header and some payload (data).
@details The idea is that the user must never actually interact with this
structure directly, only the data involved. Any vector related functions
- deal with
+ will take the pointer to the data and look behind it to get the header.
*/
typedef struct
{
generated by cgit v1.2.3-13-gbd6f (git 2.30.0) at 2025-10-28 07:59:08 +0000