📄 s_cm1.htm

📁 Data Structure Ebook
💻 HTM
字号:
<html>
<body bgcolor="#ffffff">

<p align=right>
<a href="s_man.htm" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_man.htm" target="_top"><img src="c_man.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/c_man.gif" width=74 height=19 border=0></a>
</p>

<h1>Comparison</h1>

In this section we will compare the sorting algorithms covered:
insertion sort, shell sort, and quicksort.  There are several
factors that influence the choice of a sorting algorithm:
<ul>
<li><i>Stable sort</i>.  Recall that a stable sort will leave identical
     keys  in  the  same relative position in the sorted  output.
     Insertion sort is the only algorithm covered that is stable.
<li><i>Space</i>.  An in-place sort does not require any extra space to
     accomplish its task.  Both insertion sort and shell sort are in-
     place sorts.  Quicksort requires stack space for recursion, and
     therefore is not an in-place sort. <i>Tinkering</i> with the algorithm
     considerably reduced the amount of time required.
<li><i>Time</i>.  The time required to sort a dataset 
can easily become astronomical (<a href="s_int.htm#Tbl1-1" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_int.htm#Tbl1-1">Table 1-1</a>).
Table 2-2 shows the relative timings for each method.
The time required to sort a randomly ordered dataset is shown in
Table 2-3.

<li><i>Simplicity</i>.  The number of statements required for each
algorithm may be found in
Table 2-2.
Simpler algorithms result in fewer programming errors.
 </ul>
<center>
<p><a name="Tbl2-2"></a>
<table border cellspacing=0 cellpadding=3>
<caption align=bottom><h3>Table 2-2:  Comparison of Sorting Methods</h3></caption>
<tr><th>method</th><th>statements</th><th>average time</th><th>worst-case time</th></tr>
<tr align=center> <td align=left>insertion sort</td> <td>9</td> <td><b><i>O</i></b>(<i>n</i><sup>2</sup>)</td> <td><b><i>O</i></b>(<i>n</i><sup>2</sup>)</td></tr>
<tr align=center> <td align=left>shell sort</td> <td>17</td> <td><b><i>O</i></b>(<i>n</i><sup>1.25</sup>)</td> <td><b><i>O</i></b>(<i>n</i><sup>1.5</sup>)</td></tr>
<tr align=center> <td align=left>quicksort</td> <td>21</td> <td><b><i>O</i></b>(<i>n</i> lg <i>n</i>)</td> <td><b><i>O</i></b>(<i>n</i><sup>2</sup>)</td></tr>
</table>
</center>

<center>
<p><a name="Tbl2-3"></a>
<table border cellspacing=0 cellpadding=3>
<caption align=bottom><h3>Table 2-3:  Sort Timings</h3></caption>
<tr><th>count</th><th>insertion</th><th>shell</th><th>quicksort</th></tr>
<tr align=right> <td>16</td> <td>39 &micro;s</td> <td>45 &micro;s</td> <td>51 &micro;s</td> </tr>
<tr align=right> <td>256</td> <td>4,969 &micro;s</td> <td>1,230 &micro;s</td> <td>911 &micro;s</td> </tr>
<tr align=right> <td>4,096</td> <td>1.315 sec</td> <td>.033 sec</td> <td>.020 sec</td> </tr>
<tr align=right> <td>65,536</td> <td>416.437 sec</td> <td>1.254 sec</td> <td>.461 sec</td> </tr>
</table>
</center>

</body>
</html>
⌨️ 快捷键说明

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