Demo entry 6339253

313123

   

Submitted by anonymous on Dec 20, 2016 at 15:20
Language: C++. Code size: 1.9 kB.

const CUTOFF = 8

function shortsort(low, high, width, compare())
    while high > low
        max = low
        for p = low + width to high, step = width
            if compare(p, max) > 0
                max = p
        swap(max, high)

        hi = hi - width

function qsort(base, num, width, comp())
    if num < 2 or width = 0 ruturn
    stack_ptr = 0
    low = base
    high = base + width * (num - 1)

label recurse:
    size = (high - low) / width + 1
    if (size <= CUTOFF)
        shortsort(low, high, width, compare())
    else
        mid = low + (size / 2) * width
        if (compare(low, mid) > 0) swap(low, mid)
        if (compare(low, high) > 0) swap(low, high)
        if (compare(mid, high) > 0) swap(mid, high)

        lowguy = low
        highguy = high

        while (1)
            if mid > lowguy
                increase lowguy until lowguy >= mid or a[lowguy] > a[mid]

            if mid <= lowguy
                increase lowguy until lowguy > high or a[lowguy] <= a[mid]

            decrease highguy until highguy <= mid or a[highguy] <= a[mid]

            if (highguy < lowguy) break

            swap(lowguy, highguy)

            if mid == highguy
                mid = lowguy

        highguy = highguy + width
        if (mid < highguy)
            decrease highguy until highguy <= mid or a[highguy] != a[mid]
        if (mid >= highguy)
            decrease highguy until highguy <= low or a[highguy] != a[mid]

        if (highguy - low >= high - lowguy)
            if low < highguy
                push low to low_stack
                push highguy to high_stack
            if lowguy < high
                low = lowguy
                goto recurse
    if low_stack is not unique
        low = pop low_stack
        high = pop high_stack
        goto recurse
    else
        return

This snippet took 0.00 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).