Insertion Sort demo

[lemming]

Building on my previous Bubble Sort and Gnome Sort scripts, here is my implementation of Insertion Sort.

 

Like the previous scripts, this is a "pure" macro - no external programs, scripts or libraries are used. However, it will only work with Macro Express Pro, because it need arrays.

 

Insertion sort outperforms both Bubble Sort and Gnome sort, as predicted by complexity analysis.

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

 

This implementation is based on my understanding of the Insertion Sort algorithm, as explained by xoaxdotnet - http://xoax.net/comp/sci/algorithms/Lesson2.php

 

Other references: http://en.wikipedia.org/wiki/Insertion_sort

 

Benchmarks on an old machine running Win XP (P4 3GHz Northwood, about 5 years old):

 

Insertion Sort

100 elements = about 0.6 sec

250 elements = about 3.5 sec

500 elements = about 14.8 sec

 

Bubble Sort

100 elements = about 1.0 sec

250 elements = about 5.7 sec

500 elements = about 24.7 sec

 

Gnome Sort

100 elements = about 1.2 sec

250 elements = about 6.6 sec

500 elements = about 30.3 sec

 

Downloads and installation guide are in the next posting.

 

-Lemming

[lemming]

Installation guide for Insertion Sort demo

 

1. Download the sort scripts (.mex) from the Macro Express Forums, i.e. from this page.

 

2. Download the test data (.txt) from Macro Express Forums. Take note of the file location for later use.

 

3. Import the sort scripts from the downloaded .mex file into Macro Express Pro. Click File->Import->Import Macros… In this example, the file is Insertion Sort demo (strings) v 0.9.1 MEP.mex. Click Open. In the Import Macros window, click Select All and click OK.

 

4. You will now need to modify the scripts to work on your system. Basically, change the locations for the input and output files. In the Macro Express Pro Explorer window, double-click on the sort script to open it in the Script Editor window. Change the lines that start with “Variable Set String %SourceFile%” and “Variable Set String %ResultsFile%”. Just change the path to where the text source file is on your system. Click OK when you’re done and close the Script Editor window.

 

5. You can now run the script. There is no hotkey; just click on the script to select it, then click the “play” button in the Macro Express Pro Explorer window. Open “sorted listed.txt” to check the results.

 

Other things to note:

 

- The sorts are in ascending order (A to Z)

- Hint for Win Vista/Win 7 users – don’t save input and output files to C:\

- The default input file is "Top xx movies.txt". Change as needed.

- The default output file name is "sorted.txt". Change as needed.

- Any existing output file with the same name is deleted every time the scripts are run.

- There is very little error-handling

- The array size must be known beforehand. I don't know how to assign it dynamically. To change the array size, go to Script Editor window->Variables->Text Variables

- I haven't tested it with numbers (numerical sorting), but that should be trivial to implement.

Insertion Sort demo (strings) v 0.9.1 MEP.mex

Top 100 movies.txt

Top 250 movies.txt

Top 500 movies.txt

Top 1000 movies.txt

[terrypin]

Thanks for sharing that and presenting it so well.

 

I've installed and tested the macros, but they're incredibly slow, yes?

 

Using my text editor (TextPad), the 1000 item file took only milliseconds for the sort. But the macro took 3.5 s for the 500 and over 26 s for the 1000.

 

The 100 macro ran successfully.

The 250 and 500 macros gave error messages at lines 84 and 83 respectively: "The file could not be opened.

I/O error 105"

The 1000 macro would not finish (had to be terminated manually).

 

Change the lines that start with ... “Variable Set String %ResourceFile%”.

 

I think that should be

Change the lines that start with ... “Variable Set String %ResultsFile%”.

 

--

Terry, East Grinstead, UK

[lemming]

Hi Terry, thanks for pointing out the typo, and thanks for testing the scripts. Yes, I would agree they are slow. I believe it is a limitation of MEP, and not my coding ;-) I am guessing that ME and MEP are slow at comparisons, which would really impact comparison sort algorithms. Bubble, Gnome and Insertion Sort are all comparison sorts and they have to compare items thousands of times a second.

 

Anyway, I wrote the scripts mainly as a proof-of-concept and to improve my understanding of sorting algorithms. Just goes to show that once you have understood an algorithm, you can implement it even with "rudimentary" script languages.

 

For heavy-duty sorting, I would recommend using TextPad like you did, or Windows' built-in sort.exe. Both are faster than my code by many orders of magnitude.

 

I'm actually finishing up a Comb Sort script, but am still not happy with its performance. It is faster than Insertion Sort (about 50% faster), but it is also a comparison sort, so I don't think I can optimize it any more.

 

As for the error messages, are the paths/filenames are correct in your script? Also, if you're using Vista/Win 7, the OS will not let scripts access certain folders, e.g. C:\ is usually off-limits. All four scripts are almost identical. The only difference is the %SourceFile% they point to, and the size of the array for sorting.

 

- Lemming

 

 

Thanks for sharing that and presenting it so well.

 

I've installed and tested the macros, but they're incredibly slow, yes?

 

Using my text editor (TextPad), the 1000 item file took only milliseconds for the sort. But the macro took 3.5 s for the 500 and over 26 s for the 1000.

 

The 100 macro ran successfully.

The 250 and 500 macros gave error messages at lines 84 and 83 respectively: "The file could not be opened.

I/O error 105"

The 1000 macro would not finish (had to be terminated manually).

 

 

 

I think that should be

Change the lines that start with ... “Variable Set String %ResultsFile%”.

 

--

Terry, East Grinstead, UK