Power-Programmierung/CD1.mdf/euphoria/allsorts.ex

Text File | 1994-02-15 | 8KB | 373 lines

        ----------------------------------------
        -- Sorting Algorithms in Euphoria     --
        -- These routines will sort sequences --
        -- of general Euphoria objects          --
        ----------------------------------------
without type_check

constant MAX = 4800
constant TRUE = 1, FALSE = 0
constant CHECK_RESULTS = FALSE

integer hybrid_limit

type natural(integer x)
    return x >= 0
end type

type file_number(integer x)
    return x >= -1
end type

function simple_sort(sequence x)
-- put x into ascending order
-- using a very simple sort
object temp

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


function bubble_sort(sequence x)
-- put x into ascending order
-- using bubble sort
object temp
natural flip, limit

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

function insertion_sort(sequence x)
-- put x into ascending order
-- using insertion sort
object temp
natural final

    for i = 2 to length(x) do
    temp = x[i]
    final = 1
    for j = i-1 to 1 by -1 do
        if compare(temp, x[j]) < 0 then
        x[j+1] = x[j]
        else
        final = j + 1
        exit
        end if
    end for
    x[final] = temp
    end for
    return x
end function

function shell_sort(sequence x)
-- Shell sort based on insertion sort

    integer gap, j, first, last
    object tempi, tempj

    last = length(x)
    gap = floor(last / 3) + 1
    while TRUE do
    first = gap + 1
    for i = first to last do
        tempi = x[i]
        j = i - gap
        while TRUE do
        tempj = x[j]
        if compare(tempi, tempj) >= 0 then
            j = j + gap
            exit
        end if
        x[j+gap] = tempj
        if j <= gap then
            exit
        end if
        j = j - gap
        end while
        x[j] = tempi
    end for
    if gap = 1 then
        return x
    else
        gap = floor(gap / 3) + 1
    end if
    end while
end function


global function quick_sort(sequence x)
-- put x into ascending order
-- using recursive quick sort
    natural n, last, midval, temp

    n = length(x)
    if n < 2 then
    return x -- already sorted (trivial case)
    end if

    midval = x[(n + 1) / 2]
    x[(n + 1) / 2] = x[1]

    last = 1
    for i = 2 to n do
    if compare(x[i], midval) < 0 then
        last = last + 1
        temp = x[last]  x[last] = x[i]  x[i] = temp
    end if
    end for

    return quick_sort(x[2..last]) & {midval} & quick_sort(x[last+1..n])
end function


global function hybrid_sort(sequence x)
-- put x into ascending order
-- using recursive quick sort
-- but call insertion sort for short sequences
    natural n, last, midpt
    object midval, temp

    n = length(x)
    if n < hybrid_limit then
    return insertion_sort(x)
    end if

    midpt = floor((n + 1) / 2)
    midval = x[midpt]
    x[midpt] = x[1]

    last = 1
    for i = 2 to n do
    if compare(x[i], midval) < 0 then
        last = last + 1
        temp = x[last]  x[last] = x[i]  x[i] = temp
    end if
    end for

    return hybrid_sort(x[2..last]) & {midval} & hybrid_sort(x[last+1..n])
end function

sequence x

procedure g_insertion_sort()
-- put global variable x into ascending order
-- using insertion sort of general objects
object temp
natural final

    for i = 2 to length(x) do
    temp = x[i]
    final = 1
    for j = i-1 to 1 by -1 do
        if compare(temp, x[j]) < 0 then
        x[j+1] = x[j]
        else
        final = j + 1
        exit
        end if
    end for
    x[final] = temp
    end for
end procedure

procedure best_sort(natural m, natural n)
-- put x into ascending order
-- using recursive quick sort
    natural last, midpt
    object midval, temp

    if n - m < 20 then -- 10 or 20
    return
    end if

    midpt = floor((m + n) / 2)
    midval = x[midpt]
    x[midpt] = x[m]

    last = m
    for i = m+1 to n do
    if compare(x[i], midval) < 0 then
        last = last + 1
        temp = x[last]  x[last] = x[i]  x[i] = temp
    end if
    end for
    x[m] = x[last]
    x[last] = midval
    best_sort(m, last-1)
    best_sort(last+1, n)
end procedure

global function great_sort(sequence a)
-- Avoids dynamic storage allocation - just passes indexes into
-- a global sequence.
-- Not much better than hybrid_sort which makes full use of dynamic
-- storage allocation.
-- Note that we only partition down to a certain degree, then do an
-- insertion sort which will run fast because things are roughly in order.
-- See Knuth for the details
    x = a
    best_sort(1, length(x))
    g_insertion_sort()
    return x
end function

global function merge_sort(sequence x)
-- put x into ascending order
-- using recursive merge sort
    natural n
    sequence x1, x2, newx

    n = length(x)
    if n < 2 then
    return x
    end if

    x1 = merge_sort(x[1..n/2])
    x2 = merge_sort(x[n/2+1..n])
    newx = {}
    while length(x1) > 0 and length(x2) > 0 do
    if compare(x1[1], x2[1]) < 0 then
        newx = append(newx, x1[1])
        x1 = x1[2..length(x1)]
    else
        newx = append(newx, x2[1])
        x2 = x2[2..length(x2)]
    end if
    end while
    newx = newx & x1 & x2 -- one will be empty
    return newx
end function

procedure check_results(sequence sdata, sequence data)
-- compare results with another sort to make sure they are correct
    if CHECK_RESULTS then
        if compare(sdata, shell_sort(data)) != 0 then
        puts(2, "\nabort!\n")
        print(2, 1/0)
        end if
    end if
end procedure

procedure all_sorts()
-- test all sorting routines over a range of numbers of items

    file_number printer
    natural nitems, iterations
    atom t0, t
    sequence data, sdata

    printer = 1   -- open("PRN", "w")
    nitems = 5
    while nitems <= MAX do
    -- get several sets of data of length nitems
    iterations = floor(MAX/nitems)
    if iterations > 500 then
        iterations = 500
    end if
    printf(printer, "\ntime (sec.) to sort %d items (averaged over %d trials)\n",
            {nitems, iterations})

    data = rand(repeat(repeat(nitems, nitems), iterations))
    t0 = time()
    for i = 1 to iterations do
        sdata = bubble_sort(data[i])
        check_results(sdata, data[i])
    end for
    t = time() - t0
    printf(printer, "bubble sort   %9.4f\n", t/iterations)

    t0 = time()
    for i = 1 to iterations do
        sdata =  simple_sort(data[i])
        check_results(sdata, data[i])
    end for
    t = time() - t0
    printf(printer, "simple sort   %9.4f\n", t/iterations)

    t0 = time()
    for i = 1 to iterations do
        sdata = insertion_sort(data[i])
        check_results(sdata, data[i])
    end for
    t = time() - t0
    printf(printer, "insertion sort%9.4f\n", t/iterations)

    t0 = time()
    for i = 1 to iterations do
        sdata = shell_sort(data[i])
        check_results(sdata, data[i])
    end for
    t = time() - t0
    printf(printer, "shell sort    %9.4f\n", t/iterations)

    t0 = time()
    for i = 1 to iterations do
        sdata = merge_sort(data[i])
        check_results(sdata, data[i])
    end for
    t = time() - t0
    printf(printer, "merge sort    %9.4f\n", t/iterations)

    t0 = time()
    for i = 1 to iterations do
        sdata = quick_sort(data[i])
        check_results(sdata, data[i])
    end for
    t = time() - t0
    printf(printer, "quick sort    %9.4f\n", t/iterations)

    for hl = 20 to 20 by 2 do
        hybrid_limit = hl
        t0 = time()
        for i = 1 to iterations do
        sdata = hybrid_sort(data[i])
        check_results(sdata, data[i])
        end for
        t = time() - t0
        printf(printer, "hybrid sort-%d%9.4f\n", {hybrid_limit,t/iterations})
    end for

    for hl = 20 to 20 by 2 do
        hybrid_limit = hl
        t0 = time()
        for i = 1 to iterations do
        sdata = great_sort(data[i])
        check_results(sdata, data[i])
        end for
        t = time() - t0
        printf(printer, "great sort-%d %9.4f\n", {hybrid_limit,t/iterations})
    end for

    puts(1, "\nPress Enter to continue, q to quit: ")
    if find('q', gets(0)) then
        abort(1)
    end if
    nitems = nitems * 2
    end while
end procedure

all_sorts()