Friday, December 04, 2009

SimpleSort

This is an algorithm to compete with the current slowest sorting algorithms.

1. We're given our list to sort, L
2. Create a list of length 0, M
3. Randomly, either append a random* value to the end of M, or remove the last value. If M has length 0 then we do not remove the last non-existent value.
4. Check if all elements of M are in L.**
5. If yes, check if all elements of L are in M.
6. If yes, check if M is in order.***
7. If no, repeat from Step 3. If yes, we've sorted it.

* this could be problematic.
if it's an int of size 32 for example, we can just add a number from -2^31 to 2^31-1.
if it's a float, we could do something similar for the 80-bit or 64-bit floating point value.
if it's a bignum, we can apply step 3 to the number itself as a string of digits.
if it's a string, we could also apply step 3 here.
if it's some arbitrary object, we can randomize every primitive type it's composed of in the above manners

** something like:
for x in M:
if not x in L:
break
else:
it's in there.
and vice versa for Line 5.

*** something like:
M += [+inf]
for i in 0...len(M):
if M[i] > M[i+1]:
break
else:
it's sorted
RJavaScript

theteofscuba: it would be veryu cool if html provided support for the same idea behind silverlight and allow people to use javascript to script it instead of using actionscript in flash or .net in silverlight
theteofscuba: and providing support for an xml format of 3d models so javascript could be the basis for a 3d engine
theteofscuba is offline (3:59:46 AM)

Your IM will be delivered when the buddy goes online.
inhahe: i agree
inhahe: that javascript should be integrated with something like silverlight
inhahe: so that you use teh same language for everything
inhahe: there is one problem wit hthat though
inhahe: silverlight/flash apps might be more cpu intensive in some case because they're more graphics involved
inhahe: and javascript, even the next-gen js engines, is very slow compared to .net
inhahe: not sure about flash, i would imagine actionscript is faster too
inhahe: this is a fundamental limitation given by the afct that javascript is a more dynamic language
inhahe: one interesting prospect would be to provide something syntactically similar to javascript but that is really just a subset of the language, so operations requiring teh particular dynamicism of javascript won't work within a restricted javascript block
inhahe: so that they can be compiled into faster code and used for things that need more speed
inhahe: ideally you would be able to define a restricted javascript block whether or not you're doing graphics-speciifc thinsg and you should be able to do graphics-specific things whether or not you're using restricted jaovascript
theteofscuba's offline IM storage is full.

RJavaScript would be to JavaScript what RPython is to Python.

Thursday, December 03, 2009

Hash Table Sort

For a given input list of size n, make a hash table of size n*2.

Run through the list once to determine its maximum and minimum values.

Create a hash function that puts an item in a slot depending on where it lies in between the minimum and maximum values. For example, if there are 50 slots, the minimum value is 10, and the maximum value is 20, then a value of 12 would go into the 10th slot. (A comparable formula *can* be used for strings.)

After placing all the items, go through the hash table and sort each individual linked list, using the sorting method most efficient for its size (probably always an insertion sort where the input list is randomly distributed). Concatenate all the sorted lists end-to-end.

This algorithm is less particularly advantageous the less unevenly distributed the input list, but we can always mitigate that problem by using an n*n hash table or just a larger hash table to any degree. Even an n*(n/x) hash table where each secondary table is a table of linked lists.

This algorithm could also use a histogram to determine individual slot ranges and secondary table sizes.

Where the range of values is smaller than the length of the list, you don't actually need a hash table of size n*2. It can be of size range*2.

I think this whole idea is just reinventing the bucket sort. Oh well.