[Guest]

in a typical sorting algorithm, the goal is to take random data and put it in order.

your task is the reverse, take an ordered bit of data, and do an "inverted" sort function.

for example, the reverse of merge sort might look like the following...

1 2 3 4 5 6 7 8 9 10 start

6 7 8 9 10 1 2 3 4 5 invert 1/2

7 6 10 9 8 2 1 5 4 3 invert 1/4

done.

here's the sort function you have to invert...

step = [1,2,3,5,8,13,21,34...]

maxindex = 0

while step[maxindex] < len(array):

   maxindex += 1

maxindex -= 2

for k in range(maxindex,-1,-1):

   h = step[k]

   for i in range(len(array)-h,-1,-1):

      i = j

      while j+h < len(array) and array[j] > array[j+h]:

         array[j],array[j+h] = array[j+h],array[j]

         j += h

try it with 100 elements, and give me the result!

Edited June 28, 2011 by phillip1882

[superprismatic]

in a typical sorting algorithm, the goal is to take random data and put it in order.

your task is the reverse, take an ordered bit of data, and do an "inverted" sort function.

for example, the reverse of merge sort might look like the following...

1 2 3 4 5 6 7 8 9 10 start

6 7 8 9 10 1 2 3 4 5 invert 1/2

7 6 10 9 8 2 1 5 4 3 invert 1/4

done.

here's the sort function you have to invert...

step = [1,2,3,5,8,13,21,34...]

maxindex = 0

while step[maxindex] < len(array):

   maxindex += 1

maxindex -= 2

for k in range(maxindex,-1,-1):

   h = step[k]

   for i in range(len(array)-h,-1,-1):

      i = j

      while j+h < len(array) and array[j] > array[j+h]:

         array[j],array[j+h] = array[j+h],array[j]

         j += h

[/code]

try it with 100 elements, and give me the result!


j is undefined here.

[Guest]

I seems that everyone konws PYTHON!

[superprismatic]

There's precisely 100! ways to invert any sorting function on 100 distinct elements.

[fabpig]

in a typical sorting algorithm, the goal is to take random data and put it in order.

your task is the reverse, take an ordered bit of data, and do an "inverted" sort function.

Sorry if I'm being a bit stupid here, but by "inverted" sort, do you mean reorganise ordered data (1,2,3,4........) into any old random disorder?

[fabpig]

<br />Sorry if I'm being a bit stupid here, but by &quot;inverted&quot; sort, do you mean reorganise ordered data (1,2,3,4........) into any old random disorder?<br />

<br /><br /><br />

Ignore that. What's left of my brain somehow added an extra word: now I've reread it, it makes (slightly) more sense!

[Guest]

superprismatic:

j is undefined.

obviously that should be j = i not i = j, sorry.

fabpig:

the goal bassically it to make that sorting algorithm take as long as possible in terms of number of swaps.