Talk:Smoothsort

Wikiproject

I don't think this article belongs in the java wiki project - it's not about java, it just happens to have a java example. I'll drop it into comp sci instead. Paul Murray (talk) 01:12, 23 November 2009 (UTC)

7049156 - longest reversed/random list that is properly calculated by java implementation, and i have no idea why... —Preceding unsigned comment added by 83.27.127.57 (talk) 14:56, 5 September 2010 (UTC)

The problem is overflow in p. A n-bit p will work for arrays up to size proportional to L(n), where L(n) is the nth Leonardo number. Change both the declaration of the p variable in the sort() function, and the p parameter to the trinkle() function to use a 64-bit type (in C++, I use long long p), and there shouldn't be a problem until the array size reaches L(64) (which should be plenty big enough). James Barbetti (talk) 08:14, 24 November 2010 (UTC)

Gif visualization problem

Is it just me, or the frame 10 of the visualization (gif in the top right) depicts an incorrect behavior, because according to the description:

Smoothsort#Grow_the_string_by_adding_an_element_to_the_right

  1) The rightmost heap (the one that has just been created) becomes the "current" heap

so the heap of length 3 is now current

  2) While there is a heap to the left of the current heap and its root is larger than the current root and both of its child heap roots 

there is such heap, the heap of length 5, to the left of current one.

But, the visualization shows that the 3rd step of the algorithm is executed... The step two is omitted until very late into building the heaps. I wonder how step 2. and 3. are related actually, and how does it impact the time complexity of the algorithm.

Is there anyone around, who can say anything about it?

Thanks :) — Preceding unsigned comment added by Unk3mpt (talk • contribs) 14:17, 25 October 2012 (UTC)

Pseudocode

Here's some pseudocode for smoothsort using binary heaps, paraphrased from Hertel, that we may want to incorporate into the article later. Indices are 1-based.

algorithm smoothsort(A) is
    n := length(A)
    root := new array of ⌈log(n+1)⌉ integers

    // forward phase
    i := 0
    while i < n do
        k := ⌊log(n−i+1)⌋
        make-heap(i+1, i+2k−1)
        i := i+2k−1
        r := r+1
        root[r] := i
        restructure(A, root, r)

    // backward phase
    while i > 1 do
        size := root[r] − root[r−1]
        if size = 1 then
            r := r−1
        else
            // size > 1; split heap
            root[r+1] = root[r]−1
            root[r] := root[r+1] − (size−1)/2
            r := r+1
            restructure(A, root, r−1)
            restructure(A, root, r)
        i := i−1

// r is passed by value.
algorithm restructure(A, root, r) is
    while r > 1 and A[root[r−1]] > maxchildren(A, root[r]) do
        swap A[root[r−1]] and A[root[r]]
        r := r−1
    if r = 1 then
        heapify(root[r], 1)
    else
        heapify(root[r], root[r−1]+1)

maxchildren(A, i) returns the max of A[i] and its two children, if they exist. QVVERTYVS (hm?) 20:53, 29 November 2015 (UTC)