0

You are given loads of arrays and you want to know roughly how many steps it will take to sort each one.

A step consists of:

  • swapping the first and second element of the array.

  • rotating the array forward (last element becomes the first)

  • rotating the array backward.

so the default way of ranking these arrays is by assigning each array a random number. This gives 50% chance that the array with the higher number will take more steps to sort. I need to do better! (ideally around 80%)

Theo Walton
  • 1,085
  • 9
  • 24
  • Will those sort an array for sure? Please show an example – Pushan Gupta Jul 09 '17 at 11:19
  • 1
    @VidorVistrom It will. Take bubble-sort as an example - since he can rotate the array, he can effectively swap any two consecutive elements in the array, by moving them to the first and second positions and performing the swap operation. Whether this is the most efficient method given the operational constraints remains to be seen. – meowgoesthedog Jul 09 '17 at 11:23
  • @spug Yes it will..I just tried – Pushan Gupta Jul 09 '17 at 11:28
  • 2
    You may wish to start by simply [counting the number of inversions](http://www.geeksforgeeks.org/counting-inversions/) as this will give a lower bound on operations. – Peter de Rivaz Jul 09 '17 at 13:45
  • You first need to describe the method that will be used to sort an array before you can estimate how long it will take. For instance, will the in-array sorting algorithm already know exactly where every element belongs in the sorted array? Also, how long do you want your array-ranking estimator to take? If that doesn't matter, why not just sort them and see how long it takes? – RBarryYoung Jul 09 '17 at 17:08
  • Precisely, you need to formulate an exact algorithms where only these 3 rules are allowed. I can see that using just these 3 rules you can define an algorithm in more than 2 different ways. What is yours? – Pushan Gupta Jul 09 '17 at 17:12
  • You can get a rough idea by [counting the number of inversions](https://stackoverflow.com/questions/337664/counting-inversions-in-an-array). – Jim Mischel Jul 10 '17 at 00:58

0 Answers0