1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
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}
|
