Verifying a Sorting Algorithm

https://4z2.de/2016/02/07/verifying-sorting-algorithms

by lorenzhs • 10 years ago

2 6 10 years ago

dalke3• 10 years ago

What about using a counting or layered Bloom filter? They also gives a probabilistic confirmation that the sorted list contains the same elements as the unsorted one.

Another solution, if the goal is to verify the sort algorithm, is to augment the sort data with position information (which isn't used in the sort), then use that to confirm that each of the original elements is used.

lorenzhs3• 10 years ago

That would be another option but you would have to evaluate several hash functions per element, which is a lot more expensive than a few multiplications and would use a lot more space.

What do you want to gain by augmenting the data with position information? Wouldn't you just have to check whether the positions array is a permutation of (1, ..., n)?

dalke3• 10 years ago

a lot more expensive than a few multiplications

It's "t" times the few multiplications, because each one gives a 75% success factor. This is equivalent to doing multiple hash functions.

and would use a lot more space

Well, yes and no. A Bloom filter is space-efficient, so it depends on what you compare it to.

If you have both lists in memory then each verification test can be run in constant memory.

But suppose you sort in-place? This cuts your overall memory use in half. You can use some of that saved space to construct the Bloom filter, then sort, then construct and compare the result.

It's also possible to compute all "t" values first, then sort in-place, then compare. This is another sort of signature. I don't know enough to tell if this will require more or less space than an equivalently powerful Bloom filter.

"What do you want to gain by augmenting the data with position information?"

It's a linear time check, rather than O(n log n). But at a cost of n * log(n) bits (or n*32 bits if we assume 32 bit indices.)

Verifying a Sorting Algorithm

Related Stories