Announcement

Collapse
No announcement yet.

Quicksort

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

    Quicksort

    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.
    Ray Yates
    "If I have seen further, it is by standing on the shoulders of giants."
    --- Sir Isaac Newton

    #2
    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
    Emerald Media, Trade & Technology USA/Germany
    Professional Miva Programming since 1998
    Home of the Emerald Objects Application Server (EOA)
    Multi-dimensional CRM, CMS & E-Commerce

    http://www.emeraldobjects.com
    http://www.sylter-seiten.com

    Comment


      #3
      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:
      Code:
      <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>
      Ray Yates
      "If I have seen further, it is by standing on the shoulders of giants."
      --- Sir Isaac Newton

      Comment

      Working...
      X