|
Smoothsort is a comparison-based sorting algorithm. It is a variation of heapsort developed by Edsger Dijkstra in 1981. Like heapsort, smoothsort is an in-place algorithm with an upper bound of O(''n'' log ''n''), but it is not a stable sort.〔http://www.codeproject.com/Articles/26048/Fastest-In-Place-Stable-Sort〕 The advantage of smoothsort is that it comes closer to O(''n'') time if the input is already sorted to some degree, whereas heapsort averages O(''n'' log ''n'') regardless of the initial sorted state. ==Overview== Like heapsort, smoothsort builds up an implicit heap data structure in the array to be sorted, then sorts the array by continuously extracting the maximum element from that heap. Unlike heapsort, Dijkstra's original formulation of smoothsort does not use a binary heap, but rather a custom heap based on the Leonardo numbers; it was later shown that the algorithm can be reformulated in terms of a binary heap without loss of asymptotic efficiency. The heap structure consists of a string of heaps, the sizes of which are all Leonardo numbers, and whose roots are stored in ascending order. The advantage of this custom heap over binary heaps is that if the sequence is already sorted, it takes only time to construct and deconstruct the heap, hence the better runtime. Breaking the input up into a sequence of heaps is simple – the leftmost nodes of the array are made into the largest heap possible, and the remainder is likewise divided up. It can be proven 〔(Smoothsort Demystified ). Keithschwarz.com. Retrieved on 2010-11-20.〕 that: * Any array of any length can so be divided up into sections of size L(x). * No two heaps will have the same size. The string will therefore be a string of heaps strictly descending in size. * No two heaps will have sizes that are consecutive Leonardo numbers, except for possibly the final two. Each heap, having a size of L(x), is structured from left to right as a sub-heap of size , a sub-heap of size , and a root node, with the exception of heaps with a size of L(1) and L(0), which are singleton nodes. Each heap maintains the heap property that a root node is always at least as large as the root nodes of its child heaps (and therefore at least as large as all nodes in its child heaps), and the string of heaps as a whole maintains the string property that the root node of each heap is at least as large as the root node of the heap to the left. The consequence of this is that the rightmost node in the string will always be the largest of the nodes, and, importantly, an array that is already sorted needs no rearrangement to be made into a valid series of heaps. This is the source of the adaptive qualities of the algorithm. The algorithm is simple. We start by dividing up our unsorted array into a single heap of one element, followed by an unsorted portion. A one-element array is trivially a valid sequence of heaps. This sequence is then grown by adding one element at a time to the right, performing swaps to keep the sequence property and the heap property, until it fills the entire original array. From this point on, the rightmost element of the sequence of heaps will be the largest element in any of the heaps, and will therefore be in its correct, final position. We then reduce the series of heaps back down to a single heap of one element by removing the rightmost node (which stays in place) and performing re-arrangements to restore the heap condition. When we are back down to a single heap of one element, the array is sorted. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Smoothsort」の詳細全文を読む スポンサード リンク
|