Quicksort

[RayYates]

I need to sort a single dim string array. I'd like to NOT use an index for this.

product_name[n]

Any sugestions or code snippets would be appreciated.

[mvmarkus]

Re: Quicksort

Hi Ray,

The following snippet / function performs a not case-sensitive quicksort and should be slightly modified if you want to use a correct sorting of numbers.

<MvFUNCTION NAME = "qsort" PARAMETERS="array VAR" STANDARDOUTPUTLEVEL = "html,text,compresswhitespace">
<MvASSIGN NAME = "l.a" VALUE = "1" >
<MvWHILE EXPR = "{ l.a LE miva_array_max( l.array) }">
<MvIF EXPR = "{ l.array[l.a]} }">
<MvASSIGNARRAY NAME="l.sorted_array" VALUE="{ l.array[l.a]}">
<MvMEMBER NAME="{ l.array[l.a] }">
<MvDIMENSION INDEX="{ miva_array_max( miva_variable_value('l.sorted_array:'$ l.array[l.a]))+1 }">
</MvASSIGNARRAY>
</MvIF>
<MvASSIGN NAME = "l.a" VALUE = "{ l.a+1 }" >
</MvWHILE>

<MvFUNCRETURN VALUE="{ miva_variable_deserialize( trim(l.sorted_array)) }">
</MvFUNCTION>

I didn't test it, but usually something like that works quite nicely.

Markus

[RayYates]

Re: Quicksort

WOOOOOOOA! Thanks.

Fixed a minor bug .
<MvFUNCRETURN VALUE="{ miva_array_deserialize(trim(l.sorted_array)) }">

This is unbelievably fast.

I had implemented a bubble sort (suitable for sorting a dozen items);
and an Insertion sort (suitable for sorting a few hundred items)
But look at these test results for Qsort (suitable for sorting tens of thousands of items)


Sort 10000 text strings

Make Data: 0.172 sec.
Bubble Sort Time: 204.125 sec.
Insertions Sort Time: 57.937 sec.
QSort Time: 0.266 sec.


For 100,000 items QSort Time: 10.797


For Posterity:

<MvFUNCTION NAME = "qsort" PARAMETERS="array VAR" STANDARDOUTPUTLEVEL = "">
    <MvASSIGN NAME = "l.a" VALUE = "1" >
    <MvASSIGN NAME="l.max" VALUE="{ miva_array_max( l.array)  }">
    <MvWHILE EXPR = "{ l.a LE l.max }">
        <MvIF EXPR = "{ l.array[l.a] }">
            <MvASSIGNARRAY NAME="l.sorted_array" VALUE="{ l.array[l.a] }">
            <MvMEMBER NAME="{ l.array[l.a] }">
            <MvDIMENSION INDEX="{ miva_array_max( miva_variable_value('l.sorted_array:'$ l.array[l.a]))+1 }">
            </MvASSIGNARRAY>
        </MvIF>
        <MvASSIGN NAME = "l.a" VALUE = "{ l.a+1 }" >
    </MvWHILE>
    <MvFUNCRETURN VALUE="{ miva_array_deserialize(trim(l.sorted_array)) }">
</MvFUNCTION>