Sorting lines of code - an IDE future add on?

[Andy]

Thought you might like this little one.

I am at times a bit lazy when I'm adding in lines of code, say DECLARE EXTERN.... lines.

What I mean by that is I'm more concerned about adding in functions than I am placing them in alphabetical order - which looks better when you share code.

Take a look at this example...

Code Select Expand

declare extern RegSetValue(Key as string,Value as string,opt ValueName as string),int
declare extern RegSetESValue(Key as string,Value as string,opt ValueName as string,lns as int),int
declare extern RegSetDWValue(Key as string,Value as int,opt ValueName as string),int
declare extern RegCreateKey(Key as string),int
declare extern RegDeleteKey(Key as string),int

You can see they are not in alphabetical order, and I don't want to spend a lot of time manually sorting say 60 lines of code myself.

This little program will take lines of code that you paste to the clipboard, sort them, and send the sorted code back to the clipboard.

You can then delete the unsorted code and paste the new sorted code back in.

How to:

In your IDE editor,
1. open the CopyFrom.iwb file.
2. Select all the lines of code.
3. Copy them to the clipboard.
4. Compile and run Sortclipboard.iwb
5. Wait a few seconds while the sort is done and for the window to appear - it will close again after 2 seconds.

When the program ends, open up a blank iwb file and paste in the sorted code - simple.

Maybe something like this could be added into a later edition of the IDE?

BTW, I've not tidied up the code, it's just an idea for an add-on?

Anyway, hope you like this idea.

Andy.

[Andy]

I've updated the program.

I noticed that you might have blank lines in between lines of code you are pasting, also lines might be indented with spaces / tabs which caused a sorting error.

Code Select Expand

declare extern GetRoot(Key as string),UInt
declare extern RegCreateKeyHandle(Key as string),Uint
declare extern RegCreateTempKey(Key as string),int
declare extern RegGetValue(Key as string,opt ValueName as string),string
declare extern RegGetValueA(Key as string,opt ValueName as string),string
declare extern RegGetDWValue(Key as string,opt ValueName as string),string
declare extern RegGetEntryType(Key as string,opt ValueName as string),INT
        Declare extern RegDeleteValue(Key as string,ValueName as string),string
declare extern RegSetValue(Key as string,Value as string,opt ValueName as string),int
declare extern RegSetESValue(Key as string,Value as string,opt ValueName as string,lns as int),int
declare extern RegSetDWValue(Key as string,Value as int,opt ValueName as string),int
declare extern RegCreateKey(Key as string),int
declare extern RegDeleteKey(Key as string),int

declare extern RegEnumKey(STRING Key,INT Index),STRING
declare extern RegEnumEntryName(STRING Key,INT Index),string






declare extern RegCountSubKeys(STRING Key),INT
declare extern RegCountEntries(STRING Key),INT
declare extern RegDeleteAll(Key as string),int
declare extern RegDeleteSubKeys(Key as string),int
declare extern RegDummyDel(Key as string),string
declare extern RegGetMSValue(Key As istring, ValueName As iString),string 'Multi String

declare extern RegGetMSValueStr(Key As istring, ValueName As iString),string 'Multi String
declare extern RegSetMSValue(Key as string,Value as istring,opt ValueName as string,lns as int),int
declare extern RegGetBinValue(Key As string, ValueName As String),string 'Binary
declare extern RegSetBinValue(Key as string,lns as int,Value as Istring,opt ValueName as string),int
declare extern RegCopyKey(Key as String,ToKey as string),int
declare extern RegRenameKey(string mykey,string newkey),int
declare extern RegKeyExists(Key as string),int
declare extern RegCountAllSubKeys(Key as string),int
declare extern RegGetQWValue(Key as string,opt ValueName as string),uint64
declare extern RegSetQWValue(Key as string,Value as uint64,opt ValueName as string),int
declare extern RegGetDWValueU32(Key as string,opt ValueName as string),uint64 'DWord Value
declare extern RegSetNoneValue(Key as string,lns as int,Value as istring,opt ValueName as string),int
declare extern RegSetResourceValue(Key as string,lns as int,Value as istring,opt ValueName as string),int
declare extern RegSetResourceDescriptorValue(Key as string,lns as int,Value as istring,opt ValueName as string),int
declare extern RegExportKey(mykey as string,RegFileName as string,opt RegExportSort as int),int
declare extern RegGetQWValueHex(Key as string,opt ValueName as string),string
declare extern RegGetResList(Key As istring, ValueName As iString),string
declare extern RegSetResListValue(Key as string,lns as int,Value as istring,opt ValueName as string),int
declare extern RegGetFullResDesc(Key As istring, ValueName As iString),string 'Full Resource Descriptor
declare extern RegSetFullResDescValue(Key as string,lns as int,Value as istring,opt ValueName as string),int
declare extern RegGetBinValueAsc(Key As istring, ValueName As iString),string 'Binary
declare extern RegGetType(Key as string,opt ValueName as string),int
declare extern RegGetName(Key as string,opt ValueName as string),string
declare extern RegGetQWValueU64(Key as string,opt ValueName as string),uint64 'QWord Value
declare extern RegRead(Key as string,opt ValueName as string),int
declare extern RegWrite(Key as string,opt ValueName as string),int
declare extern RegDeleteSubs(Key as String,opt SubKey as string),int
declare extern RegRenKey(Key as String,NewName as string),uint
declare extern RegGetAccessFull(Key as String),int
declare extern RegGetAccessRead(Key as String),int
declare extern RegLoadKey(UnameIn as string,UnamePath as string),uint
declare extern RegUnLoadKey(UnameIn as string),uint
declare extern RegKeyModified(STRING Key),string
declare extern RegGetDataSize(Key as string,opt ValueName as string),int
declare extern RegEntryExists(Key as string,opt ValueName as string),int
declare extern MyBase(string Stringin),int
declare extern ToBase(intValue As Int,Base As Int),String
declare extern RegRn(),int
declare extern RegRoot(Key as String),int



So, attached is the new version that ignores these blank lines, spaces at the start of a line and tabs.

The new sorted and pasted code is now nice and in order.

Code Select Expand

declare extern GetRoot(Key as string),UInt
declare extern MyBase(string Stringin),int
declare extern RegCopyKey(Key as String,ToKey as string),int
declare extern RegCountAllSubKeys(Key as string),int
declare extern RegCountEntries(STRING Key),INT
declare extern RegCountSubKeys(STRING Key),INT
declare extern RegCreateKey(Key as string),int
declare extern RegCreateKeyHandle(Key as string),Uint
declare extern RegCreateTempKey(Key as string),int
declare extern RegDeleteAll(Key as string),int
declare extern RegDeleteKey(Key as string),int
declare extern RegDeleteSubKeys(Key as string),int
declare extern RegDeleteSubs(Key as String,opt SubKey as string),int
Declare extern RegDeleteValue(Key as string,ValueName as string),string
declare extern RegDummyDel(Key as string),string
declare extern RegEntryExists(Key as string,opt ValueName as string),int
declare extern RegEnumEntryName(STRING Key,INT Index),string
declare extern RegEnumKey(STRING Key,INT Index),STRING
declare extern RegExportKey(mykey as string,RegFileName as string,opt RegExportSort as int),int
declare extern RegGetAccessFull(Key as String),int
declare extern RegGetAccessRead(Key as String),int
declare extern RegGetBinValue(Key As string, ValueName As String),string 'Binary
declare extern RegGetBinValueAsc(Key As istring, ValueName As iString),string 'Binary
declare extern RegGetDataSize(Key as string,opt ValueName as string),int
declare extern RegGetDWValue(Key as string,opt ValueName as string),string
declare extern RegGetDWValueU32(Key as string,opt ValueName as string),uint64 'DWord Value
declare extern RegGetEntryType(Key as string,opt ValueName as string),INT
declare extern RegGetFullResDesc(Key As istring, ValueName As iString),string 'Full Resource Descriptor
declare extern RegGetMSValue(Key As istring, ValueName As iString),string 'Multi String
declare extern RegGetMSValueStr(Key As istring, ValueName As iString),string 'Multi String
declare extern RegGetName(Key as string,opt ValueName as string),string
declare extern RegGetQWValue(Key as string,opt ValueName as string),uint64
declare extern RegGetQWValueHex(Key as string,opt ValueName as string),string
declare extern RegGetQWValueU64(Key as string,opt ValueName as string),uint64 'QWord Value
declare extern RegGetResList(Key As istring, ValueName As iString),string
declare extern RegGetType(Key as string,opt ValueName as string),int
declare extern RegGetValue(Key as string,opt ValueName as string),string
declare extern RegGetValueA(Key as string,opt ValueName as string),string
declare extern RegKeyExists(Key as string),int
declare extern RegKeyModified(STRING Key),string
declare extern RegLoadKey(UnameIn as string,UnamePath as string),uint
declare extern RegRead(Key as string,opt ValueName as string),int
declare extern RegRenameKey(string mykey,string newkey),int
declare extern RegRenKey(Key as String,NewName as string),uint
declare extern RegRn(),int
declare extern RegRoot(Key as String),int
declare extern RegSetBinValue(Key as string,lns as int,Value as Istring,opt ValueName as string),int
declare extern RegSetDWValue(Key as string,Value as int,opt ValueName as string),int
declare extern RegSetESValue(Key as string,Value as string,opt ValueName as string,lns as int),int
declare extern RegSetFullResDescValue(Key as string,lns as int,Value as istring,opt ValueName as string),int
declare extern RegSetMSValue(Key as string,Value as istring,opt ValueName as string,lns as int),int
declare extern RegSetNoneValue(Key as string,lns as int,Value as istring,opt ValueName as string),int
declare extern RegSetQWValue(Key as string,Value as uint64,opt ValueName as string),int
declare extern RegSetResListValue(Key as string,lns as int,Value as istring,opt ValueName as string),int
declare extern RegSetResourceDescriptorValue(Key as string,lns as int,Value as istring,opt ValueName as string),int
declare extern RegSetResourceValue(Key as string,lns as int,Value as istring,opt ValueName as string),int
declare extern RegSetValue(Key as string,Value as string,opt ValueName as string),int
declare extern RegUnLoadKey(UnameIn as string),uint
declare extern RegWrite(Key as string,opt ValueName as string),int
declare extern ToBase(intValue As Int,Base As Int),String

Andy.

[Andy]

This simple bubble sort program can be optimised.

Before I tried this I took some readings e.g. loops, time taken etc, this is what I found:

1. The program was looping 17,414 times to make 43 swaps and on average took around 600 milliseconds to complete the sort. 

2. Although the sort was complete, the looping process was still continuing until all loops had finished.

So this is what I did:

I counted how many times through the process there was NO swapping.  If you have 17 items to swap and no swapping occurred 17 times in a row then the sorting must be finished.  Once I had that idea it was just a case of breaking out of the for / next loops.

Now when I take readings from this optimised sort I find the following:

1. The program loops only 3153 times instead of 17,414.
2. The time taken is approximately half the time - around 300 milliseconds.

The code that improves the sort is as follows:

If a swap occurs, set the number of no changes back to zero

Code Select Expand

if doswap = 1
   swap = swap + 1
   lswap = swap
   NoChange = 0
   breakfor
endif

Here we are storing the latest swap number in a variable called lswap.

Now as we go through the array list of 17 entries, if lswap does not change we count the number of no changes. If no swaps occur 17 times in a row the sort is done, we just need to jump out of those for / next loops.

Code Select Expand

if lswap = swap
   NoChange ++
   if NoChange = count 'After 17 compares, nothing changed - so end the sort!
   breakfor
   endif
endif

See attached.


 

[Brian]

Andy,

Just tested your code. It took 43 swaps, looped through 3153 times, and took 125 milliseconds
on my PC - not bad!

Brian

[Andy]

Thanks Brian!

I'm displaying registry entries in alphabetical order, and I came across one key that had 153 entries in it. 

It was taking around 6 seconds (on my PC) to sort them alphabetically before displaying them.

I've managed to cut that down to around 3 seconds - I'm sure it would be much faster on your PC!!

Thanks again for trying the code.

[ckoehn]

Andy,

Can you tell me why this wouldn't work?

Later,
Clint

[Brian]

Clint,

Are you asking if your code shouldn't work? Because it appears to work for me!

43 swaps, 9 loop throughs and, wait for it - 0 milliseconds. Blimey!

Brian

[ckoehn]

I was just curious if there was something he was checking for that I wasn't.  IWBASIC does compare strings.  If he needed to strip characters off the front I can make code for that too. 

Later,
Clint

[ckoehn]

I didn't comment my code.  Sort of self explanatory except for a[0].  I just used that as a temporary variable since he wasn't using that element of the array.

[Andy]

Clint,

That's outstanding! didn't know you could compare strings like numbers.

The 153 entries are being sorted in a fraction of a second even on my PC - what's the name of the sort? do you know?

Hoped someone would come up with something much faster - thanks clint!!!

[ckoehn]

It is just a simple bubble sort.  It compares current entry with next entry and swaps if next is bigger.  It has to take one pass doing no swaps before it knows it is finished.

[ckoehn]

This could help it slightly.  On some sorts it would take 1 less pass. On large sorts it would make a difference.  If my logic isn't right let me know.  I'm still claiming chemo brain. 

Code Select Expand

swap=0

int change ' I like to define my variables this way, less typing
STRING s_tmp

do
change=0
loops++
for x=1 to count-1
if a[x]>a[x+1]
s_tmp=a[x+1]
a[x+1]=a[x]
a[x]=s_tmp
swap++
change++ 'count how many changes
endif
next x
until change<2 'if there is none or only one change, it should be finished.
'because all "big" entries are floated to the top nessesitating
'many changes (i hope I'm thinking right). This could make it take
'one less pass.



Later,
Clint

[Brian]

I was watching a science programme on BBC4 the other night, and they were talking about algorithms, and how they ruled the world. Basically, everything would stop if we didn't have them! They were explaining the algorithms that ran huge warehouses, picking and stocktaking, and also the landings and takeoffs at Heathrow are also managed with algorithms

Anyway, they started with a simple bubble sort algorithm, and I understood that. As Clint said, it compares pairs, sorting out which one is the lower or higher, then arranging them in order

Then they explained that there was a faster one, called a merge sort. This basically splits your total amount of sorts, say, 100 numbers are split into two pairs of 50, each is sorted concurrently, and then merged together. Started losing me then!

They mentioned other types of sorts, and my eyes were glazing over . . .

Brian

[Egil]

Brian, was this the BBC program you saw?  https://www.youtube.com/watch?v=gOKVwRIyWdg

Here is another one explained visually: https://www.youtube.com/watch?v=kPRA0W1kECg



Egil

[Brian]

Egil,

To the first one - yes

I've just watched the second video - quite fascinating to see the sorting in action, but still couldn't figure out which one was the fastest. Radix (LSG) Sort was very fast. Should have been a listing at the end giving timings. I reckon Bubble Sort is up there with the best

Brian

[ckoehn]

Brian,

You mean something like this..

Code Select Expand


/*

An example of how to sort arrys into alphanumerical order.
To do this I calculate the ASCII value of each alphanumeric character
and string of characters.

*/
$include "windowssdk.inc"

DEF a[255]:string
DEF loops:int
def x1,x2:uint

'The array we want to sort
a[1] =  "declare extern GetRoot(Key as string),UInt"
a[2] =  "declare extern RegCreateKeyHandle(Key as string),Uint"
a[3] =  "declare extern MyBase(string Stringin),int"
a[4] =  "declare extern RegDeleteValue(Key as string,ValueName as string),string"
a[5] =  "declare extern RegCreateKey(Key as string),int"
a[6] =  "declare extern RegDeleteKey(Key as string),int"
a[7] =  "declare extern RegSetBinValue(Key as string,lns as int,Value as Istring,opt ValueName as string),int "
a[8] =  "declare extern RegCopyKey(Key as String,ToKey as string),int"
a[9] =  "declare extern RegRenameKey(string mykey,string newkey),int"
a[10] = "declare extern RegKeyExists(Key as string),int"
a[11] = "declare extern RegCountAllSubKeys(Key as string),int"
a[12] = "declare extern RegGetQWValue(Key as string,opt ValueName as string),uint64"
a[13] = "declare extern RegSetQWValue(Key as string,Value as uint64,opt ValueName as string),int"
a[14] = "declare extern RegGetDWValueU32(Key as string,opt ValueName as string),uint64 'DWord Value"
a[15] = "declare extern RegSetNoneValue(Key as string,lns as int,Value as istring,opt ValueName as string),int "
a[16] = "declare extern RegExportKey(mykey as string,RegFileName as string,opt RegExportSort as int),int"
a[17] = "declare extern RegEntryExists(Key as string,opt ValueName as string),int"

'Begin the sort.
OPENCONSOLE
print
x1 = GetTickCount()
print "  Start time ",x1

count = 17 'The number we want to sort

swap=0

int change, cnt_step ' I like to define my variables this way, less typing
string s_tmp

cnt_step=(count-1)/2

do
change=0
loops++
for x=1 to count-cnt_step
if a[x]>a[x+cnt_step]
s_tmp=a[x+cnt_step]
a[x+cnt_step]=a[x]
a[x]=s_tmp
swap++
change++ 'count how many changes
endif
next x
if cnt_step>1
cnt_step=cnt_step/2
endif
until change<2 and cnt_step=1'if there is none or only one change, it should be finished.
'because all "big" entries are floated to the top nessesitating
'many changes (i hope I'm thinking right). This could make it take
'one less pass.

print
x2 = GetTickCount()
print "  End Time ",x2
print
print "  Sort took ",x2-x1," millisecs"
print
PRINT
PRINT "  Final alphabetical listing"
print

for x = 1 to count
    PRINT "  ",a[x]
next x

PRINT
print "  Number of swaps done ",swap
print
print "  Looped through ",loops
print
print
PRINT "  Press any key to exit..."
DO:UNTIL INKEY$ <> ""
END


If there are only a few items the bubble sort is the simplest to use.  If there are more items this one would work better.  It moves the "big" numbers up faster resulting in fewer iterations which means faster time.  Andy needs to give us several thousand items to test it on. 

Later,
Clint

[Brian]

Clint,

Attached a text file full of rubbish names and numbers you could use for testing?

Brian

[ckoehn]

Thanks Brian. Will play around with it.

[Andy]

Clint,

I've built up a large file of 100,000 lines of strings randomly generated (rnd.iwb).

I haven't tried it on your last sorting code, but have on the bubble4Optimised one (attached).

Run rnd.iwb first to generate the input file.

[billhsln]

Has anyone tested the HeapSort.iwb from the Examples.

Bill

[Brian]

Andy,

Your bubble4optimisedLarge example just hangs for me. I've adjusted slightly, and run
again, but no banana. rnd.iwb ran OK, though

Brian

[Andy]

Made the rnd.iwb make 1000 strings worked ok, just trying 100,000 - may have to leave the pc on all night.

Let's see....

[ckoehn]

I ran Brians data.  Just pulled out the first and last name and placed it in a string.  Used my last sorting algorithm it runs between 2.5 to 3.3 seconds.  Using my BubbleSort4 it takes 11 secs on my machine.  My machine is a quad core so it is fast.

[fasecero]

Very interesting topic! This code sorts Brian's list using 2 methods already proposed and a third one using C-runtime. To sort those 100000 lines tweak the code directly: change "SampleData.txt" to "input.txt" and the line FOR j = 1 TO 3 to FOR j = 3 TO 3.

Code Select Expand



/*

An example of how to sort arrys into alphanumerical order.
To do this I calculate the ASCII value of each alphanumeric character
and string of characters.

*/

$include "windowssdk.inc"

' -----------------------------------------------------------
' TIME ELAPSED STRUCT
' -----------------------------------------------------------

TYPE TIME_ELAPSED
INT loops
INT swap
UINT x1
UINT x2
ENDTYPE

' -----------------------------------------------------------
' VARS
' -----------------------------------------------------------

DEF a[100001]:string
DEF te:TIME_ELAPSED
INT j

' -----------------------------------------------------------
' ENTRY POINT
' -----------------------------------------------------------


OPENCONSOLE

FOR j = 1 TO 3
print
print "Reading data..."
INT count = ReadData(getstartpath + "SampleData.txt") ' SampleData - input
print "Done"
print

print "SORT #" + STR$(j)
TimeElapsedInit(te)

SELECT j
CASE 1: DoSort1(te, count)
CASE 2: DoSort2(te, count)
CASE 3: DoSort3(te, count)
ENDSELECT

TimeElapsedPrint(te)
PRINT "  Sending to output file....."
WriteData(getstartpath + "output" + STR$(j) + ".txt", count)
print "  Done"
NEXT j

print
PRINT "  Press any key to exit..."
DO:UNTIL INKEY$ <> ""
END

' -----------------------------------------------------------
' SORT METHOD
' -----------------------------------------------------------

SUB DoSort1(TIME_ELAPSED te, INT count)
INT change

do
change=0
te.loops++
for x=1 to count-1
if a[x]>a[x+1]
a[0]=a[x+1]
a[x+1]=a[x]
a[x]=a[0]
te.swap++
change=1
endif
next x
until change=0
ENDSUB

SUB DoSort2(TIME_ELAPSED te, INT count)
INT change
STRING s_tmp

INT cnt_step=(count-1)/2

do
change=0
te.loops++
for x=1 to count-cnt_step
if a[x]>a[x+cnt_step]
s_tmp=a[x+cnt_step]
a[x+cnt_step]=a[x]
a[x]=s_tmp
te.swap++
change++ 'count how many changes
endif
next x
if cnt_step>1
cnt_step=cnt_step/2
endif
until change<2 and cnt_step=1'if there is none or only one change, it should be finished.
'because all "big" entries are floated to the top nessesitating
'many changes (i hope I'm thinking right). This could make it take
'one less pass.
ENDSUB

SUB DoSort3(TIME_ELAPSED te, INT count)
pointer v = &a + 0 : v+ = 255
qsort(v, count, 255, &cmpFunc)
ENDSUB

DECLARE CDECL cmpFunc(pointer a, pointer b),int

SUB cmpFunc(pointer a, pointer b), INT
   return strcmp(a, b)
ENDSUB

' -----------------------------------------------------------
' TIME ELAPSED
' -----------------------------------------------------------

SUB TimeElapsedInit(TIME_ELAPSED te)
ZeroMemory(te, LEN(te))
te.x1 = GetTickCount()
print "  Starting"
ENDSUB

SUB TimeElapsedPrint(TIME_ELAPSED te)
te.x2 = GetTickCount()
print "  Sort took ",te.x2-te.x1," millisecs"
print
ENDSUB

' -----------------------------------------------------------
' I/O
' -----------------------------------------------------------

SUB ReadData(string _file), INT
int Index = 0
DEF myfile:FILE
DEF ln:STRING

IF(OPENFILE(myfile, _file, "R") = 0)
WHILE EOF(myfile) = 0
IF(READ(myfile,ln) = 0)
Index ++
a[Index] = ln
ENDIF
WEND

CLOSEFILE myfile
ENDIF

RETURN Index
ENDSUB

SUB WriteData(string _file, INT count)
DEF myfile:FILE

IF(OPENFILE(myfile, _file, "W") = 0)
for x = 1 to count
write myfile,a[x]
next x
endif
ENDSUB



[Andy]

Oh boy is this one fast!

On my random list of 100,000 lines it took around 4.5 hours to sort using the bubble4optimesed program, with the built in c sort (quick sort) it took just over half a second!!