commit c2d47e60540c67946cd57ad28ec37a238e8cfdaf
parent 4e525f0ca71f7536e09605ac616c3f2b76b12c9b
Author: zerous Naveen Narayanan <zerous@nocebo.space>
Date: Sun, 3 Mar 2019 22:48:36 +0100
Exercise 2.4 - Solution
Diffstat:
| A | exercise-2-4.c | | | 152 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| D | res.c | | | 131 | ------------------------------------------------------------------------------- |
2 files changed, 152 insertions(+), 131 deletions(-)
diff --git a/exercise-2-4.c b/exercise-2-4.c
@@ -0,0 +1,152 @@
+#include <error.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+/* Solution - Exercise 2-4
+ * Compare insertion sort and quick sort (library routine)
+ * strings are used as opposed to integers
+ *
+ * Observation:
+ * Found that insertion sort took ~9 mins to sort a string array
+ * of size 12.3 MB in comparison with qsort which took >1 min.
+ */
+
+void delstr(char *);
+void genstrstore(void);
+void isort(int (*)(const void *, const void *));
+void store(char);
+void strstore(char *);
+
+char *buf;
+char *end;
+char *nextelem;
+char **strbuf;
+char **strnextelem;
+char **strend;
+
+int
+comp(const void *a, const void *b)
+{
+ char *k = (char *)a;
+ char *j = (char *)b;
+
+ return *k - *j;
+}
+
+int
+qcomp(const void *a, const void *b)
+{
+ char *s = *(char **)a;
+ char *t = *(char **)b;
+
+ return *s - *t;
+}
+
+
+int
+main(int argc, char **argv)
+{
+ char c;
+
+ while ((c = getc(stdin)) != EOF) {
+ store(c);
+ }
+
+ genstrstore();
+
+ qsort(strbuf, strnextelem - strbuf, sizeof(char *), qcomp);
+ /* isort(comp); */
+ for (char **t = strbuf; t < strnextelem ; t++) {
+ printf("%s\n", *t);
+ }
+
+ free(strbuf);
+ free(buf);
+
+ return 0;
+}
+
+void
+genstrstore(void)
+{
+ for (char *c = buf; c < nextelem; c++) {
+ if (c == buf)
+ strstore(c);
+
+ if(*c == '\n') {
+ *c = '\0';
+ c++;
+ strstore(c);
+ }
+ }
+}
+
+
+void
+store(char c)
+{
+ static int growthfact = 1;
+ char *t;
+
+ if (nextelem == end) {
+ if ((t = realloc(buf, growthfact * 512 * sizeof(char))) == NULL)
+ error(1, 1, "realloc");
+
+ nextelem = t + (nextelem - buf);
+ buf = t;
+ end = buf + (growthfact * 512);
+ growthfact++;
+ }
+
+ if (nextelem != end)
+ *nextelem++ = c;
+}
+
+void
+strstore(char *s)
+{
+ static int growthfact = 1;
+ char **t;
+
+ if (strnextelem == strend) {
+ if ((t = realloc(strbuf, growthfact * 512 * sizeof(char *))) == NULL)
+ error(1, 1, "realloc");
+ strnextelem = t + (strnextelem - strbuf);
+ strbuf = t;
+ strend = strbuf + (growthfact * 512);
+ growthfact++;
+ }
+
+ if (strnextelem != strend)
+ *strnextelem++ = s;
+}
+
+void
+delstr(char *s)
+{
+ for (char **t = strbuf; t < strnextelem; t++) {
+ if (strcmp(*t,s) == 0) {
+ memmove(t, t + 1,
+ (strnextelem - t + 1) * sizeof(char *));
+ strnextelem--;
+ return;
+ }
+ }
+}
+
+void
+isort(int (*cmp)(const void *a, const void *b))
+{
+ void **j;
+
+ for (void **t = (void **) strbuf; t < (void **) strnextelem; t++) {
+ j = t - 1;
+ void *val = *t;
+ while ((j - (void **) strbuf) >= 0 && cmp(*j, val) > 0) {
+ *(j + 1) = *j;
+ j--;
+ }
+ *(j + 1) = val;
+ }
+}
+
diff --git a/res.c b/res.c
@@ -1,131 +0,0 @@
-#include <error.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-void delstr(char *);
-void store(char);
-void strstore(char *);
-void isort(void **, int (*)(const void *, const void *));
-
-char *buf;
-char *end;
-char *nextelem;
-char **strbuf;
-char **strnextelem;
-char **strend;
-unsigned long nstr;
-
-int
-comp(const void *a, const void *b)
-{
- char *k = (char *)a;
- char *j = (char *)b;
-
- return *k - *j;
-}
-
-
-int
-main(int argc, char **argv)
-{
- char c;
-
- while ((c = getc(stdin)) != EOF) {
- store(c);
- }
- printf("nstr: %lu\n", nstr);
- /* qsort(strbuf, nstr, sizeof(char *), comp); */
- isort((void **)strbuf, comp);
-
- for (int i = 0; i < nstr; i++)
- printf("%s\n", strbuf[i]);
-
- free(strbuf);
- free(buf);
-
- return 0;
-}
-
-void
-store(char c)
-{
- static int growthfact = 1;
- char *t;
-
- if (nextelem == end) {
- if ((t = realloc(buf, growthfact * 512 * sizeof(char))) == NULL)
- error(1, 1, "realloc");
- nextelem = t + (nextelem - buf);
- buf = t;
- end = buf + (growthfact * 512);
- growthfact++;
- }
-
- if (nextelem != end) {
- if (nextelem == buf) { /* first time */
- strstore(nextelem);
- *nextelem++ = c;
- }
-
- if (c == '\n') {
- *nextelem++ = '\0';
- strstore(nextelem);
- }
- else {
- *nextelem++ = c;
- }
- }
-}
-
-void
-strstore(char *s)
-{
- static int growthfact = 1;
- char **t;
-
- if (strnextelem == strend) {
- if ((t = realloc(strbuf, growthfact * 512 * sizeof(char *))) == NULL)
- error(1, 1, "realloc");
- strnextelem = t + (strnextelem - strbuf);
- strbuf = t;
- strend = strbuf + (growthfact * 512);
- growthfact++;
- }
-
- if (strnextelem != strend) {
- *strnextelem++ = s;
- nstr++;
- }
-}
-
-void
-delstr(char *s)
-{
- for (int i = 0; i < nstr; i++) {
- if (strcmp(strbuf[i],s) == 0) {
- memmove(strbuf + i, strbuf + i + 1,
- (nstr - i - 1) * sizeof(char *));
- nstr--;
- return;
- }
- }
-}
-
-void
-isort(void **ar, int (*cmp)(const void *a, const void *b))
-{
- int j;
-
- for (int i = 1; i < nstr; i++) {
- printf("%d\n", i);
- j = i - 1;
- void *val = ar[i];
- while (j >= 0 && cmp(ar[j], val) > 0) {
- ar[j + 1] = ar[j];
- j--;
- }
- ar[j+1] = val;
- }
-}
-
