Lets talk about them! Which ones do you like/use/have implemented/have invented/etc.?
Code related:
// A spectacular variant of bogo-sort which has the interesting property
// that, if the Many Worlds interpretation of quantum mechanics is true, it
// can sort an arbitrarily large array in linear time.
static BogoSort(arrayToSort : array [int]) : void
{
// permute the array randomly using a quantum process
def rnd = Random(DateTime.Now.Millisecond);
def sort(left = 0)
{
when (left < arrayToSort.Length - 1)
{
def right = rnd.Next(left, arrayToSort.Length);
def tmp = arrayToSort[left];
arrayToSort[left] = arrayToSort[right];
arrayToSort[right] = tmp;
sort(left + 1);
}
}
sort();
// check if array is sorted
def check(left = 0)
{
def right = left + 1;
when (right < arrayToSort.Length)
{
if (arrayToSort[left] < arrayToSort[right])
check(right);
else
throw Exception("Sort failed! Please destroy the universe. :(");
}
}
check();
}
C# like syntax, object-oriented and functional programming, optional type annotation, .NET framework.. Sounds good!
Name:
Anonymous2007-08-01 15:42 ID:1j+4HILw
No reason to rewrite sorting algorithms, I like NIH so I don't have to take the blame.
Name:
Anonymous2007-08-01 18:25 ID:CjleYNTL
How is this algorithm called? I invented it!
def srt arr, i
if i < arr.length - 1
if not arr[i] <= arr[i+1]
tmp = arr[i]
arr[i] = arr[i+1]
arr[i+1] = tmp
srt arr, i == 0 ? i : i-1
else
srt arr, i+1
end
else
return arr
end
end
>>16
Can't be.. it has to have some cool name like Smoothsort, Gnome sort, LSD Radix sort or Bucket sort. You know..
Name:
Anonymous2007-08-01 19:28 ID:CjleYNTL
>>17
OK, I can't find it anywhere, I guess I really am the inventor! Though, it looks a bit like Bubble sort.. but should be faster!
Sweet. I think I'll name it Ghey Nigger Bubble sort.
Name:
Anonymous2007-08-01 20:14 ID:aT9U4L7e
My current favourite is the radix sort variant where you count the number of items that go in each bucket in the preceding radix pass, and therefore can produce your intermediate outputs right off the bat without linked lists or other such structures that require dynamic allocation. Destructive radixsort ends up using N temporary space for N sorted keys (plus a small constant amount depending on how big your radix is), which isn't that big a deal given that just storing the data you're about to sort requires about as much too.
Not exactly the most exciting algorithm around, and rather shitty from a theoretical standpoint. However, in today's computers optimization is about hitting the cache as often as possible and avoiding impredictable branching; this kind of radix sorting accomplishes the former by allocating temporary memory at the start of the routine and by not doing dynamic memory management, and the latter by using bitwise operations and indexing rather than comparisons. The "N storage to sort N items" issue's cache effect can be mitigated with prefetch instructions, as every pass of radix sort fetches keys in order. (Plus the temp space can be allocated on the stack if sufficiently small, which is nearly guaranteed to be "hot" already.)
Radixsort also has the worst-case advantage over qsort, which is nice if you're sorting inputs from an untrusted source, i.e. no chance of exploitable worst-case performance.
Name:
Anonymous2007-08-01 20:17 ID:aT9U4L7e
I'll poast code to >>19 if some expect BBCode programmer will tip me off on how I'd coax this board software to not mangle my indentation.