Did a quick read on the subject. The Bucket sort looks like a glorified Bubble sort. I believe can still be done within a single array.

The Radix sort is interesting. I wonder how would one could easily obtain LSD, or MSD with TWX?   

How could I sort:
170, 45, 75, 90, 2, 24, 802, 66

into:
170, 90, 2, 802, 24, 45, 75, 66

..etc.


P.S. I'm not trying to be argumentative. Am genuinely curious.

Uhm, well it's not a glorified bubble sort... laff. A radix sort is a form of bucket sort.

An in-place algorithm is one that does it's job on the data being processed, without creating a second array.

LSD is not in-place, IIRC, MSD can be... but it will be tricky to handle the recursion. EP has managed to use stacks to replace the local namespace that's needed. It'll take a little work to adapt it to TWX, but I think it can be done. The benefit here is that as the list grows, the time required to sort the list is much much smaller. On really small lists I doubt it matters, but if you're working with 1000+ elements... it's going to make a big difference.

Neither of your 2 lists are sorted. The 2nd is only a single pass on (I think) an LSD version. You'd use getLength and cutText I guess.

But for a list that small, with a spread of less than 1000 a simple counting sort would be smarter... Make an $occurances array as you process the data that has how many times a particular value occurs. Then increment from the min to the max, and if there's an occurance then write it. This works great whenever the spread between min and max is relatively small, but as it gets larger it gets much less efficient. A counting sort is not in-place but with such a small dataset it hardly matters.

The second list is the result of a 1st pass LSD. Based on what I've read, the second pass would focus on the 'tens' column, and so on. However, without bitwise operators or even a MOD operator, looks like Bubble-type sorts win at the end of the day --as far as TWX is concerned.

Bubble sorts are n^2 time, radix is n*log(n) @ worst-case. Do the math, you don't need bitwise operators, all you need is an intelligent way to get a digit. With that said I think TWX has bitwise math, doesn't it? Couldn't you do a bitmask with XOR?

ok ill bite here is a script I thru together to clean the Major Space Lane list of duplicates and line them up in numerical value low to high.

I would be interested on how to do this without ending up with unwanted aarrays in memory. Speed not an issue on something that gets run once a game but its as good an example as any.

Forgive me. I can see clearly the speed advantage of a Radix sort over a Buble type.. my previous post simply stated that Radix sorts in TWX are not easily attainable and probably not even worth the effort. Using bitwise operators *is* an intelligent method. Case and point


and volla, a radix sort. First, TWX doesn't allow Logical expressions with XOR it only allows $SomeVar to be XOR'd with TRUE or FALSE. Besides. What's needed to achive a bitwise Radix sort is a Logical AND.

I'm not an expert by any means. But manipulating data with a mish mash of String functions resulting in mixing Data Types (Long Int -> unsigned Char -> Long Int) cannot ever be more efficient than dealing at the Binary Level.

Well as for Bubble Sort at least the 2 or 3 ways I tried it in comparing 2 arrays allowed me to make lunch while I was waiting so instead of this little contest maybe posting some actual code that can be timed would be more useful.
As for Radix sorts what would the LSD be in the amount of port product be? Only useful in telling if a port has over 2000 or 3000 or 10000 product to sell or buy otherwise will have to be done over and over for each digit. You can tell True or false from it but an array would have to be loaded first requiring many DB calls so I dont see the time saving their either.

okay. I'm way tired. here's what I whipped up:


it's over simplified because 1: I gotta hit the sack, ,and 2: I gotta hit the sack.. hehe

so if this were 2 sector sized array of 20 k the 8000000000000 comparisions would be made? Guess im missing something.

Yeah. Sigh. You appear to be. Your inital 'example' was loading a text file of MSL sectors via ReadAll , and THEN populated an Array sizeOf SECTORS ... holy moly Bat-Man.. take another look.. ReadAll your MSL list, and sort *that* Array.. you wouldn't ever need an array SizeOf SECTORS --to order your MSL list, which would max out at ho wmany Rows?? 20k?? Never saw that before

I'd sort a slew of sectors like this:
I'm not a student of algorithms... I just make them up when I need them.

Sing, that was a cool recursive stack routine... I should post it.

+EP+

I tawt I taw an EPcat!

Hm... I thought AND/XOR/OR could do more complex bitwise ops, guess not. Delphi's can. That's very wierd. Bitwise would be faster than cutText for sure, but I'm not convinced that cutText would be slower than using a comparable bubble sort. LS, all arrays are treated as strings, I believe, in TWXproxy. It's certainly not retyping the variable every single time you change something.

For sorting sector numbers yea, you can just use a basic counting sort like ya'll are doing. But what if you want to sort by something more complex, by say distance from dock or traffic count? The former has a small spread, the latter... well my version gets very big very quickly.

Be nice if we could get the bitops to work more naturally.

And yea it was a cool recursion.

The size of the example has what to do with the math? Grow up a little please. This Forum is for Adult discussion.

Heh, thanks Slim. You know I can't stay away from a good nerdy conversation for long

Sing, spell out the nature of the data to be sorted in more detail. If traffic count is simply a number, and you have a maximum of 20k numbers that need to be sorted, it shouldn't be too time-consuming. If it's something else, elaborate and maybe we can put our heads together. You know how I enjoy logic puzzles

What's with the mood swings in here?

+EP+