How best to sort an array

[Cory]

I need to sort some lists not greater than a thousand or so and in this example I will be using arrays but I don't think that's important. But for the sake of this thread think arrays.

 

I could use a bubble sort but it is terribly inefficient so I was hoping to find a better method. However most of the algorithms I see online that are efficient become complex really quick. Also it seems like they mostly are limited to one array. Can any one recommend a simple method I could use in MEP?

 

I had my own idea before my research but can not find it anywhere. It's similar to an Insertion Sort but might be more efficient. The analogy of an Insertion Sort how a human might sort a deck of cards. The person starts with one deck and takes the top card in hand. They then pull another card and if it is greater than the card in hand it goes to the back else front. Subsequent cards get compared to every card until it's place is found where the one in front is smaller and the one behind is larger and it's inserted there. I like it because it's conceptually simple and way more efficient than a bubble sort. But there is one aspect I don't like. In order to do this in an array one takes the next value and then starts from the highest element in the array and as it moves down thru the elements moves each one up an element number until it's place is found so that can be a lot of operations.

 

Now my idea was to have two arrays. In the first one we take one of the value and compare it to ever element in the list that is less than or equal to it. This value is it's element in the second array and I copy it there. Now I do this for every element in the first array. The untidy bit is if I have duplicate items in the first list. To address this I reckon before I copy to the new array I could first see if that slot is taken. If it is decrement the element number and repeat until an empty slot is found.

 

My biggest wonderment here is if my method is really any more efficient. Reflexively it could be but after some consideration of the counting I'm wondering if it really is. Do you think my method is any better?

 

After working on this problem awhile I think for the job at hand I will be using an insert sort but the main reason for that is that since it doesn't need to know the entire set in advance I can use it on the fly. So if I am grabbing variables from some source I can insert sort them as they are gathered instead of having to create an unsorted list first. Also I can embed some comparisons and other tests for things like duplicates in line and for that it would actually be more efficient because the list is already sorted at any point in time so I can quit when a hit is registered.

[stevecasper]

I don't think this will help at all, but nobody else has taken a stab, so here's my response:

 

Imagine a guy whose idea of climbing a mountain consists of sitting in his Laz-E-Boy with a Dew in one hand, the other hand sifting through the crumbs at the bottom of an all-but-empty bag of potato chips, watching an action movie with a spy/ninja on skiis trying to escape from the badguys (who are, of course, on Ski Doo snow-mobiles), in the alps.

 

Now imagine a famous mountain climber - one who has scaled all the 8-thousanders a couple of times each.

 

Now, imagine this experienced climber asking the couch-potato for his opinion about which route is faster, or more enjoyable to climb, South Col or North Col.

 

I think the couch-potato would be better qualified to answer that question than I would be to answer any Macro Express situations that are giving Cory trouble.

 

Maybe Floyd is around?

[terrypin]

Cory,

 

The various sort techniques are outside my skill level. But if I wanted to sort a list of a thousand or so text strings I think my first move would be to open them as a text file in my text editor (TextPad in my case), and use its handy, fast Sort facility. I just tried it with a list of 1200 or so and the result was effectively instant.

 

So maybe I'd do exactly that in the ME Pro macro.

 

--

Terry, East Grinstead, UK

[kevin]

You could use Windows' built in sort array:

 
// Initialize file paths
Variable Set String %InFile% to "%Temp%\InFile.tmp"
Variable Set String %OutFile% to "%Temp%\OutFile.tmp"

Join String %BigArray%[1..2000] with "," into %BigString% // Copy array to a single string. Each element is separated by a comma
Variable Modify String: Save %BigString% to "%InFile%" // Save the string to a file
Program Launch: "sort.exe" (Normal)
Parameters: %InFile% /O%OutFile% // Use Windows' sort routine to sort the content of the file

Variable Set String set %BigString% to the contents of %OutFile% // Read sorted string
Split String "%BigString%" on "," into %BigArray%, starting at 1

This uses some file I/O and consequently may not be as fast as a sort performed directly in memory. However, it may be faster than a macro with loops and a lot of macro commands.

 

Here is my untested sample macro:

<COMMENT/>
<COMMENT Value="Initialize file paths"/>
<VARIABLE SET STRING Option="\x00" Destination="%InFile%" Value="%Temp%\\InFile.tmp"/>
<VARIABLE SET STRING Option="\x00" Destination="%OutFile%" Value="%Temp%\\OutFile.tmp"/>
<COMMENT/>
<JOIN STRING Source="%BigArray%" StartIndex="1" EndIndex="2000" JoinWith="," Destination="%BigString%" _COMMENT="Copy array to a single string. Each element is separated by a comma"/>
<VARIABLE MODIFY STRING Option="\x11" Destination="%BigString%" Filename="%InFile%" CRLF="FALSE" _COMMENT="Save the string to a file"/>
<PROGRAM LAUNCH Path="sort.exe" Mode="\x00" Parameters="%InFile% /O%OutFile%" Default_Path="TRUE" Wait="1" Get_Console="FALSE" _COMMENT="Use Windows' sort routine to sort the content of the file"/>
<COMMENT/>
<VARIABLE SET STRING Option="\x03" Destination="%BigString%" Filename="%OutFile%" Strip="FALSE" _COMMENT="Read sorted string"/>
<SPLIT STRING Source="%BigString%" SplitChar="," Dest="%BigArray%" Index="1"/>

[Cory]

I had no idea that existed. Is Sort.exe in all versions of Windows?

[kevin]

I had no idea that existed. Is Sort.exe in all versions of Windows?

Yes, so far. I can't vouch for Windows 7 yet.

[Cory]

Steve that's a beautiful visualization! Except I was thinking Cheetos because they leave an embarrassing stain on the hands and front of the worn out old tanker Teeshirt.

[terrypin]

I had no idea that existed. Is Sort.exe in all versions of Windows?

 

It's usually at C:\WINDOWS\system32\sort.exe. Entering sort /? at a Command prompt gets you the specs.

 

--

Terry, East Grinstead, UK

[stevecasper]

Steve that's a beautiful visualization! Except I was thinking Cheetos because they leave an embarrassing stain on the hands and front of the worn out old tanker Teeshirt.

LOL Yes, Cheetos would definitely fit better

[paul]

I don't know if this is of any help, but if you go to VbNet and search on the word Sort, items 1, 2, 3, 5 and 7 may be of interest (lots of VB6 code which you may be able to plough through).

 

There are also many free sort utilities available on the web, some of which allow you to sort on particular columns. Thus you would create a file of data, sort it with one utility or another, then read back in to ME the contents of your sorted file. Writing sort routines can be quite challenging, and I'm not sure MEP is the right vehicle to accomplish this.

[Cory]

Point is well taken. This post was inspired by one macro I need to write but was supposed to be a general question but after due consideration I think that the answer contains an "It depends". In the cases where there are large amounts of data using other tools would be the best tack but for smaller sets I think using the insert method, especially when running on the fly.

[lemming]

LOL. I actually did write a bubble sort macro for Macex ver 3.5x a few years ago

 

http://pgmacros.invisionzone.com/index.php?showtopic=918

 

It wasn't fast, but I suspect it was because I had to create an array for ver 3.5x.

 

http://pgmacros.invisionzone.com/index.php...9&hl=bubble

 

I have not tried Macex Pro, and in fact, I no longer use Macex. So perhaps someone else could rewrite it to use the new arrays supported by Macex Pro. I'm sure it'd work a lot faster than my macro, which used a kludgy array.

[Cory]

I actually have a sorter now that works well. It's an insert sort so if I want to sort an existing array it requires creating another array but I find that most times I'm accumulating values from some source and can sort as I find them. It simply starts at 1 and goes until it's greater than or equal to the evaluated one and then bumps each subsequent one up. Optionally it can discard an duplicate value which leaves a unique list. Not high tech but it works well and more importantly is conceptually simple.