|
Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort).〔 The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbor exchange. Donald Shell published the first version of this sort in 1959.〔Some older textbooks and references call this the "Shell-Metzner" sort after Marlene Metzner Norton, but according to Metzner, "I had nothing to do with the sort, and my name should never have been attached to it." See 〕 The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem. == Description == Shellsort is a generalization of insertion sort that allows the exchange of items that are far apart. The idea is to arrange the list of elements so that, starting anywhere, considering every ''h''th element gives a sorted list. Such a list is said to be ''h''-sorted. Equivalently, it can be thought of as ''h'' interleaved lists, each individually sorted. Beginning with large values of ''h'', this rearrangement allows elements to move long distances in the original list, reducing large amounts of disorder quickly, and leaving less work for smaller ''h''-sort steps to do. If the file is then ''k-sorted'' for some smaller integer ''k'', then the file remains ''h''-sorted. Following this idea for a decreasing sequence of ''h'' values ending in 1 is guaranteed to leave a sorted list in the end.〔 An example run of Shellsort with gaps 5, 3 and 1 is shown below. The first pass, 5-sorting, performs insertion sort on separate subarrays (''a''1, ''a''6, ''a''11), (''a''2, ''a''7, ''a''12), (''a''3, ''a''8), (''a''4, ''a''9), (''a''5, ''a''10). For instance, it changes the subarray (''a''1, ''a''6, ''a''11) from (62, 17, 25) to (17, 25, 62). The next pass, 3-sorting, performs insertion sort on the subarrays (''a''1, ''a''4, ''a''7, ''a''10), (''a''2, ''a''5, ''a''8, ''a''11), (''a''3, ''a''6, ''a''9, ''a''12). The last pass, 1-sorting, is an ordinary insertion sort of the entire array (''a''1,..., ''a''12). As the example illustrates, the subarrays that Shellsort operates on are initially short; later they are longer but almost ordered. In both cases insertion sort works efficiently. Shellsort is unstable: it may change the relative order of elements with equal values. It is an adaptive sorting algorithm in that it executes faster when the input is partially sorted. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「shellsort」の詳細全文を読む スポンサード リンク
|