Sorting text alphabetically

mhermanns · January 2006

Has anyone a good (fast) function for sorting text (min. 100 names) alphabetically?

maxifox · January 2006

I have not that ready but how about shellsort algorithm?

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm

mhermanns · January 2006

The shellsort algorithm is a good choice. But much better would be a ready to use source code... ;-)

Joe Hebert · January 2006

Bubble Sort

Here is a Bubble Sort routine. I?m sure there are faster sorts but this is the only one I?ve ever learned to write and it?s been fast enough for my purposes. Perhaps it will be fast enough for you.

The sort function will alphabetize by last name and then by first name.

DEFINE_DEVICE

dvTP	= 10001:1:0


DEFINE_CONSTANT

INTEGER nMaxProfiles	= 5


DEFINE_TYPE

STRUCTURE _sProfile {		

   INTEGER 	ID		
   CHAR		LastName[32]	
   CHAR		FirstName[32]
}


DEFINE_VARIABLE

_sProfile 	sProfiles[nMaxProfiles]


DEFINE_FUNCTION fnInitPofiles() {

sProfiles[1].ID	= 1
sProfiles[1].FirstName= 'John'
sProfiles[1].LastName	= 'Doe'

sProfiles[2].ID	= 2
sProfiles[2].FirstName= 'Jane'
sProfiles[2].LastName	= 'Doe'

sProfiles[3].ID	= 3
sProfiles[3].FirstName= 'Joe'
sProfiles[3].LastName	= 'Crow'

sProfiles[4].ID	= 4
sProfiles[4].FirstName= 'Bullwinkle '
sProfiles[4].LastName	= 'Moose'

sProfiles[5].ID	= 5
sProfiles[5].FirstName= 'Garfield'
sProfiles[5].LastName	= 'Goose'


}

DEFINE_FUNCTION fnSortByLastName() {

   INTEGER 	x
   INTEGER 	y
   INTEGER 	tempID
   CHAR		tempLastName[32]
   CHAR		tempFirstName[32]
      
   //bubble sort
   //bubble up the smaller names (alphabetically) by pushing the bigger names down
   FOR (x=1; x<nMaxProfiles; x++) {

      FOR (y=1; y<nMaxProfiles; y++) {
	 
	 //if position y > position y+ 1 then swap
	 IF ("sProfiles[y].LastName,sProfiles[y].FirstName" >
	       "sProfiles[y+1].LastName,sProfiles[y+1].FirstName") {
	 
	    tempID 			= sProfiles[y+1].ID
	    tempLastName 		= sProfiles[y+1].LastName
	    tempFirstName 		= sProfiles[y+1].FirstName
	    
	    sProfiles[y+1].ID		= sProfiles[y].ID
	    sProfiles[y+1].LastName 	= sProfiles[y].LastName
	    sProfiles[y+1].FirstName 	= sProfiles[y].FirstName
	    
	    sProfiles[y].ID		= tempID
	    sProfiles[y].LastName	= tempLastName
	    sProfiles[y].FirstName	= tempFirstName
	    
	 }
      }
   }

}

DEFINE_START

fnInitPofiles()

DEFINE_EVENT

BUTTON_EVENT[dvTP,1] {  //sort the profiles by last name

   PUSH: {
      fnSortByLastName()
   }
}

BUTTON_EVENT[dvTP,2] {  //reset profiles to original order

   PUSH: {
      fnInitPofiles()
   }
}

mhermanns · January 2006

looks good. thank you, joe!

Joe Hebert · January 2006

You're welcome, Micha. If you come across a faster sort algorithm please post it.

mhermanns · January 2006

i just coded the shellsort algorithm, that maxifox suggested.

-> http://www.iti.fh-flensburg.de/lang...ell/shellen.htm

This is definitely a very fast algorithm, but i can't test it right now (no hardware). I will post it, when i'am sure that it works fine (next week?).

In case i forget it, please send me a mail...

frthomas · January 2006

Quicksort

Here is an implementation of Quicksort (see http://linux.wku.edu/~lamonml/algor/sort/quick.html for info). It is recursive so don't use it on Netlinx to sort 10'000 items...

The function DoSort sorts an array of integers (myArray). The function Sort is the one doing the work.

Note that if you're sorting "large" data sets, swapping elements can be CPU intensive so you're better off sorting an index (and the reason why the sort routine below operates on an integer array). That is, the data is in an array of large structs Data with elements 1..N. You create an integer array DataSorted giving the position of the element in Data (initially, the indexes are the same so DataSorted = i), and you "sort this array" (and access the data in sorted fashion using Data[DataSorted]); that is, the sorted array gives you the sequences of indexes in Data to get Data in sorted fashion (another advantage is that you can maintain multiple sort orders in parallel).
If you want to do that you need to change in Sort the two comparisons: aInt[iHi] > tempInt AND aInt[iLo] <= tempInt with equivalent comparisons on Data (f.e. Data[aInt[iHi]].last_name > Data[tempInt].last_name), or create functions to compare elements together if you want to sort by last, first name and then by area code and phone number.

Very fast. On my old NE master I need 6 ticks (GET_TIMER units) to sort 200 elements.

HTH

Fred

DEFINE_FUNCTION Sort(INTEGER aInt[], INTEGER myLow, INTEGER myHigh)
{
    STACK_VAR INTEGER iLo;
    STACK_VAR INTEGER iHi;
    STACK_VAR INTEGER Low;
    STACK_VAR INTEGER High;
    STACK_VAR INTEGER tempInt;

    Low  = myLow;
    High = myHigh;

    WHILE (Low < High)
    {
	iLo     = Low;
	iHi     = High;
	tempInt = aInt[Low];

	WHILE (iLo < iHi)     // split list in two
	{//GAs[GAsPos[j]].sGA > GAs[GAsPos[i]].sGA
	FOR (; (aInt[iHi] > tempInt) && (iHi > 1); iHi--);
	    FOR (aInt[iLo] = aInt[iHi]; (iLo < iHi) && (aInt[iLo] <= tempInt); iLo++);
		aInt[iHi] = aInt[iLo];
	} (* While *)
	aInt[iLo] = tempInt;
	// sort recursively, the smallest first
	IF (iLo - Low < High - iLo)
	{
	    Sort(aInt, Low, iLo - 1);
	    Low = iLo + 1;
	}
	ELSE
	{
	    Sort(aInt, iLo + 1, High);
	    High = iLo - 1;
	}
    } (* While *)
}

DEFINE_FUNCTION DoSort()
{
    Sort(myArray, 1, LENGTH_ARRAY(myArray));
}

mhermanns · January 2006

Here is the implementation of ShellSort:

DEFINE_CONSTANT
INTEGER hSequence[8] = {701,301,132,57,23,10,4,1} // best known h-sequence (average)


DEFINE_TYPE
STRUCTURE STRUCT_PHONEBOOK
{		
  INTEGER phonebookID		
  CHAR phonebookName[32]	
}


DEFINE_VARIABLE
VOLATILE STRUCT_PHONEBOOK phonebook[1000] // for example



DEFINE_CALL'ShellSort'
{
  LOCAL_VAR VOLATILE STRUCT_PHONEBOOK shellsortSaver
  LOCAL_VAR VOLATILE INTEGER structPhonebookLength,hSequenceLength
  LOCAL_VAR VOLATILE INTEGER i,j,k,h
	
  hSequenceLength=LENGTH_ARRAY(hSequence)
  structPhonebookLength=LENGTH_ARRAY(phonebook)

  SEND_STRING 0,"'Sorting phonebook...'"

  FOR(k=1;k<=hSequenceLength;k++)
  {
    h=hSequence[k]
    FOR(i=h+1;i<=structPhonebookLength;i++)
    {
      j=i
      shellsortSaver=phonebook[j]
      LONG_WHILE((j>h)AND("phonebook[j-h].phonebookName">"shellsortSaver.phonebookName"))
      {
        phonebook[j]=phonebook[j-h]
        j=j-h
      }
      phonebook[j]=shellsortSaver
    }
  }

  SEND_STRING 0,"'Sorting phonebook...OK'"
}

AMXJeff · December 2007

Joe,

Looks good the only thing I would change, to speed it up, is to not check the sorted array elements again and again. See the "y=x + 1" in the second for loop.

   FOR (x=1; x<nMaxProfiles; x++) {

      FOR (y=x + 1; y<nMaxProfiles; y++) {

Joe Hebert wrote:

Here is a Bubble Sort routine. I’m sure there are faster sorts but this is the only one I’ve ever learned to write and it’s been fast enough for my purposes. Perhaps it will be fast enough for you.

The sort function will alphabetize by last name and then by first name.

DEFINE_DEVICE

dvTP	= 10001:1:0


DEFINE_CONSTANT

INTEGER nMaxProfiles	= 5


DEFINE_TYPE

STRUCTURE _sProfile {		

   INTEGER 	ID		
   CHAR		LastName[32]	
   CHAR		FirstName[32]
}


DEFINE_VARIABLE

_sProfile 	sProfiles[nMaxProfiles]


DEFINE_FUNCTION fnInitPofiles() {

sProfiles[1].ID	= 1
sProfiles[1].FirstName= 'John'
sProfiles[1].LastName	= 'Doe'

sProfiles[2].ID	= 2
sProfiles[2].FirstName= 'Jane'
sProfiles[2].LastName	= 'Doe'

sProfiles[3].ID	= 3
sProfiles[3].FirstName= 'Joe'
sProfiles[3].LastName	= 'Crow'

sProfiles[4].ID	= 4
sProfiles[4].FirstName= 'Bullwinkle '
sProfiles[4].LastName	= 'Moose'

sProfiles[5].ID	= 5
sProfiles[5].FirstName= 'Garfield'
sProfiles[5].LastName	= 'Goose'


}

DEFINE_FUNCTION fnSortByLastName() {

   INTEGER 	x
   INTEGER 	y
   INTEGER 	tempID
   CHAR		tempLastName[32]
   CHAR		tempFirstName[32]
      
   //bubble sort
   //bubble up the smaller names (alphabetically) by pushing the bigger names down
   FOR (x=1; x<nMaxProfiles; x++) {

      FOR (y=1; y<nMaxProfiles; y++) {
	 
	 //if position y > position y+ 1 then swap
	 IF ("sProfiles[y].LastName,sProfiles[y].FirstName" >
	       "sProfiles[y+1].LastName,sProfiles[y+1].FirstName") {
	 
	    tempID 			= sProfiles[y+1].ID
	    tempLastName 		= sProfiles[y+1].LastName
	    tempFirstName 		= sProfiles[y+1].FirstName
	    
	    sProfiles[y+1].ID		= sProfiles[y].ID
	    sProfiles[y+1].LastName 	= sProfiles[y].LastName
	    sProfiles[y+1].FirstName 	= sProfiles[y].FirstName
	    
	    sProfiles[y].ID		= tempID
	    sProfiles[y].LastName	= tempLastName
	    sProfiles[y].FirstName	= tempFirstName
	    
	 }
      }
   }

}

DEFINE_START

fnInitPofiles()

DEFINE_EVENT

BUTTON_EVENT[dvTP,1] {  //sort the profiles by last name

   PUSH: {
      fnSortByLastName()
   }
}

BUTTON_EVENT[dvTP,2] {  //reset profiles to original order

   PUSH: {
      fnInitPofiles()
   }
}

Joe Hebert · December 2007

AMXJeff wrote:
Joe,

Looks good the only thing I would change, to speed it up, is to not check the sorted array elements again and again. See the "y=x + 1" in the second for loop.
   FOR (x=1; x<nMaxProfiles; x++) {

      FOR (y=x + 1; y<nMaxProfiles; y++) {

Good catch Jeff but I think you inadvertently looked at it upside down and the sort will be incorrect. The first time through the array the smallest element will not be at the top. Instead the biggest element will be at the bottom. The smaller elements bubble to the top by pushing the bigger elements down. So?

Instead of your proposed second loop of:
FOR (y=x + 1; y<nMaxProfiles; y++) {

I think it should be:
FOR (y=1; y<=nMaxProfiles-x; y++) {

And yes that will speed things up since it doesn?t need to check the sorted elements more than once. Thanks for pointing it out.

I suppose I could have made it potentially event quicker if I added a flag to test if a swap was made in the second loop because if no swaps were made then we can break out since the sort must be complete.

Spire_Jeff · December 2007

I haven't been following this thread too well, but would it make sense to create a temporary array that adds a pointer value and then do the sort routine by just moving the pointer. After the array is sorted, write the appropriate values into the original array. I am just thinking that with a larger array, it would be a lot faster to just shuffle a single integer pointer as needed as opposed to writing all of the strings back and forth. Actually, there isn't a need to create anything other than an array of pointers. Here is the modified code.

DEFINE_DEVICE

dvTP	= 10001:1:0


DEFINE_CONSTANT

INTEGER nMaxProfiles	= 100
LONG  lTL_ID = 1

DEFINE_TYPE

STRUCTURE _sProfile {		

   INTEGER 	ID		
   CHAR		LastName[32]	
   CHAR		FirstName[32]
}


DEFINE_VARIABLE

_sProfile 	sProfiles[nMaxProfiles]
LONG 	lTL_Times[5] = {100,100,100,100,100}
LONG	lINDEX_TIME
LONG	lSTRING_TIME

DEFINE_FUNCTION fnInitPofiles() {
STACK_VAR INTEGER x;
STACK_VAR INTEGER y;
STACK_VAR INTEGER z;
STACK_VAR CHAR RNDM_NAME[20];

	FOR(x=1;x<=nMaxProfiles;x++)
	{
		z = RANDOM_NUMBER(15) + 5 //Determine Random length for Last Name 5 Char Minimum
		SET_LENGTH_ARRAY(RNDM_NAME,z)
		FOR(y=1;y<=z;y++)
			RNDM_NAME[y] = (RANDOM_NUMBER(26) + 65)
		sProfiles[x].LastName	= RNDM_NAME
	
		z = RANDOM_NUMBER(10) + 3 //Determine Random length for First Name 3 Char Minimum
		SET_LENGTH_ARRAY(RNDM_NAME,z)
		FOR(y=1;y<=z;y++)
			RNDM_NAME[y] = (RANDOM_NUMBER(26) + 65)
		sProfiles[x].FirstName= RNDM_NAME
		
		sProfiles[x].ID	= x
	}

}

DEFINE_FUNCTION fnSortByLastName_Index() {

  INTEGER 	x
  INTEGER 	y
  INTEGER 	tempID
  CHAR		tempLastName[32]
  CHAR		tempFirstName[32]
  INTEGER nPTR[nMaxProfiles]
	
	TIMELINE_CREATE(lTL_ID,lTL_Times,5,TIMELINE_RELATIVE,TIMELINE_REPEAT)
	
	FOR(x=1; x<=nMaxProfiles; x++)
		nPTR[x] = x;
		
   
  //bubble sort
  //bubble up the smaller names (alphabetically) by pushing the bigger names down
  FOR (x=1; x<nMaxProfiles; x++) {
    FOR (y=1; y<=nMaxProfiles-x; y++) {
			//if position y > position y+ 1 then swap
			IF ("sProfiles[nPTR[y]].LastName,sProfiles[nPTR[y]].FirstName" >
	       "sProfiles[nPTR[y+1]].LastName,sProfiles[nPTR[y+1]].FirstName") {
	 
				tempID 			= nPTR[y]	
				nPTR[y]			= nPTR[y+1]
				nPTR[y+1] 	=	tempID
	    
			}
		}
	}
	FOR(x=1;x<=nMaxProfiles;x++) {
		tempID = sProfiles[x].ID
		tempLastName = sProfiles[x].LastName
		tempFirstName = sProfiles[x].FirstName
		
		sProfiles[x].ID = sProfiles[nPTR[x]].ID
		sProfiles[x].LastName = sProfiles[nPTR[x]].LastName
		sProfiles[x].FirstName = sProfiles[nPTR[x]].FirstName
		
		sProfiles[nPTR[x]].ID = tempID
		sProfiles[nPTR[x]].LastName = tempLastName
		sProfiles[nPTR[x]].FirstName = tempFirstName
		
		y=x
		while(y<=nMaxProfiles AND nPTR[y] <> x)
			y++
		IF(y<=nMaxProfiles)
			nPTR[y] = nPTR[x]
	}
	
	TIMELINE_PAUSE(lTL_ID)
	lINDEX_TIME = TIMELINE_GET(lTL_ID)
	TIMELINE_KILL(lTL_ID)

}

DEFINE_FUNCTION fnSortByLastName_String() {

  INTEGER 	x
  INTEGER 	y
  INTEGER 	tempID
  CHAR		tempLastName[32]
  CHAR		tempFirstName[32]

	TIMELINE_CREATE(lTL_ID,lTL_Times,5,TIMELINE_RELATIVE,TIMELINE_REPEAT)
      
   //bubble sort
   //bubble up the smaller names (alphabetically) by pushing the bigger names down
  FOR (x=1; x<nMaxProfiles; x++) {
    FOR (y=1; y<nMaxProfiles; y++) {
	 
	 //if position y > position y+ 1 then swap
			IF ("sProfiles[y].LastName,sProfiles[y].FirstName" >
	       "sProfiles[y+1].LastName,sProfiles[y+1].FirstName") {
	 
	    tempID 			= sProfiles[y+1].ID
	    tempLastName 		= sProfiles[y+1].LastName
	    tempFirstName 		= sProfiles[y+1].FirstName
	    
	    sProfiles[y+1].ID		= sProfiles[y].ID
	    sProfiles[y+1].LastName 	= sProfiles[y].LastName
	    sProfiles[y+1].FirstName 	= sProfiles[y].FirstName
	    
	    sProfiles[y].ID		= tempID
	    sProfiles[y].LastName	= tempLastName
	    sProfiles[y].FirstName	= tempFirstName
	    }
		}
	}
	TIMELINE_PAUSE(lTL_ID)
	lSTRING_TIME = TIMELINE_GET(lTL_ID)
	TIMELINE_KILL(lTL_ID)
	
}


DEFINE_START

fnInitPofiles()

DEFINE_EVENT

BUTTON_EVENT[dvTP,1] {  //sort the profiles by last name

   PUSH: {
      fnSortByLastName_String()
   }
}

BUTTON_EVENT[dvTP,2] {  //reset profiles to original order

   PUSH: {
      fnInitPofiles()
   }
}
BUTTON_EVENT[dvTP,3] {  //sort the profiles by last name

   PUSH: {
      fnSortByLastName_Index()
   }
}

I also bumped up the number of records to 100 and randomized the population of the data.
I then added a timeline to track execution time as closely as I could come up with in the last couple minutes. These are the results I got from an NI-3000 running nothing more than this code.

Run Number\ Indexed | String
1 | 1989ms | 4029ms
2 | 1978ms | 4121ms
3 | 1951ms | 3896ms
4 | 1967ms | 4038ms

I also checked a completely sorted list and got these numbers:
Indexed : 1606ms
String: 2670ms

I would appreciate somebody checking my time measurements as well as the methods I'm using for timing. As I type this up, I could have probably set the timeline times to be very large to minimize timeline events from happening during the sort, but I'm lazy, so someone else can do that if they like

Have fun,
Jeff

Spire_Jeff · December 2007

Ok, I was having a VERY Rough time with the shell sort algorithm. I worked through the implementation based on the website provided and the AMX code that mhermanns provided. It took me a few to get it parsing correctly, and once I did, I was VERY disappointed. I was expecting fairly quick sorting, but running the shell sort took so long I thought I was stuck in an infinite loop. A little debugging showed that everything was moving along as it should, it just took FOREVER. I upped the qty to 250 for this last round of testing, and the shell sort was taking soooooo long that the timeline milliseconds were wrapping around. I was getting reports of 20000, but it was taking MANY MINUTES for it too complete. I was just about to give up on the shell sort and be ok with the fact that either I coded it wrong or it wasn't that fast. In a last ditch effort, I changed the LONG_WHILE to a standard WHILE....OMG! HUGE Difference!

DO NOT USE LONG_WHILE in Netlinx code. I think they talk about it in the help file stating that it should not be used in an event. Based on this experience...DO NOT EVER USE IT

Anyway, here are the new times:

250 data elements

String Sort: 28369ms
Indexed Sort: 12275ms
Shell (Pratt): 3577ms
Shell (mhermanns): 2370ms

There wasn't a big difference between running the Papernov-Stasevic, Sedgewick, and the mhermanns column number break down. The Pratt column numbers did take a little longer.

Here are the time on a presorted list:

250 data elements

String Sort: 17322ms
Indexed Sort: 10036ms
Shell (Pratt): 1733ms
Shell (mhermanns): 591ms

I think it's clear which algorithm is the fastest

Here is the newest version of code I was using that has all three functions. They are not what I would call polished and complete, but they should give a fairly good jump to anyone that needs to use them.

DEFINE_DEVICE

dvTP	= 10001:1:0


DEFINE_CONSTANT

INTEGER nMaxProfiles	= 250
LONG  lTL_ID = 1

INTEGER NumColumns1[] = {108,96,81,72,64,54,48,36,32,27,24,18,16,12,9,8,6,4,3,2,1} //Portion of Pratt
INTEGER NumColumns2[] = {701,301,132,57,23,10,4,1} // best known h-sequence (average)
INTEGER NumColumns3[] = {4592,1968,861,336,112,48,21,7,3,1} //Sedgewick
INTEGER NumColumns4[] = {8191,4095,2047,1023,511,255,127,63,31,15,7,3,1} //Papernov-Stasevic
DEFINE_TYPE

STRUCTURE _sProfile {		

   INTEGER 	ID		
   CHAR		LastName[32]	
   CHAR		FirstName[32]
}


DEFINE_VARIABLE

_sProfile 	sProfiles[nMaxProfiles]
LONG 	lTL_Times[5] = {10000,10000,10000,10000,10000}
LONG	lINDEX_TIME[6] //1-5 = last values, 6 = running avg of all
LONG	lSTRING_TIME[6]
LONG	lSHELL_TIME[6]
LONG  lINDEX_AVG_CNTR = 0
LONG  lSTRING_AVG_CNTR = 0
LONG  lSHELL_AVG_CNTR = 0

INTEGER nSHELL_SELECT = 1

INTEGER nCNTR_STRING = 1
INTEGER nCNTR_INDEX = 1
INTEGER nCNTR_SHELL = 1
INTEGER nWORK_IN_PROGRESS = 0

DEFINE_FUNCTION fnInitPofiles() {
STACK_VAR INTEGER x;
STACK_VAR INTEGER y;
STACK_VAR INTEGER z;
STACK_VAR CHAR RNDM_NAME[20];

nWORK_IN_PROGRESS = 1
	FOR(x=1;x<=nMaxProfiles;x++)
	{
		z = RANDOM_NUMBER(15) + 5 //Determine Random length for Last Name 5 Char Minimum
		SET_LENGTH_ARRAY(RNDM_NAME,z)
		FOR(y=1;y<=z;y++)
			RNDM_NAME[y] = (RANDOM_NUMBER(26) + 65)
		sProfiles[x].LastName	= RNDM_NAME
	
		z = RANDOM_NUMBER(10) + 3 //Determine Random length for First Name 3 Char Minimum
		SET_LENGTH_ARRAY(RNDM_NAME,z)
		FOR(y=1;y<=z;y++)
			RNDM_NAME[y] = (RANDOM_NUMBER(26) + 65)
		sProfiles[x].FirstName= RNDM_NAME
		
		sProfiles[x].ID	= x
	}
nWORK_IN_PROGRESS = 0
}

DEFINE_FUNCTION fnSortByLastName_Index() {

  INTEGER 	x
  INTEGER 	y
  INTEGER 	tempID
  CHAR		tempLastName[32]
  CHAR		tempFirstName[32]
  INTEGER nPTR[nMaxProfiles]
  nWORK_IN_PROGRESS = 1	
	TIMELINE_CREATE(lTL_ID,lTL_Times,5,TIMELINE_RELATIVE,TIMELINE_REPEAT)
	
	FOR(x=1; x<=nMaxProfiles; x++)
		nPTR[x] = x;
		
   
  //bubble sort
  //bubble up the smaller names (alphabetically) by pushing the bigger names down
  FOR (x=1; x<nMaxProfiles; x++) {
    FOR (y=1; y<=nMaxProfiles-x; y++) {
			//if position y > position y+ 1 then swap
			IF ("sProfiles[nPTR[y]].LastName,sProfiles[nPTR[y]].FirstName" >
	       "sProfiles[nPTR[y+1]].LastName,sProfiles[nPTR[y+1]].FirstName") {
	 
				tempID 			= nPTR[y]	
				nPTR[y]			= nPTR[y+1]
				nPTR[y+1] 	=	tempID
	    
			}
		}
	}
	FOR(x=1;x<=nMaxProfiles;x++) {
		tempID = sProfiles[x].ID
		tempLastName = sProfiles[x].LastName
		tempFirstName = sProfiles[x].FirstName
		
		sProfiles[x].ID = sProfiles[nPTR[x]].ID
		sProfiles[x].LastName = sProfiles[nPTR[x]].LastName
		sProfiles[x].FirstName = sProfiles[nPTR[x]].FirstName
		
		sProfiles[nPTR[x]].ID = tempID
		sProfiles[nPTR[x]].LastName = tempLastName
		sProfiles[nPTR[x]].FirstName = tempFirstName
		
		y=x
		while(y<=nMaxProfiles AND nPTR[y] <> x)
			y++
		IF(y<=nMaxProfiles)
			nPTR[y] = nPTR[x]
	}
	
	TIMELINE_PAUSE(lTL_ID)
	lINDEX_TIME[nCNTR_INDEX] = TIMELINE_GET(lTL_ID)
	TIMELINE_KILL(lTL_ID)
	lINDEX_TIME[6] = ((lINDEX_TIME[6]*lINDEX_AVG_CNTR) + lINDEX_TIME[nCNTR_INDEX])/(lINDEX_AVG_CNTR + 1)
	lINDEX_AVG_CNTR++

	IF(nCNTR_INDEX == 5)
		nCNTR_INDEX = 1
	ELSE
		nCNTR_INDEX++
	nWORK_IN_PROGRESS = 0
}

DEFINE_FUNCTION fnSortByLastName_String() {

  INTEGER 	x
  INTEGER 	y
  INTEGER 	tempID
  CHAR		tempLastName[32]
  CHAR		tempFirstName[32]
	
	nWORK_IN_PROGRESS = 1
	TIMELINE_CREATE(lTL_ID,lTL_Times,5,TIMELINE_RELATIVE,TIMELINE_REPEAT)
      
   //bubble sort
   //bubble up the smaller names (alphabetically) by pushing the bigger names down
  FOR (x=1; x<nMaxProfiles; x++) {
    FOR (y=1; y<nMaxProfiles; y++) {
	 
	 //if position y > position y+ 1 then swap
			IF ("sProfiles[y].LastName,sProfiles[y].FirstName" >
	       "sProfiles[y+1].LastName,sProfiles[y+1].FirstName") {
	 
	    tempID 			= sProfiles[y+1].ID
	    tempLastName 		= sProfiles[y+1].LastName
	    tempFirstName 		= sProfiles[y+1].FirstName
	    
	    sProfiles[y+1].ID		= sProfiles[y].ID
	    sProfiles[y+1].LastName 	= sProfiles[y].LastName
	    sProfiles[y+1].FirstName 	= sProfiles[y].FirstName
	    
	    sProfiles[y].ID		= tempID
	    sProfiles[y].LastName	= tempLastName
	    sProfiles[y].FirstName	= tempFirstName
	    }
		}
	}
	TIMELINE_PAUSE(lTL_ID)
	lSTRING_TIME[nCNTR_STRING] = TIMELINE_GET(lTL_ID)
	TIMELINE_KILL(lTL_ID)
	lSTRING_TIME[6] = ((lSTRING_TIME[6]*lSTRING_AVG_CNTR) + lSTRING_TIME[nCNTR_STRING])/(lSTRING_AVG_CNTR + 1)
	lSTRING_AVG_CNTR++


	IF(nCNTR_STRING == 5)
		nCNTR_STRING = 1
	ELSE
		nCNTR_STRING++
  nWORK_IN_PROGRESS = 0	
}

DEFINE_CALL'ShellSort' { 
STACK_VAR INTEGER nLength;
STACK_VAR	INTEGER hSequenceLength;
STACK_VAR INTEGER i;
STACK_VAR INTEGER j;
STACK_VAR INTEGER k;
STACK_VAR INTEGER h;
STACK_VAR INTEGER x;
STACK_VAR INTEGER y;
STACK_VAR INTEGER 	tempID;
STACK_VAR CHAR		tempLastName[32];
STACK_VAR CHAR		tempFirstName[32];
STACK_VAR INTEGER nPTR[nMaxProfiles];
STACK_VAR INTEGER hSequence[40];

  nWORK_IN_PROGRESS = 1	
	SWITCH(nSHELL_SELECT)
	{
		CASE 1:
		{
			hSequence = NumColumns1
			hSequenceLength=LENGTH_ARRAY(NumColumns1);
		}
		CASE 2:
		{
			hSequence = NumColumns2
			hSequenceLength=LENGTH_ARRAY(NumColumns2);
		}
		CASE 3:
		{
			hSequence = NumColumns3
			hSequenceLength=LENGTH_ARRAY(NumColumns3);
		}
		CASE 4:
		{
			hSequence = NumColumns4
			hSequenceLength=LENGTH_ARRAY(NumColumns4);
		}
	}
	TIMELINE_CREATE(lTL_ID,lTL_Times,5,TIMELINE_RELATIVE,TIMELINE_REPEAT)
	
	FOR(x=1; x<=nMaxProfiles; x++)
		nPTR[x] = x;
	
	FOR(k=1;k<=hSequenceLength;k++) { 
		h=hSequence[k]	
		IF(h< (nMaxProfiles/2)) {
			FOR(i=h+1;i<nMaxProfiles;i++) { 
				j=i 
				WHILE((j>=h)AND("sProfiles[nPTR[j-h]].LastName,sProfiles[nPTR[j-h]].FirstName" >
						 "sProfiles[nPTR[j]].LastName,sProfiles[nPTR[j]].FirstName")) {
					tempID = nPTR[j]
					nPTR[j]=nPTR[j-h] 
					nPTR[j-h] = tempID
					
					j=j-h 
					} 
				
				 
			}
		}
	}

	FOR(x=1;x<=nMaxProfiles;x++) {
		tempID = sProfiles[x].ID
		tempLastName = sProfiles[x].LastName
		tempFirstName = sProfiles[x].FirstName
		
		sProfiles[x].ID = sProfiles[nPTR[x]].ID
		sProfiles[x].LastName = sProfiles[nPTR[x]].LastName
		sProfiles[x].FirstName = sProfiles[nPTR[x]].FirstName
		
		sProfiles[nPTR[x]].ID = tempID
		sProfiles[nPTR[x]].LastName = tempLastName
		sProfiles[nPTR[x]].FirstName = tempFirstName
		
		y=x
		while(y<=nMaxProfiles AND nPTR[y] <> x)
			y++
		IF(y<=nMaxProfiles)
			nPTR[y] = nPTR[x]
	}
	
	TIMELINE_PAUSE(lTL_ID)
	lSHELL_TIME[nCNTR_SHELL] = TIMELINE_GET(lTL_ID)
	TIMELINE_KILL(lTL_ID)
	lSHELL_TIME[6] = ((lSHELL_TIME[6]*lSHELL_AVG_CNTR) + lSHELL_TIME[nCNTR_SHELL])/(lSHELL_AVG_CNTR + 1)
	lSHELL_AVG_CNTR++

	IF(nCNTR_SHELL == 5)
		nCNTR_SHELL = 1
	ELSE
		nCNTR_SHELL++
	nWORK_IN_PROGRESS = 0


}


DEFINE_START

fnInitPofiles()

DEFINE_EVENT

BUTTON_EVENT[dvTP,1] {  //sort the profiles by last name

   PUSH: {
      fnSortByLastName_String()
   }
}

BUTTON_EVENT[dvTP,2] {  //reset profiles to original order

   PUSH: {
      fnInitPofiles()
   }
}
BUTTON_EVENT[dvTP,3] {  //sort the profiles by last name

   PUSH: {
      fnSortByLastName_Index()
   }
}
BUTTON_EVENT[dvTP,4] {  //sort the profiles by last name

   PUSH: {
      CALL 'ShellSort'
   }
}

You can use the debug window to change between the 4 different column number sets I have in the code if you want to play around with 4 different sets of numbers for testing purposes.

Have fun,
Jeff

DHawthorne · December 2007

The more advanced we are getting with our programming, the more then not-quite-really-multi-threaded nature of NetLinx is rearing it's head. A LONG_WHILE should, by all rights, just lock the thread running it until it times out, not the entire controller. Similarly, Recently had needed something to calculate a fractional exponent, and of course, there is no such function in NetLinx (nor Java ME, for that matter). I found an algorithm on java.net to approximate it, but it seriously impacted my NetLinx master ... one line of code freezing the entire master for a good 5-10 seconds. I optimized it a bit so it now only takes about a second ... but really, we need a good idle() function to give up processor ticks to other threads. We aren't just turning TV's on and off anymore, we are acquiring and handling data, and the language needs to expand accordingly ... and it does not seem Duet is fitting the bill as it ought to have

ericmedley · December 2007

DHawthorne wrote:

The more advanced we are getting with our programming, the more then not-quite-really-multi-threaded nature of NetLinx is rearing it's head. A LONG_WHILE should, by all rights, just lock the thread running it until it times out, not the entire controller. Similarly, Recently had needed something to calculate a fractional exponent, and of course, there is no such function in NetLinx (nor Java ME, for that matter). I found an algorithm on java.net to approximate it, but it seriously impacted my NetLinx master ... one line of code freezing the entire master for a good 5-10 seconds. I optimized it a bit so it now only takes about a second ... but really, we need a good idle() function to give up processor ticks to other threads. We aren't just turning TV's on and off anymore, we are acquiring and handling data, and the language needs to expand accordingly ... and it does not seem Duet is fitting the bill as it ought to have

Preach it brother! I'm running into these kind of issues as well. I also find myself avoiding the whole 'Java-think' in my programming as well because I just don't feel the NetLinx hardware/software model fits into strict object-oriented programming. Not that I think that's necessarily a bad thing. Object oreinted programming has a LOT of mental overhead and for a good chunk of what we do with Netlinx boxes I just don't think it's needed. However, for a lot of things that we are supposed to be 'in theory' able to do, the hardware/software tools just aren't there yet.

I'd still like to be able to make a decent simple web browser for the touch panels. But I can't.

Spire_Jeff · December 2007

Just some follow up. I was curious to see how much faster the 3100 is than the 3000, so I ran the benchmarks on a 3100 we have here. I ran each test 10 times to give me a fair average and here are the results:

|Test Type                |     NI3000      |    NI3100     |
|===========================================================|

|************************ Random Data **********************|
|-----------------------------------------------------------|
|Bubble Sort              |     23364ms     |     9226ms    |
|-----------------------------------------------------------|
|Bubble Sort Indexed      |     11976ms     |     4560ms    |
|-----------------------------------------------------------|
|Shell Sort (Pratt)       |      3380ms     |     1321ms    |
|-----------------------------------------------------------|
|Shell Sort(mhermanns)    |      2194ms     |      878ms    |
|===========================================================|


|********************** Presorted Data *********************|
|-----------------------------------------------------------|
|Bubble Sort              |     16880ms     |     6442ms    |
|-----------------------------------------------------------|
|Bubble Sort Indexed      |      9713ms     |     3753ms    |
|-----------------------------------------------------------|
|Shell Sort (Pratt)       |      1704ms     |      639ms    |
|-----------------------------------------------------------|
|Shell Sort(mhermanns)    |       536ms     |      207ms    |
|===========================================================|

Anyone know if any of the other processors are supposed to be faster or slower?

Jeff

a_riot42 · December 2007

ericmedley wrote:

Preach it brother! I'm running into these kind of issues as well. I also find myself avoiding the whole 'Java-think' in my programming as well because I just don't feel the NetLinx hardware/software model fits into strict object-oriented programming. Not that I think that's necessarily a bad thing. Object oreinted programming has a LOT of mental overhead and for a good chunk of what we do with Netlinx boxes I just don't think it's needed. However, for a lot of things that we are supposed to be 'in theory' able to do, the hardware/software tools just aren't there yet.

I'd still like to be able to make a decent simple web browser for the touch panels. But I can't.

Not undertanding this. Everyday I curse Netlinx for not being object oriented. Trying to create complex systems without being able to say, pass structures to modules, or use polymorphism or abstraction is just a huge drag, and would be hugely beneficial in this kind of work where there are many devices that do basically the same thing (power on , power off, play, stop, pause etc). I would like to be able to do this:

dvCD.play()
dvDVD.play()
dvIpod.play()

and have the right thing happen regardless of what the device is.

I also miss not being able to have functions that take variable arguments like Java or C++ like this:

define_function switch(integer input, integer output) {}

define_function switch(integer input[], integer output) {}

so that I don't have to rename the functions if the argument is slightly different.

If they had at least given us pointers then we would have a fighting chance, but no ponters either, sheesh.

Oh how I pine for OO.

Joe Hebert · December 2007

Duet

a_riot42 wrote:

I also miss not being able to have functions that take variable arguments like Java or C++ like this:

define_function switch(integer input, integer output) {}

define_function switch(integer input[], integer output) {}

so that I don't have to rename the functions if the argument is slightly different.

If they had at least given us pointers then we would have a fighting chance, but no ponters either, sheesh.

Oh how I pine for OO.

You can write in Java if you want. That's what DUET is all about. No?

a_riot42 · December 2007

I don't know, I typed System.out.println("Hello World") into my program and it wouldn't compile

Seriously, I started down the Duet route but realized that it would require AMX training to really understand how they set things up. Plus the Java IDE they make you use I don't like (Eclipsed). I have paid for my own Java IDE (Jetbrains) and can't use it for Duet which really burns me. I wish that they had set it up so that you could add Java code into a netlinx program by calling a lib function similar to calling native functions from Java.
Paul

Auser · December 2007

Spire_Jeff wrote:

... Anyone know if any of the other processors are supposed to be faster or slower?

Jeff

From memory, AMX suggest that the NIx100 series run code about three times faster than the NIx000's. From your figures it seems like the reality is closer to 2.5 times.

So of the currently available controllers, the 2100, 3100 and 4100's will run code about 2.5x faster than the 700's and 900's.

Merry Christmas peoples *<:-)

Sorting text alphabetically

Comments