希尔排序时间复杂度证明

落日映苍穹つ 2022-08-21 07:56 149阅读 0赞

<table> 
 <tbody> 
  <tr> 
   <td style="font-size:13.44px"> <h2 style="font-size:24.192px; font-weight:normal; font-style:italic; margin-top:5px; margin-bottom:5px"> <a href="http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm" rel="nofollow">Shellsort</a></h2> </td> 
   <td align="right" style="font-size:13.44px">&nbsp;<a href="http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shell.htm" rel="nofollow"><img src="http://www.iti.fh-flensburg.de/lang/symbols/de.gif" width="19" height="19" alt="German version" title="German version" style="border:none"></a>&nbsp;&nbsp;<a href="http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/algoen.htm" rel="nofollow"><img src="http://www.iti.fh-flensburg.de/lang/symbols/up.gif" width="19" height="19" alt="up" title="up" style="border:none"></a></td> 
  </tr> 
 </tbody> 
</table>

Shellsort is one of the oldest sorting algorithms, named after its inventor D.L. Shell (1959) \[She 59\]. It is fast, easy to understand and easy to implement. However, its [complexity][] analysis is a little more sophisticated.

### Idea ###

The idea of Shellsort is the following:

1.  arrange the data sequence in a two-dimensional array
2.  sort the columns of the array

The effect is that the data sequence is partially sorted. The process above is repeated, but each time with a narrower array, i.e. with a smaller number of columns. In the last step, the array consists of only one column. In each step, the sortedness of the sequence is increased, until in the last step it is completely sorted. However, the number of sorting operations necessary in each step is limited, due to the presortedness of the sequence obtained in the preceding steps.

**Example:**  Let  3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2  be the data sequence to be sorted. First, it is arranged in an array with 7 columns (left), then the columns are sorted (right):

Data elements 8 and 9 have now already come to the end of the sequence, but a small element (2) is also still there. In the next step, the sequence is arranged in 3 columns, which are again sorted:

Now the sequence is almost completely sorted. When arranging it in one column in the last step, it is only a 6, an 8 and a 9 that have to move a little bit to their correct position.

### Implementation ###

Actually, the data sequence is not arranged in a two-dimensional array, but held in a one-dimensional array that is indexed appropriately. For instance, data elements at positions 0, 5, 10, 15 etc. would form the first column of an array with 5 columns. The "columns" obtained by indexing in this way are sorted with insertion sort, since this method has a good performance with presorted sequences.

The following program sorts an array a from index position 0 through n\-1. The number of columns used for arranging data in each step is in array cols. Thus, data are arranged in 1391376 columns in the first step and in one column in the last step. (Note that essentially nothing is done if the number of columns h is larger than the number of data elements n.) Each column is sorted by[insertion sort][]. First, data of the second row (beginning at i = h) are sorted to the correct position in their column, then data of the third row (when i reaches value 2h) etc.

Algorithm *Shellsort*

<table> 
 <tbody> 
  <tr> 
   <td style="font-size:13.44px; padding:3px 5px 3px 15px; background-color:rgb(238,238,238)"> <pre><code><span style="font-weight:bold; color:blue">void</span> shellsort (<span style="font-weight:bold; color:blue">int</span>[] a, <span style="font-weight:bold; color:blue">int</span> n)
{
    <span style="font-weight:bold; color:blue">int</span> i, j, k, h, v;
    <span style="font-weight:bold; color:blue">int</span>[] cols = {1391376, 463792, 198768, 86961, 33936, 13776, 4592,
                    1968, 861, 336, 112, 48, 21, 7, 3, 1}
    <span style="font-weight:bold; color:blue">for</span> (k=0; k&lt;16; k++)
    {
        h=cols[k];
        <span style="font-weight:bold; color:blue">for</span> (i=h; i&lt;n; i++)
        {
            v=a[i];
            j=i;
            <span style="font-weight:bold; color:blue">while</span> (j&gt;=h &amp;&amp; a[j-h]&gt;v)
            {
                a[j]=a[j-h];
                j=j-h;
            }
            a[j]=v;
        }
    }
}
</code></pre> </td> 
  </tr> 
 </tbody> 
</table>

### Analysis ###

The correctness of the algorithm follows from the fact that in the last step (with h = 1) an ordinary insertion sort is performed on the whole array. But since data are presorted by the preceding steps (h = 3, 7, 21, ...) only few insertion sort steps are sufficient. How many exactly will be the subject of the following analysis. The above sequence of h's (denoted as h\-sequence in the following) is just one of several possible; actually, the performance of Shellsort depends on which h\-sequence is used.

##### Basics #####

The postage for a letter is 16F, for a postcard it is 11F. But there are only stamps of 3F and 7F available. Is it possible to stamp the letter and the postcard exactly?

Obviously, the problem is to represent the numbers 16 and 11 as linear combinations k·3 + l·7 with nonnegative integer coefficientsk and l. Which natural numbers can be combined from multiples of 3 and 7 and which cannot?

**Definition:**  Let g, h ![element][] ![natural numbers][]. We call a number f a combination of g and h, if f can be represented as a linear combination f = kg + lhwith coefficients k, l ![element][] ![natural numbers][]0.

The letter can be stamped exactly, since 16 is a combination of 3 and 7, namely 16 = 3·3 + 1·7.

**Definition:**  Let g, h ![element][] ![natural numbers][] be relatively prime. With N(g, h) we denote the (finite) set of all natural numbers that are not combinations of g and h and with γ(g, h) the largest of these numbers:

N(g, h)  =  \{ f ![element][] ![natural numbers][]  | ¬ ![there exists][] k, l ![element][] ![natural numbers][]0 :  f = kg + lh \}

γ(g, h)  =  max;(N(g, h))

**Example:**  Let g = 3, h = 7. Then

N(g, h)  =  \{1, 2, 4, 5, 8, 11\},   and   γ(g, h)  =  11

The postcard cannot be stamped exactly, since 11 is not a combination of 3 and 7.

**Proposition:**  Let g, h ![element][] ![natural numbers][] be relatively prime. Then

γ(g, h)  =  (g\-1)·(h\-1) – 1

i.e. every number f with f![greater or equal][](g\-1)·(h\-1) is a combination of g and h.

**Proof:**  (Exercise)

##### h\-sortedness #####

**Definition:**  Let h ![element][] ![natural numbers][]0. A sequence a1, ..., an is called h\-sorted, if for all i ![element][] \{1, ..., n\-h\} it holds that

ai![less or equal][]ai\+h

A h\-sorted sequence is obtained by arranging the sequence in an array with h columns and then sorting the columns. A 1-sorted sequence is sorted.

**Proposition:**  Let g, h ![element][] ![natural numbers][]. A g\-sorted sequence remains g\-sorted after h\-sorting it.

**Proof:**  see \[Knu 73\]

**Definition:**  A sequence that is g\-sorted and h\-sorted is called g,h\-sorted.

**Proposition:**  A g,h\-sorted sequence is g\+h\-sorted.

**Proof:**  We have to show that for all i ![element][] \{1, ..., n\-(g\+h)\} it holds that

ai![less or equal][]ai\+g\+h

But this is the case because ai![less or equal][]ai\+g, since the sequence is g\-sorted, and ai\+g![less or equal][]ai\+g\+h, since the sequence is h\-sorted.

As an immediate consequence, we have the following

**Proposition:**  If a sequence is g,h\-sorted, then it is kg\+lh\-sorted for all k, l ![element][] ![natural numbers][]0, i.e. the sequence is f\-sorted for each f that is a combination of g and h.

**Proposition:**  Let a be a g,h\-sorted sequence, where g and h are relatively prime. Then for all elements ai and aj the following holds:

j – i ![greater or equal][] (g\-1)·(h\-1) ![implies][] ai![less or equal][]aj

i.e. to the right of each ai only the next (g\-1)·(h\-1) – 1 elements can be smaller.

**Proof:**  Let  j – i  =  f ![greater or equal][] (g\-1)·(h\-1), then f is a combination of g and h. Therefore the sequence is f\-sorted, which means that

ai![less or equal][]ai\+f  =  aj

**Proposition:**  Let a be a g,h\-sorted sequence, where g and h are relatively prime, and let d be a variable. If both g and h are inO(d), then O(n·d) sorting steps are sufficient for d\-sorting the sequence.

**Proof:**  To the right of each element ai at most (g\-1)·(h\-1) – 1 elements are smaller. d\-sorting the sequence means arranging it as a two-dimensional array with d columns and sorting the columns.

In the column under ai only every d\-th of these smaller elements can occur. This means that ai has to be exchanged with at most ((g\-1)·(h\-1) – 1) / d elements or, since g and h are in O(d), with O(d) elements.

Since this holds for all ai (i = 1, ..., n), there are O(n·d) sorting steps needed for d\-sorting the sequence.

From this proposition upper bounds for the complexity of Shellsort can be derived.

##### Upper bounds #####

**Theorem:**  With the h\-sequence 1, 3, 7, 15, 31, 63, 127, ..., 2k – 1, ... Shellsort needs O(n·![square root][]n) steps for sorting a sequence of length n  (Papernov/Stasevic \[PS 65\]).

**Proof:**  Let ht be the h closest to ![square root][]n. We analyze the behavior of Shellsort separately for the elements hk with k![less or equal][]t and with k > t.

Let k![less or equal][]t. Since hk = 2k – 1 we have the conditions mentioned above that hk\+1 and hk\+2 are relatively prime and in O(hk). Therefore, O(n·hk) sorting steps suffice for hk\-sorting the data sequence. Since the hk form a geometric series, the sum of allhk with k = 1, ..., t is in O(ht) = O(![square root][]n). Thus O(n·![square root][]n) sorting steps are needed for this part where k![less or equal][]t.

Now let k > t. When the sequence is arranged as an array with hk columns there are n/hk elements in each column. Thus,O((n/hk)2) sorting steps are needed to sort each column, since insertion sort has quadratic complexity. There are hk columns, therefore the number of sorting steps for hk\-sorting the entire data sequence is in O((n/hk)2·hk) = O(n·n/hk). Again, the n/hkform a geometric series whose sum is in O(n/ht) = O(![square root][]n). Therefore, again O(n·![square root][]n) steps are needed for this part wherek > t.

It can be shown that for this h\-sequence the upper bound is tight. But there is another h\-sequence that leads to a more efficient behavior of Shellsort.

**Theorem:**  With the h\-sequence 1, 2, 3, 4, 6, 8, 9, 12, 16, ..., 2p3q, ... Shellsort needs O(n·log(n)2) steps for sorting a sequence of length n  (Pratt \[Pra 79\]).

**Proof:**  If g = 2 and h = 3, then γ(g, h)  =  (g\-1)·(h\-1) – 1  =  1, i.e. in a 2,3-sorted sequence to the right of each element only the next element can be smaller. Therefore, O(n) sorting steps suffice to sort the sequence with insertion sort. Considering elements with odd and with even index separately, it becomes clear that again O(n) sorting steps suffice to make a 4,6-sorted sequence 2-sorted. Similarly, O(n) sorting steps suffice to make a 6,9-sorted sequence 3-sorted and so on.

The above h\-sequence has the property that for each hk also 2hk and 3hk occurs, so O(n) sorting steps suffice for each hk. Altogether there are log(n)2 elements in the h\-sequence; thus the complexity of Shellsort with this h\-sequence is inO(n·log(n)2).

The h\-sequence of Pratt performs best asymptotically, but it consists of log(n)2 elements. Particularly, if the data sequence is presorted, a h\-sequence with less elements is better, since the data sequence has to be scanned (by the for-i-loop in the program) for each hk, even if only a few sorting steps are performed.

By combining the arguments of these two theorems h\-sequences with O(log(n)) elements can be derived that lead to a very good performance in practice, as for instance the h\-sequence of the program (Sedgewick \[Sed 96\]). But unfortunately, there seems to be no h\-sequence that gives Shellsort a worst case performance of O(n·log(n)) (see \[Sed 96\]). It is an open question whether possibly the average complexity is in O(n·log(n)).

### Sorting network ###

Shellsort can be implemented as a [sorting network][] if the data-dependent insertion sort is replaced with [bubble sort][]. With the h\-sequence 2p3q the sorting network consists of O(n·log(n)2) comparators. This is the same number of comparators as in [bitonic sort][].

The following figure shows the corresponding sorting network for n = 8.

<table> 
 <tbody> 
  <tr> 
   <td align="center" style="font-size:13.44px"> 
    <table> 
     <tbody> 
      <tr> 
       <td align="center" style="font-size:13.44px"><img src="http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellsrt.gif" alt="Figure 1: Shellsort network for n=8" style="border:none"></td> 
      </tr> 
     </tbody> 
    </table> </td> 
  </tr> 
  <tr> 
   <td style="font-size:11.36px; text-align:center; padding-top:10px; padding-bottom:10px"> Figure 1: Shellsort network for n=8</td> 
  </tr> 
  <tr> 
   <td style="font-size:13.44px">&nbsp;</td> 
  </tr> 
 </tbody> 
</table>

### Simulation ###

(Java applet for simulation of shellsort)

### References ###

Shellsort was originally published by D.L. Shell \[She 59\].

<table> 
 <tbody> 
  <tr> 
   <td style="font-size:13.44px; width:100px; padding-left:5px; padding-top:0.5ex; padding-bottom:0.5ex; vertical-align:top"> &nbsp;</td> 
   <td style="font-size:13.44px">&nbsp;</td> 
   <td style="font-size:13.44px">&nbsp;</td> 
  </tr> 
  <tr> 
   <td style="font-size:13.44px; width:100px; padding-left:5px; padding-top:0.5ex; padding-bottom:0.5ex; vertical-align:top"> [Knu&nbsp;73]</td> 
   <td colspan="2" style="font-size:13.44px; padding-left:5px; padding-top:0.5ex; padding-bottom:0.5ex"> <span style="font-variant:small-caps">D.E. Knuth</span>: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)</td> 
  </tr> 
  <tr> 
   <td style="font-size:13.44px; width:100px; padding-left:5px; padding-top:0.5ex; padding-bottom:0.5ex; vertical-align:top"> [Pra&nbsp;79]</td> 
   <td colspan="2" style="font-size:13.44px; padding-left:5px; padding-top:0.5ex; padding-bottom:0.5ex"> <span style="font-variant:small-caps">V. Pratt</span>: Shellsort and Sorting Networks. Garland, New York (1979)</td> 
  </tr> 
  <tr> 
   <td style="font-size:13.44px; width:100px; padding-left:5px; padding-top:0.5ex; padding-bottom:0.5ex; vertical-align:top"> [PS&nbsp;65]</td> 
   <td colspan="2" style="font-size:13.44px; padding-left:5px; padding-top:0.5ex; padding-bottom:0.5ex"> <span style="font-variant:small-caps">A. Papernov, G. Stasevic</span>: A Method of Information Sorting in Computer Memories. Problems of Information Transmission 1, 63-75 (1965)</td> 
  </tr> 
  <tr> 
   <td style="font-size:13.44px; width:100px; padding-left:5px; padding-top:0.5ex; padding-bottom:0.5ex; vertical-align:top"> [Sed&nbsp;88]</td> 
   <td colspan="2" style="font-size:13.44px; padding-left:5px; padding-top:0.5ex; padding-bottom:0.5ex"> <span style="font-variant:small-caps">R. Sedgewick</span>: Algorithms. 2nd edition, Addison-Wesley (1988)</td> 
  </tr> 
  <tr> 
   <td style="font-size:13.44px; width:100px; padding-left:5px; padding-top:0.5ex; padding-bottom:0.5ex; vertical-align:top"> [Sed&nbsp;96]</td> 
   <td colspan="2" style="font-size:13.44px; padding-left:5px; padding-top:0.5ex; padding-bottom:0.5ex"> <span style="font-variant:small-caps">R. Sedgewick</span>: Analysis of Shellsort and Related Algorithms. In: Josep Díaz, Maria Serna (Eds.): Algorithms - ESA '96, Fourth Annual European Symposium, Barcelona, Lecture Notes in Computer Science, Vol. 1136, Springer, 1-11 (1996)</td> 
  </tr> 
  <tr> 
   <td style="font-size:13.44px; width:100px; padding-left:5px; padding-top:0.5ex; padding-bottom:0.5ex; vertical-align:top"> [She&nbsp;59]</td> 
   <td colspan="2" style="font-size:13.44px; padding-left:5px; padding-top:0.5ex; padding-bottom:0.5ex"> <p><span style="font-variant:small-caps">D.L. Shell</span>: A High-Speed Sorting Procedure. Communications of the ACM, 2, 7, 30-32 (1959<span style="font-size:13.44px">)</span></p> </td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td style="font-size:13.44px"> <a href="http://www.iti.fh-flensburg.de/lang/indexen.htm" title="home" style="text-decoration:none" rel="nofollow"><img src="http://www.iti.fh-flensburg.de/lang/home.gif" height="10" width="25" alt="home" style="border:none">H.W. Lang</a>&nbsp;&nbsp;&nbsp;<a href="http://www.fh-flensburg.de/" title="Fachhochschule Flensburg - University of Applied Sciences" style="text-decoration:none" rel="nofollow">Fachhochschule Flensburg</a>&nbsp;&nbsp;&nbsp;<a href="mailto:lang@fh-flensburg.de" title="send comments" style="text-decoration:none" rel="nofollow">lang@fh-flensburg.de</a>&nbsp;&nbsp;&nbsp;<a href="http://www.iti.fh-flensburg.de/lang/impressum.htm" style="text-decoration:none" rel="nofollow">Impressum</a>&nbsp;&nbsp; © &nbsp; Created: 29.01.1998 &nbsp; Updated: 15.02.2016 <br>  <br>  <br>  如果我有时间，就翻译一下吧 </td> 
  </tr> 
 </tbody> 
</table>

[complexity]: http://www.iti.fh-flensburg.de/lang/algorithmen/asympen.htm
[insertion sort]: http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/insert/insertionen.htm
[element]: http://www.iti.fh-flensburg.de/lang/symbols/elem.gif
[natural numbers]: http://www.iti.fh-flensburg.de/lang/symbols/zn.gif
[there exists]: http://www.iti.fh-flensburg.de/lang/symbols/ex.gif
[greater or equal]: http://www.iti.fh-flensburg.de/lang/symbols/ge.gif
[less or equal]: http://www.iti.fh-flensburg.de/lang/symbols/le.gif
[implies]: http://www.iti.fh-flensburg.de/lang/symbols/imp.gif
[square root]: http://www.iti.fh-flensburg.de/lang/symbols/sqrt.gif
[sorting network]: http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/sortieren.htm
[bubble sort]: http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/sortieren.htm#section3
[bitonic sort]: http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm