Jump to content
Macro Express Forums

Bubble Sort Using Only Macro Express


Recommended Posts

I was looking for some sort of sorting capability in Macex and there isn't. The closest thing is a macro which generates and calls a VBS script, as discussed here.

 

So here is my implementation of the classic Bubble Sort algorithm using Macex alone (see next posting). Sure, bubble sort is considered a "n00b" algorithm, but I say a bubble sort is better than no sort at all.

 

This is a "pure" macro - no external programs, scripts or libraries are used. I didn't even use dynamic variables! (i.e. Run Macro in Variable). I did use "Variable Evaluation Level" initially, but even that is not required now.

 

Here some sample data files I used for testing (included with this posting).

 

How fast is it? Here are some benchmarks conducted on my machine which has P4 2.8GHz proc and 1GB of RAM:

 

50 elements = less than 1 sec (too fast to measure)

100 elements = about 5 sec

200 elements = about 17 sec

500 elements = about 1 min 3 secs

 

In any case, you can easily conduct your own benchmarking because I've included code for reporting the start and end time.

bubblesort_test_files.zip

Link to comment
Share on other sites

Bubble Sort - Text

 

WHAT IT DOES:

Implementation of the classic Bubble Sort algorithm in Macex.

 

TO INSTALL:

 

Download Bubble Sort - Text v1.0.1b.mex

In Macro Explorer, choose File->Import->Import Macros. Choose Bubble Sort - Text

and place it into the category of your choice.

 

TO USE:

No hotkey has been defined for the macro. You can either run it directly from the Macro Explorer, or you can define your own hotkey to run it. The script read records from a text file (default is C:\unsorted list.txt).

It can handle either a Comma Delimited text file (every field in each record is separated by a comma) or a Basic text file (each line of the text file is considered as a single entry to be read in).

 

HOW IT WORKS:

 

The Bubble Sort algorithm is well known, and is often taught to programming students. Here's a good description from

http://en.wikipedia.org/wiki/Bubble_sort

 

Bubble sort, also known as exchange sort, is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time, swapping these two items if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top (i.e. head) of the list via the swaps. In more detail, the bubble sort algorithm works as follows:

 

1. Compare adjacent elements. If the first is greater than the second, swap them.

2. Do this for each pair of adjacent elements, starting with the first two and ending with the last two. At this point the last element should be the greatest.

3. Repeat the steps for all elements except the last one.

4. Keep repeating for one fewer element each time, until you have no more pairs to compare. (Alternatively, keep repeating until no swaps are needed.)

 

I had to create my own array routine to get pass Macex's 99-variable limit, and to allow for variable manipulation in a loop. In fact, the bulk of this macro deals with array handling. Details about the array are available separately in the Macro Express 3.x forum in the thread titled "My new array technique is unstoppable!"

http://pgmacros.com/community/index.php?showforum=2

 

LIMITATIONS:

 

The current limitations in this macro are:

1) Does not handle quoted commas.

2) Sorts everything as text.

3) Does not handle blank records (they are just removed).

4) Comparisons are case-insensitive (can be changed in the macro).

5) Maximum text file size has been set at 10KB and the maximum number of elements (or records) has been set at 500, though though the macro can address up to 999 elements. These can be changed in the macro.

 

The limitations are discussed in more detail in another posting.

 

REQUIREMENTS:

 

No "advanced" methods such as "Variable Evaluation Level" or "Run Macro in Variable" are used in this macro, so it should work with Macro Express v 3.5 or later. All testing was done with version 3.5e (3.5.5.1) of Macex. I don't have access to any older versions. Your version of Macex must at least support these commands - "Get Position of Text in a Text Variable", "Variable Set String from File", and "Repeat Options->Place Counter in Variable"

 

Submitted by:

Chan Lee Meng

(Lemming)

http://star-techcentral.com/

email: Not provided due to excessive spam. Contact me using the forum message system instead.

Bubble_Sort___Text_v1.0.1b.mex

Link to comment
Share on other sites

LIMITATIONS:

 

The current limitations in this macro are:

1) Does not handle quoted commas.

2) Sorts everything as text.

3) Does not handle blank records (they are just removed).

4) Comparisons are case-insensitive (can be changed in the macro).

5) Maximum text file size has been set at 10KB and the maximum number of elements (or records) has been set at 500.

 

More details:

 

1) Does not handle quoted commas which are used by certain types of csv files. For example, if you have the following records -

Paris,New York,Rome,"Rome,Georgia",Miami

The array will be created containing these elements:

Element 1 = Paris

Element 2 = New York

Element 3 = Rome

Element 4 = "Rome,

Element 5 = Georgia"

Element 6 = Miami

 

2) Sorts everything as text. The numbers 1 to 10 would be sorted as 1,10,2,3,4,5,6,7,8,9 because they are not "seen" as integers. With a bit more coding (mainly text->integer conversion, and back again), you can make it sort integers properly. As they often say in those Math textbooks, this is left as an exercise for the reader ;)

 

3) Does not handle blank records. My macro first removes any duplicate commas and CR/LFs, that is, it replaces ,, with ,

These are sometimes used to indicate a blank or empty record. If you need these to be included with your final sort, replace ,, with something like ,(blank),

 

4) You should also note that comparisons are case-insensitive, resulting in elements sorted like this: Adam,apple,Eve,garden,Satan,snake

By default, the comparisons are made using the If variable > (more than) command with the "Ignore Case" option selected. If you want case-sensitive sorting, just unselect that option, and your elements would be sorted like this:

Adam,Eve,Satan,apple,garden,snake

 

5) Text file and element limits have been set. The macro can actually address up to 999 elements, but I have set the limit to 500. Sorting more than that would be slow and may appear to hang your PC. You can up the max values, but do so at your own risk.

Link to comment
Share on other sites

  • 3 weeks later...

Chan Lee -

 

Looks nice. Looks intense. And from a programming-task point-of-view, not for the feint-of-heart. :unsure:

 

You are correct: "a bubble sort is better than no sort at all". Congratulations! We will be running some tests on it soon. Thanks for good documentation, too!

Link to comment
Share on other sites

Chan Lee -

 

Looks nice. Looks intense. And from a programming-task point-of-view, not for the feint-of-heart. :unsure:

[...]

 

Hi Joe et al., my surname is Chan, so you can call me Lee Meng or Lemming (but not Lee). That's the name convention for my side of the world.

 

Anyway, yes, the code does seem complicated, but I had to work with the limitations of Macex.

 

To help out other users, I've created a slightly newer version of the Bubble Sort macro which is split into three macros so that it is (slightly) easier to understand.

 

The main macro (top level macro) is called Bubble Sort - [MAIN] v1.0.1c , and it will call Bubble Sort - Create Array v1.0.1c and Bubble Sort - Sort Routine v1.0.1c which are self-descriptive.

 

The main macro uses the Macro Run command to call the other two. To use these group of macros, you need to import all of them into the same category (same folder).

 

You may also need to point the Macro Run command to the correct location of Bubble Sort - Create Array v1.0.1c and Bubble Sort - Sort Routine v1.0.1c. Pls remove earlier versions of the Bubble sort macros.

 

The performance for v1.0.1c is the same as v1.0.1b, as are its limitations.

 

I'm already working on a faster sort routine, and will probably do a partial implementation of

Merge Sort which would be more efficient than Bubble Sort.

Bubble_Sort_v1.0.1c.mex

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

×
×
  • Create New...