2

First of all, I am serious :)

You have array of N elements and we can compare them (e.g. operator > works).

Let's try to (unstable) sort it using following brand new sorting algorithm.

First, consider "smart" optimized bozosort - you choose 2 array elements at random, you compare them and only if first is great than second, then you swap.

Standard optimized bozosort implementation repeats that until array is sorted. However, we do this only specific number of times, say N/10 or N.

At the end array should be partially sorted. At least in theory, it will be in a better condition than before the bozo action.

Then we use some other sorting method, that benefits from partially sorted array. Let say merge sort (timsort) or quicksort (introsort / std::sort).
Some algorithms are out of the question, for example heapsort should be out, because it will first construct a heap and partial sort doesn't really matter.

I can see how this can be huge improvement for N^2 algorithms such insertion or shell sort, but I am not quite sure about N log N algorithms.

Any ideas with the analysis of this sort?

Pseudo code:

template<typename T>
void sort(T *m, size_t size){
   const auto max = size / 10;
   for(size_t i = 0; i < max; ++i){
      const auto a = random(size);
      const auto b = random(size);
      if (m[a] > m[b]){
         using std::swap;
         swap(m[a], m[b]);
      }
   }

   std::sort(m, m + size);
}
1
  • 1
    There's a bit of an opportunity cost here. Yes, you can help some algorithms by making the array more sorted on average. However, you could also spend the same effort on actually running the sorting algorithm. At first approximation, guaranteed progress is better than rolling the dice.
    – amon
    Feb 2, 2023 at 16:34

1 Answer 1

2

Yes, kind of.

We have, say, bozo + merge sort.

Cost is O(N) + O(N log N), which is O(N log N).

You're hoping that bozo can knock off that log N.

The only way we'd win is if bozo happened to get lucky, as we can verify "array is already sorted" in O(N) time. Let's pursue that in two different ways.

Ground rules: input array shall be a random permutation of integers 1 .. N, and pigeonhole / radix sort is prohibited.

  1. Given an is_sorted() predicate, we could compute the probability that second phase, mergesort, isn't needed, and then the expected cost sums to slightly less than O(N log N).
  2. Given a find_first_unsorted_index() function that identifies a (possibly empty) sorted prefix in linear time, we could compute a probability distribution over the size M of the unsorted suffix. Now there are battling terms, where we potentially have O(N) > O(M log M).

(To be clear, letting bozosort process a fixed fraction of N entries, like 10%, puts it firmly in the O(N) linear work category.)


Here is one definition of a "sorted prefix", tailored to run in linear time.

Iterate through array, comparing pairwise elements to verify they are sorted. So verify a[0] <= a[1], then a[1] <= a[2] and so on.

Let max_prefix be index of first violation. For example, in [0, 1, 2, 4, 3] it would be 3. In [1, 0] it is 0. It is N for a sorted array; the is_sorted() predicate simply outputs whether it's N.

If it is positive, we remember the last winning value, last_value = a[max_prefix - 1], and continue scanning to end. If we encounter any value less than last_value, we are forced to declare the sorted prefix length is zero, since we don't get to loop through the prefix.


We can bail early, prior to finding first violation, at the point that M log M work is less than N work. That reduces the risk of encountering a spoiler value less than last_value.


Altering the ground rules would change the probability distribution, but it's not clear that that's useful.

Sorting large, distinct, positive integers would put radix sort back on the table as a possibility.

Sorting a 50-50 mix of booleans gives bozo a better shot at winning, but radix sort trivially deals with it in linear time.

Sorting N-1 zeros plus a single one would be the simplest case to analyze, except that radix already told us the answer is O(N).

1
  • Sorting bools often requires stable sort. else you can just use counting sort. Bozo action does not try to check if array is sorted, because it requires O(n) steps, it just try to change some numbers at random. and may be the numbers after them, because they are already in CPU cache (not shown in the code)
    – Nick
    Feb 1, 2023 at 23:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.