-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
143 lines (132 loc) · 4.56 KB
/
index.html
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
<html>
<head>
<link href="https://fonts.googleapis.com/css?family=Fira+Sans|Roboto&display=swap" rel="stylesheet">
<style>
body {
width: 60ch;
margin: 0 auto;
font-family: 'Roboto', sans-serif;
}
h1, h2, h3 {
font-family: 'Fira Sans', sans-serif;
}
.expand-on-hover {
position: relative;
}
.expand-on-hover:hover .expand-on-hover-wrapper {
opacity: 1;
bottom: 3em;
}
.expand-on-hover-wrapper {
pointer-events: none;
position: fixed;
left: 0;
right: 0;
bottom: -3em;
padding: 0;
opacity: 0;
transition: opacity 0.3s, bottom 0.3s;
background: transparent;
display: flex;
flex-direction: column;
flex-wrap: nowrap;
}
.expand-on-hover-content {
margin: 0 auto;
width: 30em;
background: white;
padding: 1em;
box-shadow: 0 1em 2.5em -0.5em rgba(0,0,0,0.2);
border-radius: 2px;
border: 1px solid #eee;
font-size: 10pt;
line-height: 1.6em;
}
</style>
</head>
<body>
<h1>Sorting Algorithms</h1>
<ul>
<li><a href="insertionsort/index.html">Insertion sort</a></li>
<li><a href="shellsort/index.html">Shell sort</a></li>
<li><a href="gapsort/index.html">Gap sort</a></li>
<hr>
<li><a href="mergesort/index.html">Merge sort</a></li>
<li><a href="inplacemerge/index.html">In-place mergesort</a></li>
<li><a href="weavesort/index.html">Weave sort</a></li>
<hr>
<li>
<a href="quicksort/index.html">Quicksort</a>
<span class="expand-on-hover">
...
<div class="expand-on-hover-wrapper">
<div class="expand-on-hover-content">
<h3>Quicksort</h3>
Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays. The steps are:
<ol>
<li> Pick an element, called a pivot, from the array. </li>
<li> Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it. </li>
<li> Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values. </li>
</ol>
</div>
</div>
</span>
</li>
<li>
<a href="median/index.html">Median of array (quickselect + median of medians)</a>
<span class="expand-on-hover">
...
<div class="expand-on-hover-wrapper">
<div class="expand-on-hover-content">
<h3>Quickselect</h3>
<p>
Quickselect is a divide and conquer algorithm. It finds the k-th
element in an array (for some given k) in average linear time.
</p>
<p>
It achieves this by partitioning the array around a pivot, counting
how many elements are left on each side, and discarding the side
that doesn't contain the k-th element
</p>
<h3>Median of Medians</h3>
<p>
The median of medians algorithm is an approximate median-finding
algorithm. It can be used it to discard large portions of an array
when searching for the exact median, thus speeding up the search.
</p>
<p>
In this case, we use the Quickselect algorithm, and enhance it by
choosing pivots using the median of medians algorithm, which gives
it worse case linear time, instead of just average.
</p>
</div>
</div>
</span>
</li>
<li>
<a href="deterministic_quicksort/index.html">Deterministic Quicksort</a>
<span class="expand-on-hover">
...
<div class="expand-on-hover-wrapper">
<div class="expand-on-hover-content">
<h3>Deterministic Quicksort</h3>
Like quicksort, but uses the "Median of Medians" algorithm to pick
a pivot. This guarantees the O(n log(n)) runtime.
</div>
</div>
</span>
</li>
<hr>
<li><a href="selectionsort/index.html">selection sort</a></li>
<li><a href="heapsort/index.html">heapsort</a></li>
<li><a href="smoothsort/index.html">smoothsort</a></li>
</ul>
<h2>What is this?</h2>
<p>
These are some sorting algorithm visualizations I made between 2017 and 2019.
</p>
<p>
Most of them are well-known algorithms, but there's also one I invented: "Gapsort". It is in a class of sorting algorithms known as "Library sorts", those being a variant of insertion sorts. Though library sorts can theoretically be implemented in O(N log N) with O(1) extra space, Gapsort is quadratic on average (though a lot faster than insertion sort).
</p>
</body>
<html>