8
\$\begingroup\$

TL;DR

  • Record (left-right)/length for each pair of consecutive elements. If they're 0 or negative, don't record it.
  • Once this is done, take these actions. Don't update quotients:
    • Increment right and decrement left for (0, .3)
    • Remove from the array at >=.3
    • Print both elements for >.5
  • Print the remaining array. Have some separator for executed and remaining.

Now, onto the challenge…

This is the sorting algorithm that has a worst-case of GLORIOUS LINEAR TIME, and where any who dare oppose its INFINITE WISDOM will be promptly EXECUTED for their HEINOUS CRIME OF HIGH TREASON.

The FEARLESS LEADER has tasked you with the HONORABLE MISSION of writing a program or function that takes in an array of integers and sorts it using the following sorting algorithm:

  1. Iterate through your array, enlightening each element with the GLORIOUS presence of their FEARLESS LEADER.
  2. Have your SECRET POLICE check on every pair of 2 consecutive elements to make sure they are PROPERLY LOYAL TO THEIR NATION. If they're not ordered correctly, record the difference between the numbers, divided by the length of the array. This is their dissent quotient.
  3. At the end of your GLORIOUS TOUR, go through the list and RAIN FEARLESS LEADER'S DIVINE PUNISHMENT on all of the TREASONOUS DISSENTERS as follows:
    • For a dissent quotient of less than .3, they merely need brainwashing a reminder of the INFINITE GLORY OF THE FEARLESS LEADER. Decrement the left element and increment the right element. Don't change any dissent quotients.
    • For a dissent quotient of .3-.5 (inclusive), they are TRAITORS and should be sent to PRISON CAMPS. Remove them from the array.
    • For a dissent quotient greater than .5, they are ODIOUS REBEL SCUM. They should be PUBLICLY EXECUTED as an example for any other TREASONOUS HERETICS they might have allied with. Remove them from the array and send it to the national news source, The STDOUT Times.
  4. Your array is now COMPLETELY AND FOREVER sorted. Send it to The STDOUT Times so they can sing of your GLORIOUS VICTORY.

As MANDATORY VIEWING to those who are too FOOLISH to understand the INFINITE GLORY of this algorithm, it will be used to sort the following array:

[1,8,6,0,4,9,3,5,7,2]
  • 1 and 8 are ordered correctly.
  • 8 and 6 aren't ordered right, so the dissent quotient of .2 is recorded for both of them.
  • 6 and 0 are another pair of dissenters. This dissent quotient is .6.
  • 0 and 4 are ordered correctly.
  • 4 and 9 are ordered correctly.
  • 9 and 3 have a dissent quotient of .6.
  • 3 and 5 are ordered correctly.
  • 5 and 7 are ordered correctly.
  • 7 and 2 have a dissent quotient of .5.

So, you take the following actions in the name of the FEARLESS LEADER:

  • Decrement 8 to 7, and increment 6 to 7.
  • Remove 0 and the new 7, and EXECUTE THEM.
  • Follow with 9 and 3.
  • Haul the original 7 and the 2 to the re-education camps and remove them.

This should be your press release, done in STDOUT or whatever's convenient:

Executions: 7, 0, 9, 3
[1, 7, 4, 5]

As you can see, the resulting array is COMPLETELY AND FOREVER SORTED. Attempting to suggest that it isn't sorted constitutes HIGH TREASON.

Now, as a GLORIOUS DEMONSTRATION of the UNENDING RESOURCES given by the FEARLESS LEADER, he has provided you with his INFINITE WISDOM in generating test cases:

import random

len=random.randint(2,20)
arr=list(range(len))
random.shuffle(arr)
print(arr)

dissent=[(arr[i]-arr[i+1])/len for i in range(len-1)]
dissent.append(0) # Barrier between front and back of the array.
executions=[]
for i in range(len-1):
    if dissent[i] > 0:
        if dissent[i] < 0.3:
            arr[i] -= 1
            arr[i+1] += 1
        elif dissent[i] > 0.5:
            if dissent[i-1] <= 0.5:
                executions.append(arr[i])
            executions.append(arr[i+1])

print([arr[i] for i in range(len) if dissent[i] < 0.3 and dissent[i-1] < 0.3])
print(executions)

Try it Online - hit the run button to use, otherwise you're just getting what the last person got.

In the interest of stare desecis, the FEARLESS LEADER has also provided an edge case example:

Input                  Output
3,2,1,4,4,1,2,3,4,5    2,2,2,4,2,3,4,5

(There are no executions in this example.)

Finally, you should treat the bytes in your program as key supporters and minimize them. The shortest program in bytes will win the ETERNAL FAVOR OF THE FEARLESS LEADER.

Credit where it's due

The concept for this was inspired by Lazy Drop Sort, and the writing style used was largely taken from Psychotic Dictatorships—go visit them if you enjoyed the parody aspect of this.

Additional credit goes to everyone who voted on this in the Sandbox early on. The +8 it attained was my motivation to rewrite it to avoid duplication.

\$\endgroup\$

closed as unclear what you're asking by Shaggy, Sriotchilism O'Zaic, FantaC, Muhammad Salman, Toto Apr 27 '18 at 10:07

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Mego Apr 27 '18 at 1:50
  • \$\begingroup\$ this needs a hell lot of renovation. More on what to do and less on stories. what do you think ? \$\endgroup\$ – Muhammad Salman Apr 27 '18 at 3:32
  • \$\begingroup\$ @MuhammadSalman as with the first time this was closed, I'd really like to know what's missing from the summary. \$\endgroup\$ – Stephen Leppik Apr 27 '18 at 14:37
  • \$\begingroup\$ @StephenLeppik : Nothing is missing from summary (I am pretty sure) but like I said , less stories and more to the point facts regarding what needs to be done. At least that is the reason I voted for it to be put on hold. Others may have different reasons. \$\endgroup\$ – Muhammad Salman Apr 27 '18 at 15:00
  • \$\begingroup\$ +1 for the interesting idea. -1 for the unnecessary over the top writing style. Interesting stories, while I'm not a fan of them, can be ok if they don't detract from the challenge, but I had to reread the challenge 3 times (even with the examples) to make sure I didn't miss anything. Also in your tl;dr you are missing the point saying if left < right then dissent = 0. Additionally, I'm pretty sure you mean left minus right, not right minus left since that would always be negative if right is less than left. \$\endgroup\$ – PunPun1000 Apr 27 '18 at 16:32
2
\$\begingroup\$

Ruby, 146 135 bytes

->l{e=[];i=0;l.inject{|j,k|q=(j-k)*10.0/l.size;b,c=l[i],l[i+=1];q>5&&e<<b<<c;q>0&&(l[i-1],l[i]=q<3?[b&&b-1,c&&c+1]:p);k};[l-a=[a],e-a]}

Try it online!

\$\endgroup\$

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