Announcement

Collapse

Forum Guidelines

This forum is for finished source code that is working properly. If you have questions about this or any other source code, please post it in one of the Discussion Forums, not here.
See more
See less

Simple and versatile prioritized index sorting

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

  • Simple and versatile prioritized index sorting

    ' simple and versatile prioritized index sorting
    '
    ' the advantage of index sorting is that the data being sorted need not
    ' be moved, but can stay unchanged in their place. this is in contrast
    ' to ordinary sorting in which the original position of items is lost
    ' and cannot be retrieved.
    '
    ' an index array is formed which holds the sequence of the data after
    ' sorting. for example, after ascending sorting the 3rd smallest value
    ' will be vararray(index(3)). after ordinary sorting it would just have
    ' been vararray(3).
    '
    ' the routine presented is simple and versatile: it can sort ascending,
    ' descending, numerical and alphabetical according to your wish. it can
    ' perform partial sorting (of only part of the data), mixed sorting
    ' (according to one variable for one part of the data and according to another
    ' variable for another part of the data), as well as prioritized sorting.
    ' prioritized sorting is relevant if many items are the same for a
    ' variable e.g. family name, since within each of these you can sort
    ' according to a secondary variable like first name. if you still
    ' have many persons with the same family name and first name, you can
    ' within each of these combinations sort according to a third variable
    ' like age and so on. in principle you can perform prioritized sorting
    ' according to all the variables in the dataset.
    '
    ' the present program presents a simple sorting routine which does not
    ' exchange equal data. this is an essential feature if a sorting routine
    ' should be used for prioritized sorting. the principle is this: you sort
    ' first according to the least prioritized variable, then according to the
    ' second least prioritized and so on until you end up sorting the
    ' variable with the highest sorting priority.

    ' when you then present the data in sequence according to the
    ' index obtained in the above process, the positions of the data will
    ' be as you wanted.

    ' this small code shows the possible application for a database which
    ' stores the data in a two-dimensional string array. it simulates
    ' such a small database.
    '
    ' best regards and happy new year
    '
    ' erik

    ' p.s. if you need a faster but also more complex method for
    ' prioritized sorting, see these links:
    '
    ' http://www.powerbasic.com/support/pb...ad.php?t=22920
    '
    ' http://www.powerbasic.com/support/pb...ad.php?t=23789
    '
    ' january 1st, 2005: minor improvements made.
    ' later same day: further improvements in regard to speed.
    Code:
    #compile exe
    #register none
    #dim all
    #include "win32api.inc"
    '
    sub shakerindexsort(byref c() as string, byref index() as long, _
                        byval startrow as long, byval endrow as long, byval col as long, _
                        byval ad as long, byval an as long)
       ' a bubblesort modified for passing through the data in alternate directions.
       ' modified for index sorting - ascending or descending - alphabetic or numeric
       local l&,r&,i&,sw&
       '
       l = startrow
       r = endrow - 1
       '
       i = ad * 2 + an + 1 ' 1 to 4
       on i gosub ascendingalphabetical, ascendingnumerical, descendingalphabetical, descendingnumerical
       exit sub
       '
       ascendingalphabetical:
       do
          sw = 0
          ' forward pass ...
          for i = l to r
             if c(col,index(i)) > c(col,index(i+1)) then swap index(i),index(i+1) : sw = i
          next i
          '
          r = sw
          ' backward pass ...
          for i = r to l step -1
             if c(col,index(i)) > c(col,index(i+1)) then swap index(i),index(i+1) : sw = i
          next i
          '
          l = sw
       loop until sw = 0 ' loop until no exchanges occur
       return
       '
       ascendingnumerical:
       do
          sw = 0
          for i = l to r
             if val(c(col,index(i))) > val(c(col,index(i+1))) then swap index(i),index(i+1) : sw = i
          next i
          r = sw
          for i = r to l step -1
             if val(c(col,index(i))) > val(c(col,index(i+1))) then swap index(i),index(i+1) : sw = i
          next i
          l = sw
       loop until sw = 0
       return
       '
       descendingalphabetical:
       do
          sw = 0
          for i = l to r
             if c(col,index(i)) < c(col,index(i+1)) then swap index(i),index(i+1) : sw = i
          next i
          r = sw
          for i = r to l step -1
             if c(col,index(i)) < c(col,index(i+1)) then swap index(i),index(i+1) : sw = i
          next i
          l = sw
       loop until sw = 0
       return
       '
       descendingnumerical:
       do
          sw = 0
          for i = l to r
             if val(c(col,index(i))) < val(c(col,index(i+1))) then swap index(i),index(i+1) : sw = i
          next i
          r = sw
          for i = r to l step -1
             if val(c(col,index(i))) < val(c(col,index(i+1))) then swap index(i),index(i+1) : sw = i
          next i
          l = sw
       loop until sw = 0
       return
       '
    end sub
    '
    sub showdata(byref dataarray() as string, byref index() as long, byval r as long, byval c as long, byval t as string)
        local b$,i&,j&
        b$="
        for i&=1 to r
            for j&=1 to c
                b$=b$+dataarray(j&,index(i&))+$tab
            next
            b$=b$+$crlf
        next
        msgbox b$,,t$
    end sub
    '
    function pbmain()
        local i&,j&,k&
        local r as long
        local c as long
        r=20 ' rows
        c=4  ' columns
        dim dataarray(1:c,1:r) as local string
        dim index(1:r) as local long
        '
        data "hans","jensen","34","copenhagen"
        data "john","andersen","46","stockholm"
        data "hans","jensen","6","paris"
        data "niels","carlsen","28","new york"
        data "erik","jensen","47","london"
        data "john","smith","65","berlin"
        data "john","jensen","9","los angeles"
        data "hans","andersen","21","oslo"
        data "john","andersen","7","copenhagen"
        data "hans","carlsen","33","paris"
        data "peter","carlsen","34","london"
        data "john","smith","45","stockholm"
        data "hans","carlsen","33","new york"
        data "peter","jensen","23","new york"
        data "erik","carlsen","26","stockholm"
        data "john","smith","45","oslo"
        data "jack","andersen","36","berlin"
        data "hans","smith","35","los angeles"
        data "hans","carlsen","64","los angeles"
        data "carl","smith","36","oslo"
        '
        for i&=1 to r
            for j&=1 to c
                k&=(i&-1)*c + j&
                dataarray(j&,i&)=read$(k&)
            next
            index(i&) = i&
        next
        call showdata(dataarray(), index(), r, c,"original unsorted data:")
        '
        msgbox "sorting according to single variables!", %mb_iconinformation, "first:"
        '
        '                                          startrow  endrow  col  ad  an
        '                                                                 01  01
        call shakerindexsort(dataarray(), index(), 1,        20,     4,   0,  0)
        call showdata(dataarray(), index(), r, c,"ascending alphabetical sorting according to city:")
        '
        for i&=1 to r : index(i&) = i& : next ' reset original sequence first. optional.
        call shakerindexsort(dataarray(), index(), 1,        20,     4,   1,  0)
        call showdata(dataarray(), index(), r, c,"descending alphabetical sorting according to city:")
        '
        for i&=1 to r : index(i&) = i& : next ' reset original sequence first. optional.
        call shakerindexsort(dataarray(), index(), 1,        20,     3,   0,  1)
        call showdata(dataarray(), index(), r, c,"ascending numerical sorting according to age:")
        '
        for i&=1 to r : index(i&) = i& : next ' reset original sequence first. optional.
        call shakerindexsort(dataarray(), index(), 1,        20,     3,   0,  0)
        call showdata(dataarray(), index(), r, c,"ascending alphabetic sorting according to age (not good):")
        '
        msgbox "partial sorting: sorting part of the array!", %mb_iconinformation, "second:"
        '
        for i&=1 to r : index(i&) = i& : next ' reset original sequence first.
        call shakerindexsort(dataarray(), index(), 1,        10,     2,   0,  0)
        call showdata(dataarray(), index(), r, c,"partial (1-10) ascending alphabetical sorting according to family name:")
        '
        for i&=1 to r : index(i&) = i& : next ' reset original sequence first. optional.
        call shakerindexsort(dataarray(), index(), 1,        10,     3,   0,  1)
        call shakerindexsort(dataarray(), index(), 11,       20,     3,   1,  1)
        call showdata(dataarray(), index(), r, c,"ascending (1-10) and descending (11-20) sorting according to age:")
        '
        msgbox "mixed sorting: sorting various parts of different variables!", %mb_iconinformation, "third:"
        '
        for i&=1 to r : index(i&) = i& : next ' reset original sequence first. optional.
        call shakerindexsort(dataarray(), index(), 1,        10,     3,   0,  1)
        call shakerindexsort(dataarray(), index(), 11,       20,     4,   0,  0)
        call showdata(dataarray(), index(), r, c,"mixed ascending sorting according to age (1-10) and city (11-20):")
        '
        msgbox "prioritized sorting!", %mb_iconinformation, "now for the real thing:"
        for i&=1 to r : index(i&) = i& : next ' reset original sequence first. optional.
        call shakerindexsort(dataarray(), index(), 1,        20,     1,   0,  0)
        call shakerindexsort(dataarray(), index(), 1,        20,     2,   0,  0)
        call showdata(dataarray(), index(), r, c,"prioritized ascending sorting according to 1 family name and 2 first name:")
        '
        for i&=1 to r : index(i&) = i& : next ' reset original sequence first. optional.
        call shakerindexsort(dataarray(), index(), 1,        20,     3,   0,  1)
        call shakerindexsort(dataarray(), index(), 1,        20,     2,   0,  0)
        call showdata(dataarray(), index(), r, c,"prioritized ascending sorting according to 1 family name and 2 age:")
        '
        for i&=1 to r : index(i&) = i& : next ' reset original sequence first. optional.
        call shakerindexsort(dataarray(), index(), 1,        20,     4,   0,  0)
        call shakerindexsort(dataarray(), index(), 1,        20,     2,   0,  0)
        call showdata(dataarray(), index(), r, c,"prioritized ascending sorting according to 1 family name and 2 city:")
        '
        for i&=1 to r : index(i&) = i& : next ' reset original sequence first. optional.
        call shakerindexsort(dataarray(), index(), 1,        20,     3,   0,  1)
        call shakerindexsort(dataarray(), index(), 1,        20,     1,   0,  0)
        call shakerindexsort(dataarray(), index(), 1,        20,     2,   0,  0)
        call showdata(dataarray(), index(), r, c,"prioritized sorting according to 1 family name, 2 first name and 3 age:")
        '
        for i&=1 to r : index(i&) = i& : next
        call showdata(dataarray(), index(), r, c,"original unsorted data:")
        msgbox "that was it... happy new year!", %mb_iconinformation, "seasons greetings"
        '
    end function


    [this message has been edited by erik christensen (edited january 01, 2005).]

  • #2
    A QuickSort is generally faster than a Bubble Sort. You can make
    the Bubble Sort faster on the leg down if you replace that FOR
    loop with a binary search technique - this is applicable because
    the array to that point has been successfully sorted.

    AFAIK, QuickSort is the fastest sort that retains some vestige of
    original indexed order. That is, you can perform sequential sorts
    on different fields and achieve a complex order sort by starting
    with the least significant field and progressing to the most
    significant field.

    ARRAY SORT actually sorts the Array and any TAGARRAY associated
    with it. If the array to be sorted is rendered from a multi-
    dimensional Array and made single dimensioned, and the TAGARRAY
    is based on the existing sort order, you can resort with the
    ARRAY SORT far faster than you can with your own code. Then
    you just apply the TAGARRAY's array as an index to the proper
    dimension in the Multidimensioned Array.

    ARRAY SORT is going to handle UDT arrays as though they are
    string arrays, which is not likely to be what you had in mind.
    However, you can create an array of the type of any UDT field
    and copy that field to the array, sort it instead, and get the
    right results via the TAGARRAY's index array.

    ------------------
    Old Navy Chief, Systems Engineer, Systems Analyst, now semi-retired

    Comment


    • #3
      the method described in the first post requires that the sorting
      routine applied does not exchange equal data (like values).
      the few sorting routines, that i know of, that have this quality
      are bubble sort, shaker sort (which is a modified bubble sort
      to improve speed) and insertion sort. however, quick sort,
      shell sort, pyramid or heap sort and select sort may all exhange
      equal data. the same applies to pb’s array sort, see this link:

      array sort swaps like values
      http://www.powerbasic.com/support/pb...ead.php?t=9486

      sorting routines that exchange equal data cannot perform
      prioritized sorting according to the method described.
      naturally that method is not very fast, but it is completely
      feasible for smaller databases. i just wanted to present
      the method for illustrative purposes.

      for larger databases the method described in the links provided
      in the first post is the preferable extremely fast method.

      here are some links to other related issues:

      index sort using powerbasic's array sort with tagarray option
      http://www.powerbasic.com/support/pb...ad.php?t=24093

      shakersort - sorting without exchange of equal data
      http://www.powerbasic.com/support/pb...ad.php?t=24098

      best regards,

      erik


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




      [this message has been edited by erik christensen (edited january 05, 2005).]

      Comment

      Working...
      X