-
Notifications
You must be signed in to change notification settings - Fork 0
/
quickSort.html
281 lines (250 loc) · 13.8 KB
/
quickSort.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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1">
<!-- The above 3 meta tags *must* come first in the head; any other head content must come *after* these tags -->
<meta name="description" content="">
<meta name="author" content="Oliver Holland">
<title>RLO: Data Structures & Algorithms: Quick Sort</title>
<!-- Bootstrap core CSS -->
<link href="css/bootstrap.min.css" rel="stylesheet">
<!-- Style Sheet - CSS -->
<link href="css/style.css" rel="stylesheet">
<!-- HTML5 shim and Respond.js for IE8 support of HTML5 elements and media queries -->
<!--[if lt IE 9]>
<script src="https://oss.maxcdn.com/html5shiv/3.7.3/html5shiv.min.js"></script>
<script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
<![endif]-->
</head>
<body>
<a id="doc_top"></a>
<div class="container" id="main_container">
<!-- Top Nav-Bar -->
<header class="clearfix" role="banner">
<img src="img/essex.png" alt="University of Essex" width="144" height="59" id="university_logo"
class="pull-right">
<p class="rlo_title">Data Structures & Algorithms</p>
</header>
<nav class="nav nav-pills hidden-xs" role="navigation" id="main_nav">
<div class="btn-group">
<button type="button" class="btn btn-primary dropdown-toggle btn-sm" data-toggle="dropdown">
Contents <span class="glyphicon glyphicon-chevron-down"></span>
</button>
<ul class="dropdown-menu" role="menu">
<li><a href="index.html">Introduction</a></li>
<li><a href="overview.html">Data Structures & Algorithms Overview</a></li>
<li><a href="sortingAlgorithms.html">Sorting Algorithms</a></li>
<li><a href="activity.html">Activity</a></li>
<li><a href="bubbleSort.html">Bubble Sort</a></li>
<li><a href="insertionSort.html">Insertion Sort</a></li>
<li class="active"><a href="quickSort.html">Quick Sort</a></li>
<li><a href="algorithmsInAction.html">Algorithms in Action</a></li>
<li><a href="assessment.html">Assessment</a></li>
</ul>
</div>
<a href="insertionSort.html" class="btn btn-primary btn-sm"><span
class="glyphicon glyphicon-circle-arrow-left"></span>
Previous </a>
<a href="algorithmsInAction.html" id="next_btn" class="btn btn-primary btn-sm">Next <span
class="glyphicon glyphicon-circle-arrow-right"></span></a>
</nav>
<!-- Renders drop-down menu for smaller screen resolutions -->
<div class="visible-xs-block" id="small_screen_menu_container">
<p class="rlo_title">Data Structures & Algorithms</p>
<p><a class="btn btn-primary btn-block" data-toggle="collapse" href="#collapseExample" aria-expanded="false"
aria-controls="collapseExample" id="toggle_ss_nav">
Toggle Navigation <span class="glyphicon glyphicon-remove glyphicon-menu-hamburger"
aria-hidden="true"></span></a></p>
<div class="collapse" id="collapseExample">
<ul class="btn-group btn-group-vertical center-block" role="menu" id="small_screen_menu">
<li><a href="index.html" class="btn btn-info btn-block">Introduction</a></li>
<li><a href="overview.html" class="btn btn-info btn-block">Data Structures & Algorithms Overview</a>
</li>
<li><a href="sortingAlgorithms.html" class="btn btn-info btn-block">Sorting Algorithms</a></li>
<li><a href="activity.html" class="btn btn-info btn-block">Activity</a></li>
<li><a href="bubbleSort.html" class="btn btn-info btn-block">Bubble Sort</a></li>
<li><a href="insertionSort.html" class="btn btn-info btn-block">Insertion Sort</a></li>
<li><a href="quickSort.html" class="btn btn-info btn-block active">Quick Sort</a></li>
<li><a href="algorithmsInAction.html" class="btn btn-info btn-block">Algorithms in Action</a></li>
<li><a href="assessment.html" class="btn btn-info btn-block">Assessment</a></li>
</ul>
</div>
</div>
<!-- Main Content Area -->
<main role="main">
<article>
<a id="content_start"></a>
<h1>Quick Sort</h1>
<div class="row">
<div class="col-md-6" id="text-component">
<p>It is possible to produce a hard-split easy-merge method whose average time for large lists
is <a href="#" data-toggle="modal" data-target="#gloss_o"> O(<i>n</i> log <i>n</i>)</a>.
This algorithm, invented by Hoare in 1962, is known as <b><i>quicksort</i></b>.</p>
<p>Splitting involves producing a list containing all items less than or equal to a particular
value, called the pivot, and another list containing all items greater than the
<a href="#" data-toggle="modal" data-target="#gloss_pivot"> <b><i>pivot</i></b></a>.</p>
<p>To ensure that the list is not split into sub-lists of size 0 and n, the pivot must not be
the largest element in the list, so care must be taken if the fragment contains duplicate
elements. If all of the items in the fragment are equal we have to look at another fragment.</p>
<p>Having chosen a pivot we use two cursors, starting at each end of the list. The left cursor
is incremented until an item greater than the pivot is encountered and the right cursor is
decremented until an item less than or equal to the pivot is reached. Having found these two
items we swap them and advance the cursors. Having done this all items to the left of the left
cursor will be less than or equal to the pivot and all items to the right of the right cursor
will be greater than the pivot.</p>
<p>This process is repeated until the two cursors have advanced past each other. The meeting point
is the point at which the list should be split.</p>
</div>
<div class="col-md-6" id="rightText-component">
<p>Presented below is an outline of the code for quicksort using an array of items of
type<code>int</code>.
We need to supply two numeric arguments – the start and end locations of the array fragment
that is to be sorted</p>
<p>A calling method can be written to supply the values for these locations for the first call:</p>
</div>
<!-- START code column -->
<div class="col-md-6" id="code-component">
<pre><p>public static void quickSort(int[] l) {
if (l.length > 1) qSort(l, 0, l.length - 1);
}
</p></pre>
<pre><p>public static void qSort(int[] l, int start, int end) {
if (end > start) {
int pivot = <i>// select appropriate pivot</i>
int lo = start, hi = end;
do {
while (l[lo] <= pivot) lo++;
while (l[hi] > pivot) hi--;
if (lo < hi) {
int tmp = l[lo];
l[lo] = l[hi];
l[hi] = tmp;
lo++;
hi--;
}
} while (lo < hi);
qSort(l, start, hi);
qSort(l, lo, end);
}
}
</p></pre>
<p>It is not difficult to see that for an array fragment of size <i>n</i> the time for the do loop
is O(<i>n</i>).
In the worst case, where the pivot is the smallest or second-largest value in the fragment,
the list may be split into sub-lists of size <i>n</i>-1 and 1. The recursive call to the
sub-list of
size 1 will take constant time so we obtain a recurrence relation of the form T(<i>n</i>) ≤
T1+T(<i>n</i>-1)
where T1 is O(<i>n</i>). Hence in the worst case quicksort takes O(<i>n</i><sup>2</sup>) time.
<a href="#" data-toggle="modal" data-target="#gloss_however"> However...</a></p>
</div>
</div>
<nav class="section_nav" role="navigation">
<ul class="clearfix ">
<li class="pull-left "><a href="insertionSort.html" class="btn btn-primary"><span
class="glyphicon glyphicon-circle-arrow-left"></span> Previous </a></li>
<li class="pull-right"><a href="algorithmsInAction.html" class="btn btn-primary">Next <span
class="glyphicon glyphicon-circle-arrow-right"></span></a></li>
</ul>
</nav>
</article>
</main>
<!-- START doc top navigation -->
<div class="visible-xs-block" id="doc_top_btn"><a href="#doc_top" class="btn btn-info btn-block">Document Top
<span
class="glyphicon glyphicon-circle-arrow-up"></span></a></div>
<!-- END doc top navigation -->
<!-- Footer -->
<footer role="contentinfo">
<div class="progress">
<div class="progress-bar progress-bar-success" role="progressbar" aria-valuenow="77.7" aria-valuemin="0"
aria-valuemax="100" style="width: 77.7%">
<span class="sr">77% Complete</span>
</div>
</div>
<div class="row">
<div class="col-md-6">
<ul>
<li><b>Subject Matter:</b> Data Structure's & Algorithms</li>
<li><b>Sub-topic:</b> Sorting Algorithms</li>
<li><b>Content Author:</b> Dr Michael Sanderson</li>
<li><b>Developer:</b> Oliver Holland</li>
<li><b>Email:</b> <a href="mailto:[email protected]">[email protected]</a></li>
</ul>
</div>
<div class="col-md-6 text-right">
<p><b>Page last updated:</b> 19th March 2017</p>
</div>
</div>
</footer>
</div>
<!-- START Glossary Modals -->
<div class="modal fade" tabindex="-1" role="dialog" aria-labelledby="gloss_O(n)_label" id="gloss_o">
<div class="modal-dialog">
<div class="modal-content">
<div class="modal-header">
<h3 class="modal-title" id="gloss_O(n)_label">O(<i>n</i> log <i>n</i>)</h3>
</div>
<div class="modal-body">
<p>To obtain a hard-spilt easy-merge sorting method whose worstcase running time is O(<i>n</i> log
<i>n</i>)) we
would have to split the list into two equal-sized sub-lists, containing the smaller and larger
halves of the array, and perform this splitting in O(<i>n</i>) time. To do this we would have to
determine
the middle value of the sorted list. Since there is no way of doing this without sorting at least
half of the list, the splitting cannot be performed in O(<i>n</i>) time.</p>
</div>
<div class="modal-footer">
<button type="button" class="btn btn-danger" data-dismiss="modal">Close</button>
</div>
</div>
</div>
</div>
<div class="modal fade" tabindex="-1" role="dialog" aria-labelledby="gloss_pivot_label" id="gloss_pivot">
<div class="modal-dialog">
<div class="modal-content">
<div class="modal-header">
<h3 class="modal-title" id="gloss_pivot_label">Pivot</h3>
</div>
<div class="modal-body">
<p>For an optimum split the pivot should be the middle item of the sorted list, but since we cannot
determine this efficiently, Hoare suggested the selection of the middle-valued item from a small
fixed-size fragment of the list. </p>
</div>
<div class="modal-footer">
<button type="button" class="btn btn-danger" data-dismiss="modal">Close</button>
</div>
</div>
</div>
</div>
<div class="modal fade" tabindex="-1" role="dialog" aria-labelledby="gloss_however_label" id="gloss_however">
<div class="modal-dialog">
<div class="modal-content">
<div class="modal-header">
<h3 class="modal-title" id="gloss_however_label">However...</h3>
</div>
<div class="modal-body">
<p> For large random arrays we can expect the average sizes of the sub-lists to be about <i>n</i>/3 and
2<i>n</i>/3 and it can be shown by advanced analysis that the average performance is O(<i>n</i> log
<i>n</i>). Indeed,
for large lists, the average time for quicksort is better than for any other known generic sorting
algorithm.</p>
</div>
<div class="modal-footer">
<button type="button" class="btn btn-danger" data-dismiss="modal">Close</button>
</div>
</div>
</div>
</div>
<!-- Bootstrap core JavaScript
================================================== -->
<!-- Placed at the end of the document so the pages load faster -->
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.12.4/jquery.min.js"></script>
<script>window.jQuery || document.write('<script src="../../assets/js/vendor/jquery.min.js"><\/script>')</script>
<script src="js/bootstrap.min.js"></script>
<!-- JavaScript for Text Support Toolbar -->
<script src="js/textTools.js"></script>
</body>
</html>