📄 w2_1998.html

📁 Data Structure Ebook
💻 HTML
字号:
<html><head>
<title>Data Structures and Algorithms - Workshop 2</title>
</head>
<BODY BGCOLOR="#fffff">
<H1>Data Structures and Algorithms</H1>
<HR>
<H2>Workshop 2 - 1998</H2>
<H3>Sorting</H3>
The basic aims of this workshop are to
<UL>
<LI>compare various sorting routines.
</UL>

You will need to write a simple program to 
generate lists of data to be sorted and
then to time various sorting algorithms for
a sufficient range of sizes of the data list to
verify that the expected time complexity
is observed.
<P>
You should augment your Collection class so that
you can add two sorting methods:
<UL><LI>HeapSort <I>and</I>
<LI>QuickSort
</UL>
So that you can verify that your sort algorithms are
operating correctly,
add another method:
<UL><LI><PRE>int Sorted( Collection c );</PRE>
</UL>
which verifies that the data is, in fact, sorted
after the sort algorithm has been applied.
<P>
In order to make this code as general-purpose and useful
as possible,
you should ensure that the Collection constructor has
an additional argument,
the comparison function.
<I>This will be discussed in the lecture on Aug 10,
so you can either defer worrying about it while you design
the rest of the system (it involves a straightforward
addition to the design) or test your tutor's memory of
the definitely non-intuitive syntax required -
alternatively read your C text or the <A HREF="C_functions.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/C_functions.html">
lecture notes</A>.</I>
<P>
In order to understand the difference in the results 
that you obtain,
you should <I>instrument</I> your algorithms to count the
number of comparisons and the number of exchanges made.
Note that although you can use the machine's library quicksort
routine, <A HREF="qsort_man.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/qsort_man.html">qsort,</A> initially, 
you will need to implement a version of your own by
downloading the code from the notes in
order to instrument the algorithm.
<P>
<I>Think carefully</I> about how you will add the 
instrumentation code and how you will obtain the statistics
when the sort has completed. 
This should disturb the "normal" code as little as possible,
so that the instrumented code runs in ordinary programs
with no changes and still sorts correctly.
<P>
As a final part of this assignment,
you should test the 
<B>library</B> quicksort algorithm to see if you can infer
what type of pivot selection is used.
(<I>You can limit this to "naive" or otherwise -
but anyone who can devise a technique which reliably
detects what strategy is used under the "otherwise"
heading is assured of 100% for this assignment
(as long as no <B>major</B> design crimes are committed!</I>).)
Check the qsort
library routine on another type of machine as a demonstration
that your code is ANSI standard compliant and portable.
If it is, then this shouldn't take more than 10 minutes:
log into another machine (you can use any other one you like),
recompile, re-run and you should have an answer!
(Although using one of the fancy GUI compilers on a Windows machine
will take more than 10 minutes to set the project up!)

<P>

<H3>Report</H3>

Prepare a brief report which summarises your results.
It should contain <I>as a minimum</I>,
<UL>
<LI>your raw experimental results
<LI>the statistics obtained by instrumenting the sorting routines
<LI>your inferences from this data <I>and</I>
<LI>your inference as to quality of the library quicksort routine.
</UL>
(The report should be plain ASCII text - <FONT COLOR=red>
<B>not</B></FONT> the native form of
any word processor.)
<P>
This report should start by forming a hypothesis about your 
expected results.
This should be followed by the actual results.
The conclusion should provide a convincing argument as to why these
results confirm your original hypotheses. 
It should also highlight and attempt to explain any discrepancies.
<P>
If you design your program efficiently, you will be able to get
it to generate a table of data for you which you can paste
directly into the report.
<P>
<A HREF="new_submit.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/Labs/new_submit.html">Submission Instructions will be available soon!</A>
</body>
</html>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -