diff options
Diffstat (limited to 'usth/ICT2.1/labwork/5')
| -rw-r--r-- | usth/ICT2.1/labwork/5/Ex1.c | 58 | ||||
| -rw-r--r-- | usth/ICT2.1/labwork/5/Ex2.c | 74 | ||||
| -rw-r--r-- | usth/ICT2.1/labwork/5/README.pdf | bin | 0 -> 256485 bytes | |||
| -rw-r--r-- | usth/ICT2.1/labwork/5/README.tex | 143 | ||||
| -rw-r--r-- | usth/ICT2.1/labwork/5/TT5.pdf | bin | 0 -> 465238 bytes | |||
| -rw-r--r-- | usth/ICT2.1/labwork/5/construct.c | 27 | ||||
| -rw-r--r-- | usth/ICT2.1/labwork/5/construct.h | 15 |
7 files changed, 317 insertions, 0 deletions
diff --git a/usth/ICT2.1/labwork/5/Ex1.c b/usth/ICT2.1/labwork/5/Ex1.c new file mode 100644 index 0000000..e64c6ea --- /dev/null +++ b/usth/ICT2.1/labwork/5/Ex1.c @@ -0,0 +1,58 @@ +/* + * Cocktail shaker sorting integers from stdin + * Copyright (C) 2019, Nguyễn Gia Phong + * This software is licenced under a CC BY-SA 4.0 license + */ + +#include <stdio.h> + +void strswap(char *this, char *that, size_t n) +{ + while (n--) { + this[n] ^= that[n]; + that[n] ^= this[n]; + this[n] ^= that[n]; + } +} + +void csort(void *base, size_t nmemb, size_t size, + int (*compar)(const void *, const void *)) +{ + char *i, *low = base; + char *high = low + nmemb * size; + do { + char *h = i = low; + while ((i += size) < high) + if (compar(i - size, i) > 0) + strswap(i - size, h = i, size); + high = h; + if (low + size >= high) + break; + char *l = i = high; + while ((i -= size) > low) + if (compar(i - size, i) > 0) + strswap(i - size, l = i, size); + low = l; + } while (low + size < high); +} + +int cmp(const void *x, const void *y) +{ + return *(int *) x - *(int *) y; +} + +int main() +{ + size_t n; + scanf("%zu", &n); + int a[n]; + for (int i = 0; i < n; i++) + scanf("%d", a + i); + + csort(a, n, sizeof(int), cmp); + for (int i = 0; i < n; i++) + printf("%d ", a[i]); + putchar(10); + + return 0; +} diff --git a/usth/ICT2.1/labwork/5/Ex2.c b/usth/ICT2.1/labwork/5/Ex2.c new file mode 100644 index 0000000..edb5c26 --- /dev/null +++ b/usth/ICT2.1/labwork/5/Ex2.c @@ -0,0 +1,74 @@ +/* + * Merge sorting integers from stdin + * Copyright (C) 2019, Nguyễn Gia Phong + * This software is licenced under a CC BY-SA 4.0 license + */ + +#include <stdio.h> +#include <stdlib.h> + +#include "construct.h" + +construct *merge(construct *left, construct *right, + int (*compar)(const void *, const void *)) +{ + if (left == NULL) + return right; + if (right == NULL) + return left; + if (compar(car(left), car(right)) <= 0) + return cons(car(left), merge(cdr(left), right, compar)); + return cons(car(right), merge(left, cdr(right), compar)); +} + +construct *msort(construct *list, int (*compar)(const void *, const void *)) +{ + construct *rest, *left = NULL, *right = NULL; + while (list != NULL) { + left = cons(car(list), left); + rest = cdr(list); + if (rest == NULL) + break; + right = cons(car(rest), right); + list = cdr(rest); + } + if (left == NULL) + return right; + if (right == NULL) + return left; + return merge(msort(left, compar), msort(right, compar), compar); +} + +int cmp(const void *x, const void *y) +{ + return *(int *) x - *(int *) y; +} + +construct *iread(size_t n) +{ + if (!n) + return NULL; + int *tmp = malloc(sizeof(int)); + scanf("%d", tmp); + return cons(tmp, iread(n - 1)); +} + +void iprint(construct *list) +{ + if (list == NULL) { + putchar(10); + } else { + printf("%d ", *(int *) car(list)); + iprint(cdr(list)); + } +} + +int main() +{ + size_t n; + + scanf("%zu", &n); + iprint(msort(iread(n), cmp)); + + return 0; +} diff --git a/usth/ICT2.1/labwork/5/README.pdf b/usth/ICT2.1/labwork/5/README.pdf new file mode 100644 index 0000000..8a94167 --- /dev/null +++ b/usth/ICT2.1/labwork/5/README.pdf Binary files differdiff --git a/usth/ICT2.1/labwork/5/README.tex b/usth/ICT2.1/labwork/5/README.tex new file mode 100644 index 0000000..4c71999 --- /dev/null +++ b/usth/ICT2.1/labwork/5/README.tex @@ -0,0 +1,143 @@ +\documentclass[a4paper,12pt]{article} +\usepackage[english,vietnamese]{babel} +\usepackage{amsmath} +\usepackage{hyperref} +\usepackage{lmodern} +\usepackage{mathtools} + +\title{Algorithms and Data Structures\\ Searching and Sorting} +\author{Nguyễn Gia Phong---BI9-184} +\date{\dateenglish\today} + +\begin{document} +\maketitle +\section{Cocktail Shaker Sort} +The code is implemented following the cocktail shaker sort's +pseudocode\footnote{\url{https://en.wikipedia.org/wiki/Cocktail\_shaker\_sort\#Pseudocode}} +with bubble sort's optimization\footnote{\url{https://en.wikipedia.org/wiki/Bubble\_sort\#Optimizing\_bubble\_sort}} +whose time complexity is analyzed as follows + +\subsection{Best Case} +For the matter of brevity, we consider all operations on the array's $n$ members +are in constant time ($\Theta(1)$). If the array is already sorted, after +the first \verb|while| loop (line 25), \verb|h| is still \verb|low| and thus +the \verb|do|--\verb|while| loop is broken. Since the while loop runs from +\verb|low + size| to \verb|high - size| by \verb|size| steps, the running time +is \verb|(high - low - size*2)/size + 1| or \verb|nmemb - 1|. Therefore +the best case time complexity is $\Omega(n - 1) = \Omega(n)$. + +\subsection{Average Case} +Assume the average case is when the array is uniformly shuffled, that is, +every permutation has the equal probability to occur. + +Given a permutation of an $n$-element array, consider the positive integer +$k \le n$ that exactly the last $n - k$ members are continuously in the +correct positions (as in the ascendingly sorted array). It is obvious that +for $k = 1$, the array is sorted and the probability of the permutation +to appear is $1/n!$. For $1 < k \le n$, if we fix the last $n - k$ members +in their right places, out of the $k!$ permutations of the first $k$ elements, +$(k - 1)!$ ones has the $k$-th greatest at the correct place. Therefore, +let $X$ be the number that exactly $n - X$ last elements are in +the right positions, we have +\[p_X(k) = \begin{dcases} + \frac{1}{n!} &\text{if }k = 1\\ + \frac{k! - (k - 1)!}{n!} &\text{otherwise} +\end{dcases}\] + +Applying this to the first \verb|while| (line 25) with $n$ and $X - 1$ being +the number of steps from \verb|low| to \verb|high|, before and after +\verb|high = h| respectively, the expectation of $X$ is +\begin{align*} + \mathbf E[X] &= \sum_{k=1}^n k p_X(k)\\ + &= \frac{1}{n!} + \sum_{k=2}^n\frac{k!k - k!}{n!}\\ + &= \frac{1}{n!} + \sum_{k=3}^{n+1}\frac{k!}{n!} + - \sum_{k=2}^n\frac{k!}{n!} - \sum_{k=2}^n\frac{k!}{n!}\\ + &= \frac{1}{n!} + \frac{(n+1)!}{n!} + - \frac{2!}{n!} - \sum_{k=2}^n\frac{k!}{n!}\\ + &= n + 1 - \sum_{k=1}^n\frac{k!}{n!}\\ + &= n - \sum_{k=1}^{n-1}\frac{k!}{n!} +\end{align*} + +Hence after line 28, the newly sorted length of the array is +\[n - \mathbf E[X - 1] = n - \mathbf E[X] + 1 + = 1 + \sum_{k=1}^{n-1}\frac{k!}{n!} = \Theta(1)\] + +Similarly, line 31 to 35 also sort $\Theta(1)$ element(s), thus each iteration +of the \verb|do|--\verb|while| loop to sort $\Theta(1)$ members. The overall +average-case time complexity is +\begin{align*} + T(n) &= \begin{dcases} + (n - \Theta(1)) + (n - \Theta(1)) + T(n - \Theta(1)) &\text{if }n > 0\\ + \Theta(1) &\text{otherwise} + \end{dcases}\\ + &= \begin{dcases} + 2n - \Theta(1) + T(n - \Theta(1)) &\text{if }n > 0\\ + \Theta(1) &\text{otherwise} + \end{dcases}\\ + &= \Theta(1) + \sum_{k=1}^m(2k - \Theta(1)) + = 2\sum_{k=1}^m k - \sum_{k=1}^m\Theta(1) + = m^2 + m - \sum_{k=1}^m\Theta(1) +\end{align*} +where $m$ satisfies +\begin{multline*} + \exists\{f_k\mid k\in 1\,..\,m\} \subset \Theta(1),\, + \sum_{k=1}^m f_k(n) = n + \Longrightarrow \sum_{k=1}^m\Theta(1) = \Theta(n) + \Longrightarrow m = \Theta(n)\\ + \Longrightarrow T(n) = \Theta\left(n^2\right) + \Theta(n) - \Theta(n) + = \Theta\left(n^1\right) +\end{multline*} + +\subsection{Worst Case} +If the array is reversely sorted, after each first \verb|while| (line 25), +\verb|high| is decreased by \verb|size|; and after each second +\verb|while| (line 32), \verb|low| is increased by \verb|size|. +For \verb|low + size >= high|, it takes \verb|(high-low-size)/size + 1 >> 1| +or \verb|nmemb / 2| iterations of the \verb|do|--\verb|while| loop (line 23). +The overall complexity would then be +\begin{align*} + \sum_{k=1}^{\lfloor n/2\rfloor}(n - 2k + 1 + n - 2k) + &= \sum_{k=1}^{\lfloor n/2\rfloor}(2n - 4k + 1)\\ + &= n^2 + 2\left\lfloor\frac{n}{2}\right\rfloor + \left(\left\lfloor\frac{n}{2}\right\rfloor + 1\right) + + \left\lfloor\frac{n}{2}\right\rfloor\\ + &= O\left(n^2\right) +\end{align*} + +\section{Merge Sort} +As usual, the linked list is implemented using classic Lisp's \verb|cons|-cells. +The program is thus compiled by +\begin{verbatim} +cc construct.c Ex2.c -o Ex2 +\end{verbatim} + +To keep the implementation concise, memory safety as well as stack limit +was not considered. + +It is trivial that the time complexity of \verb|merge| is $\Theta(n)$ with +$n$ being the total length of \verb|left| and \verb|right|. For \verb|msort|, +the running time of the \verb|while| loop at line 27 is also $\Theta(n)$, where +n is the length of the input \verb|list|. The overall time complexity is +\[T(n) = \begin{dcases} + \Theta(1) &\text{if }n \le 1\\ + \Theta(n) + T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + + T\left(\left\lceil\frac{n}{2}\right\rceil\right) &\text{otherwise} +\end{dcases}\] + +The recurrence can be stated as +\[T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)\] +\pagebreak + +By the master theorem\footnote{Let $a \ge 1$ and $b > 1$ be constants, +and let $T(n)$ be defined on the nonnegative integers by the recurrence +\[T(n) = aT\left(\frac{n}{b}\right) + \Theta\left(n^{\log_b a}\right)\] +where $n/b$ is interpreted as either $\lfloor n/b\rfloor$ or $\lceil n/b\rceil$, +then \[T(n) = \Theta\left(n^{\log_b a}\lg n\right)\]}, +\[T(n) = 2T\left(\frac{n}{2}\right) + \Theta\left(n^{\log_2 2}\right) += \Theta\left(n^{\log_2 2}\lg n\right) = \Theta(n\lg n)\] + +\section{Copying} +This report along with the source files are licensed under a +\href{https://creativecommons.org/licenses/by-sa/4.0/}{Creative Commons +Attribution-ShareAlike 4.0 International License}. +\end{document} diff --git a/usth/ICT2.1/labwork/5/TT5.pdf b/usth/ICT2.1/labwork/5/TT5.pdf new file mode 100644 index 0000000..1038597 --- /dev/null +++ b/usth/ICT2.1/labwork/5/TT5.pdf Binary files differdiff --git a/usth/ICT2.1/labwork/5/construct.c b/usth/ICT2.1/labwork/5/construct.c new file mode 100644 index 0000000..235f900 --- /dev/null +++ b/usth/ICT2.1/labwork/5/construct.c @@ -0,0 +1,27 @@ +/* + * Lisp construct implementation. + * Copyright (C) 2019, Nguyễn Gia Phong + * This software is licenced under a CC BY-SA 4.0 license + */ + +#include <stdlib.h> + +#include "construct.h" + +construct *cons(void *first, construct *rest) +{ + construct *list = malloc(sizeof(construct)); + list->car = first; + list->cdr = rest; + return list; +} + +void *car(construct *list) +{ + return list->car; +} + +construct *cdr(construct *list) +{ + return list->cdr; +} diff --git a/usth/ICT2.1/labwork/5/construct.h b/usth/ICT2.1/labwork/5/construct.h new file mode 100644 index 0000000..a27a1c3 --- /dev/null +++ b/usth/ICT2.1/labwork/5/construct.h @@ -0,0 +1,15 @@ +/* + * Lisp construct header. + * Copyright (C) 2019, Nguyễn Gia Phong + * This software is licenced under a CC BY-SA 4.0 license + */ + +typedef struct list construct; +struct list { + void *car; + construct *cdr; +}; + +construct *cons(void *, construct *); +void *car(construct *); +construct *cdr(construct *); |