OpenEuphoria

Challenge for Sort programs.

• Posted by rforno at tutopia.com Jun 03, 2002
• 449 views

Hi all:
I was attempting to improve the performance of the Shell sort that comes
with Euphoria. One of the ways is substituting the divisor 3 by some other,
especially for non-integers in the range 2.5 - 3.5. 2.6, 2.7 and 3.4 have
proven to be good.. Some other tactics have been tried, with no great
success.
As you know, Shell sort is based on Insertion sort, one of the simple ones,
with times O(n ^ 2), instead of O(n log(n)) as the efficient ones.
Then I started seeking to improve the simple sorts or develop new simple
sorting methods, with the aim to apply then to Shell sort replacing
Insertion sort in it. My attempts failed with modified versions of Insertion
sort, but I succeed in programming double_sel_sort (a modification of normal
Selection sort working from both ends) and new_sort, a novel approach (also
a modification of Selection sort) which takes advantage of the
previous-to-best key to reduce the search range. These sorts are marginally
faster than Insertion sort if the number of items is not too low.
But they should not be used to replace Insertion sort inside Shell sort,
because they are slower than it when the sequence is nearly sorted. Shell
sort takes advantage of this fact especially in its last pass, identical to
Insertion sort, precisely because the sequence is then nearly sorted.
So, I tried Bubble sort, that is the fastest one for nearly sorted
sequences, and the generated a new_shell_sort based on Bubble sort. It is
not faster, but rather slower than the original Shell sort.
Well, after this rant, you will find the code for all these sorts, plus two
slightly improved versions of Bubble sort, and Selection sort, one of the
basic ones (Rob: why is it not included in Allsorts.ex?).
The challenge to find faster sorts remain open. I hope to have contributed
some ideas on this subject.

-------------------------------------------------------

function new_shell_sort(sequence x)
-- Shell sort based on bubble sort
    integer gap, last, limit, flip
    object temp
    last = length(x)
    gap = floor(last / 3) + 1
    while 1 do
        for j = 1 to gap do
            flip = last
            while flip do
                limit = flip
                flip = 0
                for i = j to limit - gap by gap do
                    temp = x[i + gap]
                    if compare(temp, x[i]) < 0 then
                        x[i + gap] = x[i]
                        x[i] = temp
                        flip = i
                    end if
                end for
            end while
        end for
        if gap = 1 then
            return x
        else
            gap = floor(gap / 3) + 1
        end if
    end while
end function

function new_sort(sequence x)
    integer len
    object min, temp
    integer first, second
    len = length(x)
    if len <= 1 then
        return x
    end if
    first = 1
    second = 1
    min = x[1]
    for i = 1 to len - 1 do
        for j = first + 1 to len do
            if compare(x[j], min) < 0 then
                second = first
                first = j
                min = x[j]
            end if
        end for
        if first = second then
            x[first] = x[i]
            x[i] = min
            first = i + 1
            second = first
            min = x[first]
        else
            temp = x[second]
            x[first] = x[i]
            x[i] = min
            min = temp
            if second = i then
                second = first
            else
                first = second
            end if
        end if
    end for
    return x
end function

function new_bubble_sort2(sequence x)
    object temp, temp1
    integer flip, limit, j
    flip = length(x)
    while flip do
        limit = flip
        flip = 0
        for i = 1 to limit - 1 do
            j = i + 1
            temp = x[j]
            temp1 = x[i]
            if compare(temp, temp1) < 0 then
                x[j] = temp1
                x[i] = temp
                flip = i
            end if
        end for
    end while
    return x
end function

function new_bubble_sort(sequence x)
    object temp
    integer flip, limit, j
    flip = length(x)
    while flip do
        limit = flip
        flip = 0
        for i = 1 to limit - 1 do
            j = i + 1
            temp = x[j]
            if compare(temp, x[i]) < 0 then
                x[j] = x[i]
                x[i] = temp
                flip = i
            end if
        end for
    end while
    return x
end function

function double_sel_sort(sequence x)
    object min, max
    integer p, q, i, len
    len = length(x)
    i = 1
    while len > i do
        p = i
        min = x[p]
        q = i
        max = min
        for j = i + 1 to len do
            if compare(x[j], min) < 0 then
                p = j
                min = x[p]
            elsif compare(x[j], max) > 0 then
                q = j
                max = x[q]
            end if
        end for
        x[p] = x[i]
        x[i] = min
        if q = i then
            x[p] = x[len]
        else
            x[q] = x[len]
        end if
        x[len] = max
        i += 1
        len -= 1
    end while
    return x
end function

function selection_sort(sequence x)
    object temp
    integer k, len
    len = length(x)
    for i = 1 to len - 1 do
        k = i
        temp = x[k]
        for j = i + 1 to len do
            if compare(x[j], temp) < 0 then
                k = j
                temp = x[k]
            end if
        end for
        x[k] = x[i]
        x[i] = temp
    end for
    return x
end function