Talk:Smoothsort

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated C-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 
WikiProject Computing / Software / CompSci (Rated C-class, Low-importance)
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 Low  This article has been rated as Low-importance on the project's importance scale.
Taskforce icon
This article is supported by WikiProject Software (marked as Low-importance).
Taskforce icon
This article is supported by WikiProject Computer science (marked as Mid-importance).
 

Wikiproject[edit]

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[edit]

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 (talkcontribs) 14:17, 25 October 2012 (UTC)

Pseudocode[edit]

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)