Programming Challenge: Nonsense Sort

[Duthomhas]

AKA a Random Sort.

Your task, should you choose to accept it, is to create a sort algorithm that unsorts data — i.e. create a random shuffle using a sorting method instead of anything like the venerable Knuth-Fisher-Yates algorithm.

Requirements
  • C++ only; no external libraries
  • Standard Library compatible: it must template to work over any type
  • It must terminate for all inputs (so test it before posting!)
  • Indicate in your answer whether the algorithm is biased or not.
    It would be sweet if the nonsense sort was unbiased, but that is not required.

There is no explicit ending date for this challenge.
  (It will officially terminate when this topic gets archived.)
  But I will stop caring about it on the ninth. That’s two weeks,
  since this is a holiday weekend in the US.

Thanks to jonnin for the idea and the name!

[mbozzi]

The Fisher-Yates algorithm is kind of selection sort in reverse, isn't it?

[jonnin]

the core idea I gave 'works' but not 'well' because the sort algorithm is not touching each element enough times to really get a good scramble on and it is attempting to swap particular elements predictably so even running it many times is not so hot. Worse, its NlgN and you can probably do better than this with just swapping randomized pairs in O(N). Still, this can serve as a baseline.
Rand or random isn't going to matter too much because of the inherent flaw in using sort as the scrambler.

#include <string>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <random>
using namespace std;

bool crazy(int a, int b)
{	
  return rand()%2;
}

int main()
{
   vector<int> v(10);
  iota(v.begin(), v.end(), 1);  

  //for(int i = 0; i < 10; i++)
	  //cout << v[i] << endl;
  
	sort(v.begin(), v.end(), crazy);	
	
	for(int i = 0; i < 10; i++)
	  cout << v[i] << endl; 	
}

[JLBorges]

> Rand or random isn't going to matter too much because of the inherent flaw in using sort as the scrambler.

Nothing is going to matter because the program engenders undefined behaviour.
(The predicate crazy does not meet the requirements of Compare.)
https://en.cppreference.com/w/cpp/named_req/Compare

This could be a viable idea:

There are other, less-desirable algorithms in common use. For example, one can assign a random number to each card, and then sort the cards in order of their random numbers. This will generate a random permutation, unless any of the random numbers generated are the same as any others (i.e. pairs, triplets etc.). This can be eliminated either by adjusting one of the pair's values randomly up or down by a small amount, or reduced to an arbitrarily low probability by choosing a sufficiently wide range of random number choices.
https://en.wikipedia.org/wiki/Shuffle#Shuffling_algorithms

[jonnin]

Heh, learn something every day... never had to study the rules on comparison function before and had no idea it was so strict.

[deleted account xyzzy]

A variation on the Fisher-Yates algorithm, the Sattolo Cycle(?):

#include <iostream>
#include <random>
#include <utility>  // std::swap
#include <vector>
#include <numeric>  // std::iota
#include <string>

template <typename T>
std::ostream& operator<<(std::ostream&, const std::vector<T>&);

template <typename T>
void crazy_sort(std::vector<T>&);

int main()
{
   std::vector<int> vecint(15);
   std::iota(vecint.begin(), vecint.end(), -5);

   std::cout << "Original int vector:\n";
   std::cout << vecint << "\n\n";

   crazy_sort(vecint);

   std::cout << "Crazy sorted int vector:\n";
   std::cout << vecint << '\n';

   std::vector<std::string> vecstr { "10", "20", "30", "40", "50" };

   std::cout << "Original string vector:\n";
   std::cout << vecstr << "\n\n";

   crazy_sort(vecstr);

   std::cout << "Crazy sorted string vector:\n";
   std::cout << vecstr << '\n';
}


template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v)
{
   for (auto const& x : v)
   {
      os << x << ' ';
   }

   return os;
}

template <typename T>
void crazy_sort(std::vector<T>& vec)
{
   static std::default_random_engine rng(std::random_device {}());

   for (unsigned i { vec.size() - 1 }; i > 1; i--)
   {
      std::uniform_int_distribution<unsigned> dis(0, i);

      unsigned j { };

      do
      {
         j = dis(rng);
      }
      while (j >= i);

      std::swap(vec[i], vec[j]);
   }
}

Rather brute force, even by the standard of this self-taught hobbyist.

[Duthomhas]

The UB problem is (partially) addressed by point 2: the algorithm must terminate for all inputs.

You can choose any sort algorithm that is guaranteed to terminate and it will work. For example, a heap sort will work with a random predicate:

template <typename RandomAccessIterator>
void nonsense_sort( RandomAccessIterator begin, RandomAccessIterator end )
{
  std::ranlux48 rng;
  std::bernoulli_distribution bd( .5 );
  auto compare = []( auto a, auto b ) -> bool { return bd( rng ); };
  std::make_heap( begin, end, compare );
  std::sort_heap( begin, end, compare );
}

It works, because heap sort does not depend on the comparison predicate for termination.


However, there are valid issues that arise from reality. For example, I once used qsort() and a random predicate, because qsort() was stated to be guaranteed to terminate. Sadly, not all implementations did that properly — implementation assumes a sane comparitor. (qsort() is not necessarily a quick sort.)

In cases like quick sort, there are also implementation issues: both the way the pivot is handled as well as the way that the subsections created in the divide step are handled make a huge difference in the correctness of the algorithm. Further, the method used for the partition step varies widely, and may fail for a crazy comparitor.

These are all issues with std::sort(), which is a modified quick sort that gives up and uses a heap sort if the quick sort finds itself in a worst-case scenario. Break the quick sort and you break the introsort.


C and C++ standards people like to write things that give implementations the widest latitude for creating an efficient and still-correct library. Hence, comparitors will be marked as requiring a strict-weak ordering, which basically means that all distinct elements in a set must be comparable with the < operator. Specifically:

  • x ≮ x
  • x < y → y ≮ x
  • x < y, y < z → x < z

A correct sort algorithm can require this basic premise.


This challenge is a bit of a round peg and square hole problem. You can easily create a quick sort that works with a random predicate — just mind your P’s and Q’s.

@mbozzi
Yes, you are exactly correct. KFY is a reverse selection sort. :O)

[helios]

int seed = get_seed();
std::sort(data.begin(), data.end(), [seed](const auto &a, const auto &b){
    Sha256 hash;
    hash.update(&a, sizeof(a));
    hash.update(&b, sizeof(b));
    hash.update(&seed, sizeof(seed));
    return hash.digest()[0] % 2 == 0;
});

[jonnin]

Going on the exotic side, trying to reverse shell sort, but so far less than exciting results.

[dhayden]

Helios beat me to it: sort where the comparison function compares the hash value of arguments.

[jonnin]

I like that one too, but it will do the same thing for the same data every time (or does it..?). I am not sure it meets the 'random' part of the problem description?

[helios]

That's why I added a seed that's independent of the data to unsort.

[jonnin]

Ok. I was not 100% sure what the seed did, to be honest. Short and sweet solution.

[helios]

More properly, I should have called it "salt".

[vondes]

hello, guys. I have read the thread and I need your help, I need to find a https://postcodefinder.net/england/sheffield sheffield postcode, preferably a list, add them to the program and sort them out. I already tried The Fisher-Yates algorithm and many more, but unsuccessfully... maybe you have any other ideas? I will be glad to any advice and recommendations.

[helios]

Make a new thread to ask your question. It's off-topic here.