"Creative" ways to determine if an array is sorted

51

21

Given an integer array, write a program that determines if it is sorted in ascending order.

Remember that this is a code trolling question.

I am looking for most interesting ways that people come up with.

The answer with most upvotes wins.

This question is inspired by a 'creative' solution that a candidate gave me in an interview :)


The 'creative' solution was something like this:

  • Because for a sorted array

    • all the elements on the left side of any element must be smaller
    • all the elements on the right side of any element must be bigger

Therefore, run a main loop for all elements and check the above two conditions by running two nested loops inside the main one (one for left side and one for right side)

I was shocked!!.

microbian

Posted 2014-02-27T16:33:02.227

Reputation: 2 297

58This is not a duplicate. Some moderators feel it necessary to mark every question duplicate to others without reading it. This is not a sorting question at all. Read it. – microbian – 2014-02-27T17:16:54.227

3At the end of the contest I would like to know the "creative" solution, too! :) – Vereos – 2014-02-27T17:23:56.980

1@microbian why do you think that this guy is a mod? – Mhmd – 2014-02-27T17:39:11.697

1Because you get mod privileges after certain reputation (i think 500) and you see option to close questions. – microbian – 2014-02-27T17:40:32.970

16@micro Diamond moderators are community elected. You are confusing moderators with the privilege system. – Doorknob – 2014-02-27T17:58:36.163

3@microbian So have you hired that guy? – VisioN – 2014-02-28T08:17:21.850

I am confused, do you want 1) creative answers to determine whether an array is sorted (regular popularity contest), 2) bad, deconstructive or cheating solutions to task of checking whether an array is sorted (regular code trolling) or 3) bad, deconstructive or cheating solutions to task of checking in a creative manner whether an array is sorted (code trolling of case 1)? To me it reads like the latter, but that’s unlikely a good task. – Wrzlprmft – 2014-02-28T11:44:16.290

1https://xkcd.com/1185/ – TheDoctor – 2014-02-28T23:29:03.577

3If only StackExchange API allowed write access, I'd ask the question "Is this array sorted?" and count upvotes on positive/negative answers.. – Michael Foukarakis – 2014-03-01T08:31:05.367

Good start of a recursive solution? shellsorted? Ouch. – Henk Langeveld – 2014-03-01T11:09:30.107

Did you tell the guy it has to fast. – PyRulez – 2014-03-02T02:36:23.540

@microbian Gaining privileges does not make you a mod, mods have a diamond next to their name and extra "powers" that normal users cannot get through privileges. – Izkata – 2014-03-02T04:55:22.110

Just for clarification, had you asked the candidate for a creative solution? Was this a good answer to your question (to see if the candidate could think outside the box) or were you shocked because you were expecting something more... useable? – Reinstate Monica -- notmaynard – 2014-03-03T15:52:51.830

1No, I did not ask for any out of the box solution. I just asked the plain question. He said this is the only solution he could think of. – microbian – 2014-03-03T16:16:43.090

Well that made no sense then. Why would you go for O(n2) solution while O(n) solution would do just the thing and is obvious. – Manish Shukla – 2014-03-05T06:09:26.747

Code-trolling is in the process of being removed, as per the official stance. This question is very highly voted with many highly voted answers, and recieved over 50% "keep" votes on the poll, so I am locking it for historical significance.

– Doorknob – 2014-05-10T16:11:58.653

Answers

77

Ruby

Everyone knows: sorting is very slow and takes many cycles (the best you can do is something with n log(n)). Thus it is quite easy to check if the array is sorted. All you have to do is compare the runtime of sorting the array and sorting the sorted array.

array = [1, 5, 4, 2, 3]

## measure the time needed to sort the array 1m times
tstart = Time.now
1000000.times {
  array.sort
}
trun = Time.now - tstart

## now do a reference measurement on a sorted array
array.sort!
tstart = Time.now
1000000.times {
  array.sort
}
treference = Time.now - tstart

## compare run times
if trun > treference
  print "array was not sorted"
else
  print "array was sorted"
end

Howard

Posted 2014-02-27T16:33:02.227

Reputation: 23 109

19This depends on the sorting algorithm though. Merge sort or heap sort would not show any difference at all, independent of whether the array is already sorted or not. – Niklas B. – 2014-02-27T19:17:12.753

4

@NiklasB. Ruby uses quicksort. That said this method could get tricky and give false positives when the input array is almost sorted, or, more likely, false negatives when the array is sorted (it would be very unlikely for treference <= trun for every sorted case, just due to nondeterministic other stuff). In theory it seems like you'd get about 50% false negatives for the sorted case?

– Jason C – 2014-02-28T03:14:10.343

6Interesting thought but not deterministic. Its about as good as one could do ten push ups and then ten more push ups and then decide if the first array was sorted or not because one sweated more on the second set of push ups. Did we forget, we run code on multi-tasking machines? Also on very small arrays, the time slice is simply not accurate enough. +1 for a wild attempt though! – LMSingh – 2014-02-28T07:58:46.867

1@NiklasB. Timsort (a variant of mergesort) runs in linear time on sorted (and also partially sorted) arrays. – Bakuriu – 2014-03-01T18:09:41.167

@Bakuriu: I'm aware that there are sorting algorithms that run in linear time on sorted input. For example any sorting algorithm combined with a precheck that exits if the array is already sorted. That doesn't invalidate my argument though :) – Niklas B. – 2014-03-01T21:06:26.273

@Bakuriu Just going with "linear time" does not take into account the constant / negligible differences, which this method would include in its measurement - specifically, partially-sorted arrays will take the tiniest bit longer than fully-sorted arrays regardless. – Izkata – 2014-03-02T04:58:22.653

1@JasonC Just knowing that it's quicksort doesn't help. The original version of quicksort (which picked the first element in each range as the pivot) is actually slower on already sorted data. I'm guessing ruby's implementation picks the middle element, as this is the version that runs faster on presorted data... – Jules – 2014-03-03T20:02:45.427

@Jules Thanks, I didn't know that! I mostly just meant my comment as "FYI, Ruby doesn't use merge sort or heap sort." – Jason C – 2014-03-03T21:16:25.633

3@JasonC - it's worth noting that this makes the implementation above even more dubious: it relies not only on the knowledge that ruby's internal sorting algorithm is quicksort (which is in itself undocumented and therefore a dubious thing to rely upon) but that the specific implementation is optimized for the case of already-sorted data (which quicksort by default is not: quicksort is only O(n log n) on average case... its worst case performance is O(n^2) and in a naive implementation that worst case is actually being called on already-sorted data). – Jules – 2014-03-05T08:26:49.890

52

Javascript

array = prompt("Give the array");
while (true) {
    sorted = prompt("Is it sorted?");
    if (/yes|Yes/.test(sorted)) {
        alert("The array is sorted.");
        break;
    } else if (/no|No/.test(sorted)) {
        alert("The array is not sorted.");
        break;
    } else {
        alert("Dear user:\n\nPlease refer to the manual (RTFM) to observe how to use the system accordingly to the defined business rules.\nNow, try again.");
    }
}

Victor Stafusa

Posted 2014-02-27T16:33:02.227

Reputation: 8 612

55-1 not enough JQuery. – Pierre Arlaud – 2014-02-28T14:09:53.463

3I had a similar idea that would ask for the array, and then one by one prompt "is this bigger than this?" And if all are true, then the array is sorted – Zach Thacker – 2014-02-28T15:03:02.967

41

Java - Recursive Subsets

Welcome to Stack Overflow! This is an excellent first question, as it stumps even some veteran coders. Let me give you a bit of background information before I just hand out the code:

Determining sortedness can be a difficult task at first glance. For any set of length n, there are n! possible ways of ordering it. These are called permutations. If your array has distinct elements, only one of those possibilities is sorted! To find the sorted one, you have to sift through them all until you find the right (possibly only) one, discarding all the others.

What? Surely it isn't that hard...

Algorithms with n! complexity take a long time for larger inputs, but with a bit of work we can get around that, and move down a whole order of complexity. That's still exponential time, but it's much better than factorial.

To do this, we only need consider the following mathematical fact: If an array is sorted, then every one of its (relatively ordered) subsets is sorted as well. You can ask the experts over at Mathematics for a formal proof, but it's intuitively true. For instance, for the set 123, the proper subsets are 1 2 3 12 13 23. You can see they are all ordered. Now if the original was 213, you'd have 2 1 3 21 23 13, and right away you can see that 21 is out of order.

The reason this is important is because there are far fewer than n! subsets. In fact, there are only 2n-2 subsets we need to look at. We can exclude the set containing the entire array of original numbers, as well as the empty set.

Still, 2n-2 can be a lot of work. As with most things that exceed polynomial time, a divide-and-conquer approach works well here. The simplest approach? Recursion!

The basics steps are simple. For every subset of your input, you generate smaller subsets. Then for each of those, you do the same thing. Once your subsets are down to size 2, you simply check which one is bigger. Since you shrink the size of the subsets each time, it actually goes quicker than you'd expect.

The key fact here is that you can exit early, as soon as you find a single subset out of order. You don't have to search through them all. If one is bad, the whole group is bad. This is a speed consideration you don't see in a lot of these other answers.

Enough talk, let's have the code!

I've done this in Java since it's a popular language and easy to read. The elegance of the recursion should be apparent:

import java.util.ArrayList;

public class SortChecker {

    static final Integer[] input = {1, 2, 3, 4, 5};

    public static void main(String[] args) {
        if(isSorted(input))
            System.out.println("The array is sorted properly.");
        else
            System.out.println("The array was not sorted properly.");
    }

    public static boolean isSorted(Integer[] in){
        if(in.length == 1)
            return true;
        if(in.length == 2)
            return (in[0] <= in[1]);
        ArrayList<Integer[]> subsets = getSubsets(in);
        for(Integer[] next : subsets){
            if(!isSorted(next))
                return false;
        }
        return true;
    }

    public static ArrayList<Integer[]> getSubsets(Integer[] in){
        ArrayList<Integer[]> subsets = new ArrayList<Integer[]>();
        int bitmasks = (1 << in.length) - 1;
        for (int i = 1; i < bitmasks; i++){
            ArrayList<Integer> subset = new ArrayList<Integer>(); 
            for (int j = 0; j < in.length; j++)
                if ((i & (1 << j)) > 0) 
                    subset.add(in[j]);          
            subsets.add(subset.toArray(new Integer[1]));
        }
        return subsets;
    }
}

For the record, I got bored and killed it after waiting 15 minutes for a sorted 12-element array. It'll do 11 elements in about 45 seconds. Of course, it really does exit earlier for non-sorted, so that's, um, good.

Update: On a fresh reboot, it does 12 elements in 13 minutes. 13 takes almost 3 hours, and 14 is at 20 hours and counting.

Geobits

Posted 2014-02-27T16:33:02.227

Reputation: 19 061

8+1 this is probably the least efficient algorithm I've ever seen. Should be around O(n!*2^(n!))-Complexity (probably worse). – Ral Zarek – 2014-02-28T11:35:16.033

6I'm sure I've seen worse, but it is pretty bad. I half-heartedly tried to determine complexity, but gave up and called it O(big). – Geobits – 2014-02-28T13:55:56.733

It looks like O(n!*2^n) to me. – Brilliand – 2014-02-28T17:11:20.167

1Providing a solution that is less efficient then even the naive attempt of the travelling salesman problem is impressive! – recursion.ninja – 2014-03-01T17:56:06.830

-1 getSubsets doesn't work for arrays longer than 32 items… :-) – Bergi – 2014-03-02T13:15:28.763

3As the chance of a 12 element array being sorted is only 1 in 479 million, it really doesn't matter that it takes a while to be absolutely certain that one is, surely? You're never actually likely to see one in the real world... – Jules – 2014-03-03T20:07:11.527

@Bergi do you really think that is a problem? I mean, there is only a worse than 1 in 8 undecillion chance that a 33 item array is sorted! It's not like you will ever see one in your lifetime! – Josef says Reinstate Monica – 2014-03-04T12:04:40.180

@Josef Are you ready for a once-in-a-lifetime experience? You better sit down! Annnd { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33 }. – Jason C – 2014-03-05T12:57:44.907

1@JasonC It's not that I don't trust you when you say that array's sorted, but my program balked upon entering it. Can you give a proof? – Geobits – 2014-03-05T13:56:12.223

2

@Geobits No problem. Run Victor's algorithm and answer "yes" at the first prompt.

– Jason C – 2014-03-05T14:12:08.747

... unless you meant "sordid". I have videos of it kicking puppies and stealing toys from babies.

– Jason C – 2014-03-05T14:15:32.593

1@JasonC Actually, I meant "sworded", but now that I look again, I can see there are indeed 14 swords(1) included. – Geobits – 2014-03-05T14:17:42.730

1

@Geobits On August 18, 2013, some random girl on tumblr shared this same experience with her friends.

– Jason C – 2014-03-05T14:23:17.467

29

C++ - a brute force method

Everybody knows that brute force methods are always the fastest.

bool issorted(std::vector<int>& list)
{
  switch (list.size()) {
    case 0: case 1: return true;
    case 2: return list[0]<=list[1];
    case 3: return list[0]<=list[1] && list[1]<=list[2];
    case 4: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3];
    case 5: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4];
    case 6: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5];
    case 7: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6];
    case 8: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7];
    case 9: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8];
    case 10: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9];
    case 11: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10];
    case 12: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11];
    case 13: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12];
    case 14: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13];
    case 15: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14];
    case 16: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15];
    case 17: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16];
    case 18: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17];
    case 19: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18];
    case 20: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19];
    case 21: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20];
    case 22: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21];
    case 23: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22];
    case 24: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23];
    case 25: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24];
    case 26: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25];
    case 27: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26];
    case 28: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27];
    case 29: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28];
    case 30: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29];
    case 31: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30];
    case 32: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31];
    case 33: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32];
    case 34: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33];
    case 35: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34];
    case 36: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35];
    case 37: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36];
    case 38: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37];
    case 39: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38];
    case 40: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39];
    case 41: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40];
    case 42: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41];
    case 43: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42];
    case 44: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42] && list[42]<=list[43];
    case 45: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42] && list[42]<=list[43] && list[43]<=list[44];
    case 46: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42] && list[42]<=list[43] && list[43]<=list[44] && list[44]<=list[45];
    case 47: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42] && list[42]<=list[43] && list[43]<=list[44] && list[44]<=list[45] && list[45]<=list[46];
    case 48: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42] && list[42]<=list[43] && list[43]<=list[44] && list[44]<=list[45] && list[45]<=list[46] && list[46]<=list[47];
    case 49: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42] && list[42]<=list[43] && list[43]<=list[44] && list[44]<=list[45] && list[45]<=list[46] && list[46]<=list[47] && list[47]<=list[48];
    case 50: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42] && list[42]<=list[43] && list[43]<=list[44] && list[44]<=list[45] && list[45]<=list[46] && list[46]<=list[47] && list[47]<=list[48] && list[48]<=list[49];
    case 51: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42] && list[42]<=list[43] && list[43]<=list[44] && list[44]<=list[45] && list[45]<=list[46] && list[46]<=list[47] && list[47]<=list[48] && list[48]<=list[49] && list[49]<=list[50];
    case 52: return list[0]<=list[1] && list[1]<=list[2] && list[2]<=list[3] && list[3]<=list[4] && list[4]<=list[5] && list[5]<=list[6] && list[6]<=list[7] && list[7]<=list[8] && list[8]<=list[9] && list[9]<=list[10] && list[10]<=list[11] && list[11]<=list[12] && list[12]<=list[13] && list[13]<=list[14] && list[14]<=list[15] && list[15]<=list[16] && list[16]<=list[17] && list[17]<=list[18] && list[18]<=list[19] && list[19]<=list[20] && list[20]<=list[21] && list[21]<=list[22] && list[22]<=list[23] && list[23]<=list[24] && list[24]<=list[25] && list[25]<=list[26] && list[26]<=list[27] && list[27]<=list[28] && list[28]<=list[29] && list[29]<=list[30] && list[30]<=list[31] && list[31]<=list[32] && list[32]<=list[33] && list[33]<=list[34] && list[34]<=list[35] && list[35]<=list[36] && list[36]<=list[37] && list[37]<=list[38] && list[38]<=list[39] && list[39]<=list[40] && list[40]<=list[41] && list[41]<=list[42] && list[42]<=list[43] && list[43]<=list[44] && list[44]<=list[45] && list[45]<=list[46] && list[46]<=list[47] && list[47]<=list[48] && list[48]<=list[49] && list[49]<=list[50] && list[50]<=list[51];
  }
}

The actual routine is longer (it goes to std::npos), but I'm limited to 30000 characters in posting here.

Mr Lister

Posted 2014-02-27T16:33:02.227

Reputation: 3 668

I really like this. – Jakob – 2014-03-03T10:23:59.083

3This is like the "use every part of the buffalo" approach to case statements. – Jonathan Van Matre – 2014-03-03T13:48:53.157

This is awesome. Unroll all the loops! – McKay – 2014-03-04T14:45:06.810

great thought!!! – bikram990 – 2014-04-30T09:01:15.247

26

Inform

Inform is a language for writing interactive fiction games for the classic Infocom Z-machine interpreter. To avoid spoilers, I'm giving the results of my program first, then the source code.

Edit: I made a small revision to allow adding numbers to the array, and included a charming room description.

Sorted
An Interactive Fiction by Jonathan Van Matre
Release 1 / Serial number 140301 / Inform 7 build 6G60 (I6/v6.32 lib 6/12N) SD

Sorting Room
You are in the Sorting Room, a sterile expanse of pure white. Translucent
lucite walls leak a lambent clinical light into the spotless room.

You can see a safe (closed), a flask of poison, a radioactive isotope 
attached to a radiation detector that triggers a hammer, an array (empty) 
and Erwin Schrodinger here.

>open safe
You open the safe.

>put flask in safe
(first taking the flask of poison)

You put the flask of poison into the safe.

>put isotope in safe
(first taking the radioactive isotope attached to a radiation detector 
 that triggers a hammer)

You put the isotope detector assembly into the safe, carefully placing 
the hammer next to the fragile glass of the flask of poison.

>get array
Taken.

>put numeral 1 in array
(first taking the numeral 1)

You put the numeral 1 into the array.

>put 2 in array
(first taking the numeral 2)

You put the numeral 2 into the array.

>put 3 in array
(first taking the numeral 3)

You put the numeral 3 into the array.

>examine array
In the array are a numeral 3, a numeral 2 and a numeral 1.

>put array in safe
You put the array into the safe.

>ask Erwin about whether the array is sorted
Erwin grumbles and complains, "You haven't finished the experiment" 

>close safe
You close the safe.

>ask Erwin about whether the array is sorted
Erwin beams and proudly announces, "Indeterminate!" 

And herewith the source code:

"Sorted" by Jonathan Van Matre

The Sorting Room is a room. "You are in the Sorting Room, a sterile expanse of pure white. Translucent lucite walls leak a lambent clinical light into the spotless room."
The safe is a container. The safe is in the Sorting Room. The safe is openable. The safe is closed.
There is a flask of poison in the Sorting Room.
There is a radioactive isotope attached to a radiation detector that triggers a hammer in the Sorting Room.
There is an array in the Sorting Room. The array is a container.
There is a numeral 1 in the Sorting Room. The numeral 1 is undescribed.
There is a numeral 2 in the Sorting Room. The numeral 2 is undescribed.
There is a numeral 3 in the Sorting Room. The numeral 3 is undescribed.
There is a numeral 4 in the Sorting Room. The numeral 4 is undescribed.
There is a numeral 5 in the Sorting Room. The numeral 5 is undescribed.
There is a numeral 6 in the Sorting Room. The numeral 6 is undescribed.
There is a numeral 7 in the Sorting Room. The numeral 7 is undescribed.
There is a numeral 8 in the Sorting Room. The numeral 8 is undescribed.
There is a numeral 9 in the Sorting Room. The numeral 9 is undescribed.
In the Sorting Room is a man called Erwin Schrodinger.
Understand the command "ask" as something new.
Understand "ask [someone] about [text]" as asking it about.
After inserting the isotope into the safe:
    If the safe encloses the flask, say "You put the isotope detector assembly into the safe, carefully placing the hammer next to the fragile glass of the flask of poison.";
Instead of asking Erwin about something:
    If the safe is closed and the safe encloses the flask and the safe encloses the array and the safe encloses the isotope, say "Erwin beams and proudly announces, 'Indeterminate!' ";
    Otherwise say "Erwin grumbles and complains, 'You haven't finished the experiment' ";

Jonathan Van Matre

Posted 2014-02-27T16:33:02.227

Reputation: 2 307

21

Doge Ruby

First you must run this setup code

class Array;alias ruby sort;end
def self.method_missing x,*a;x;end
def very x;$a=x;end
def many x;$b=$a.send x;end
def wow;puts $a==$b;end

Then just store the array in a variable called coding and run:

  very coding

                 many ruby
so algorithm


      wow

And your answer will be printed (true or false).

Please also add the doge code for optimal performance:

#~! SET DOGE=1 PERFORMANCE=OPTIMAL ONERROR=nil PIC=
#                    ***=*                                                       
#                    **===*                                                      
#                    ***=-=&                                   &&**&             
#                    **==--=                                  ***===*            
#                   &***=---*                               $*=------*&          
#                   &***=---=*                             $**=----;;=&          
#                   &**==----=&                           &*===---;;;-*          
#                   &**==----=*                          &**=-==--;;;;=          
#                   ****=-----=*                       &&*==--=---;;;;-          
#                   **===------=&                     $&*==-------;;;;-          
#                   **===-------=*&$$                &*==------;;;;;;;-          
#                   **==----==-====***&&&&&&&&$$    &*==-;;---;;;;;;;;-&         
#                  &*=---=====================*******=---;---;;;;;;;-;;=         
#                  *=======*=========================---;;--;;;;;;;;;;;*         
#                  *===***=======================------;;--;;""""";;;;;=         
#                  *=*****========================;--;;;;--;;""""";;;;;*         
#                &*********====-----===============;;;;;----;"","";-;;-&         
#               ***********====----================-;;;;----;",,";;----          
#             &************===---====================-;;;;;;",,"";----=          
#            &*************===---=====================-;;;;",,,";-----*          
#            ******=*******===--=======================--;",,,"";-----&          
#           &**************==--=========================-;"","";----;-           
#          ****************==---====****=====-===========--;";;-;;;";=           
#         ****************==----==*******===--=============--;----;--=           
#        &*****=;"";==***===----==*******===----=============------;-=$          
#        &&&***;"",,"-**====---==********=====-===============----;;;-&          
#       &&&&&*=-;;";";*==========****=***======--=========***==---;;;-&          
#      $&&&&&&=="",,,-===**=======***==-;-=================**===--;;;;*          
#      &&&&&&&-="",,"==***==***======-",,,";=-===================--";;=          
#      &&&&&**=-""";==****=***===---;"-=-,,,"--===================-;;;=&         
#     &&&&&&***--;=***********=---;,,-*",,,,,"--==================--;--*         
#     &&&&&***=*=*************=-;;","=-,,,,,,"-====================----=$        
#    &&&&&&*******************==--","-;,,,,,"-====*****=============-===&        
#   $&&&&&&******************===---",";"""";=******************=====-===*        
#   &&&&&&&&&*****************======--;;--==********************=========&       
#  &&&&&&&&&&&******=**********===========*==*****&&************=========*       
#  &&&&&&&&*=---;--==**********==============*********************=======*&      
#  &&&&&&&-""""";;"";=**********==**=========*****&&&**************=======*      
# &&&&&&&*,,,,,,,,,,,"-****&************=*******&&&&&&&************========&     
# &&**&&&=,,,,,,,,,,,,;*&&&&***********************&&&&&&***********=======*     
# &&&*&&&*",,,,,,,,,,,;*&&&*************&&**********&**************========*&    
#&&&&&&&&-"",,,,,,,,,,-*&&&**********&**&&&&&&&******************==========**    
#&&&&&&&*=,,,,,,,,,,,"-***************&&&&&&&&&*****************====--======*&   
#&&***&&*=;,,,,,,,,,";=*==*****************&&&***************=======--=======&   
#*&&&&**=-;",,,,,,"";-=*********=**&*********&&**************=======--======**   
#&&&&&**=-""",,,,,"";==**==***===**********************======***===---=======*&  
#&&&&&**=-;"""""","";;=-===*======*********************==******====----======*&  
#*&&&&**=-;""""""""";=-============*****************==*********====---==--===**  
#&&&&&***=",,,,,,"""";--=============*******==****************====----=--====**& 
#&&&&&****"",,,,,,,,,;-=========--===****====******************====--==-======*& 
#&&&&&&&&*-"",,,,,,,,,"--==--;"""";====**===********************======--======** 
#&&&&&&***=-;",,,,,,,,,,,;",,,""";-=======********************===-------=======* 
#&&&&&&&****=;""""""""",,,"""";;--==**====*******************=====--------=====* 
# &&&&&&&***=-;;;;;;;;;"";;;;;---==***====*****************=====--=--------====*$
# &&&&&&*****=-;-----=--------=====*=======****************====-==---------=====&
#  &&&&&******==-==-=============***========*************======----=--------====&
#  &&&&************==========================***********=====----------------===*
#  $&&&&***************====================***********=*======-------------=--==*
#   &&*&************=====================**************======--------------=====*
#   &******************=================**************=========-----------======*
#    &***********=*****================************==========------;-------=====*
#    &*****************================***********=============---------========*
#     &*************===================**********==***========--------========***
#      **************==================********====**===*=====--------=======****
#      &************=============================*****=*=====--------=======*****
#       &****=*******=============================**============--=======*=******
#       $*****=====**===========================***===================**********&
#        &*****=====================-====-====*=*=====*=======--==***************
#         &*****===========---==--===============**=**=*========*****************
#          &*****====---=---------========********======***===*******************
#           *****=======-=-------======*******=**==****==*==*********************
#           $***======================******===**********************************
#            &***===================*******==***=******************************=&
#             &***=========-=========*************==***************************=&
#              ******===*=======*=*****************==*************************==&
#~! END

This is the easiest way.


(the ASCII art was generated by a script I wrote up, derived from this image.)

Doorknob

Posted 2014-02-27T16:33:02.227

Reputation: 68 138

7You forgot "so algorithm". A real doge sample has 3 sentences before "wow". And yes, I'm very fun at parties. – Pierre Arlaud – 2014-02-28T14:12:15.037

@ArlaudPierre Heh, okay, fixed :P – Doorknob – 2014-02-28T14:15:06.623

11So comment, very improvement, many useful. Wow. – Pierre Arlaud – 2014-02-28T14:19:10.973

You should have written a BF program in ascii shaped like a doge... new question idea!! – TheDoctor – 2014-02-28T23:27:47.633

19

PHP

You'd love the easiness and straightforwardness of the following solution. The overall concept and the cutting edge functions used in this masterpiece of coding will immediately bring you up to the elite list of the top developers of the World.

function is_sorted($input) {
    mysql_connect('localhost', 'name', 'password');
    mysql_select_db('database');

    mysql_query('
        CREATE TEMPORARY TABLE sorting_table (
          `value` int NOT NULL
        )');

    foreach ($input as $value) {
        mysql_query('INSERT INTO sorting_table VALUES (' . $value . ')');
    }

    $i = 0;
    $result = 'SORTED';
    $query = mysql_query('SELECT * FROM sorting_table ORDER BY value ASC');
    while ($value = reset(mysql_fetch_row($query))) {
        if ($input[$i++] != $value) {
            $result = 'NOT SORTED';
            break;
        }
    }

    mysql_query('DROP TABLE sorting_table');

    return $result;
}

print is_sorted(array(10, 20, 30, 40, 50));

VisioN

Posted 2014-02-27T16:33:02.227

Reputation: 4 490

+1 Because you are using the same concept of my answer to the sorting question

– Victor Stafusa – 2014-02-27T18:48:24.057

@Victor Oh, I haven't seen that answer! It seems to be rather popular :) Using DB for sorting values is the first thing that came to my mind. – VisioN – 2014-02-27T18:57:29.327

4

Would this work if Mrs. Roberts enters the values?

– user80551 – 2014-02-28T05:15:28.940

3@user80551 yes because there is no table called students – ratchet freak – 2014-02-28T11:26:57.563

@ratchetfreak I didn't mean literally, what about DROP TABLE sorting_table – user80551 – 2014-02-28T12:39:13.017

Definitely no sanitizing of inputs here. Mrs. Roberts could actually do SQL injection with each element of the array. But...that's code trolling. – Jonathan Van Matre – 2014-02-28T14:15:21.600

3@JonathanVanMatre Certainly security is one of the strongest sides of this code. – VisioN – 2014-02-28T14:53:57.023

I actuallyfound a function very similar to this in a live site a few months ago! The worst thing is by the standards of the guy who wrote the site it's actually pretty good – Matt Indeedhat Holmes – 2014-03-20T23:00:15.300

1This is my new favourite answer on this website; but for extra marks I'd love to see you use a PDO for security – alexandercannon – 2014-04-04T15:29:59.927

@a_programmer PDO is too mainstream :) – VisioN – 2014-04-04T16:54:50.223

17

C# - The power of statistics

What you really need to do to solve this is to re-frame the question in a way that makes the solution obvious. Because this is basically a "true-false" type question, what you are essentially asking is "how can I be 100% certain that the array is sorted?" If one word pops out of that question, it is the word "certain". What is the best way to measure certainty? You got it: statistics.

Other answers here only check to see if the array is sorted in one direction. This solution tests both ascending and descending order at the same time. The trick is to take an array of the same size that you already know is sorted (easy to make one yourself) and then find out how well the ordering of each array correlates with the other one. Calculating the Kendall tau rank correlation coefficient is the easiest way to do this:

using System;

namespace Homework
{
    class Example
    {
        static void Main(string[] args)
        {
            int[] n1 = { 23, 50, 16, 57, 19, 60, 40, 7, 30, 54 };
            int[] n2 = { 7, 16, 19, 23, 30, 40, 50, 54, 57, 60 };
            int[] n3 = { 60, 57, 54, 50, 40, 30, 23, 19, 16, 7 };

            Console.WriteLine(isSorted(n1));
            Console.WriteLine(isSorted(n2));
            Console.WriteLine(isSorted(n3));
        }

        static string isSorted(int[] a)
        {
            double t = 0;
            int n = a.Length;

            //Build a 'known' sorted array.
            int[] k = new int[n];
            for (int i = 1; i < n; i++)
            {
                k[i] = i;
            }

            //Find the Kendall's tau coefficient.
            //First the numerator...
            for (int i = 1; i < n; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    t += Math.Sign(a[i] - a[j]) * Math.Sign(k[i] - k[j]);
                }
            }
            //...then the denominator.
            int d = n * (n-1) / 2;
            //This gives the correlation coefficient.
            double sortedness = t / d;
            //1 is perfect correlation (ascending), -1 is perfectly non-correlated (descending).
            if (Math.Abs(sortedness) == 1)
            {
                return "Sorted";
            }
            else
            {
                return "Unsorted";
            }
        }
    }
}

Output:

Unsorted
Sorted
Sorted

This function is also very easy to extend the functionality of, as it would be trivial to add functionality like "Mostly sorted" or "More sorted than not" or "Completely random".

Edit

Almost forgot to go over the efficiency of the algorithm. This is currently O(7). There is one in the method name, one in each of the "for" keywords, one in the "double" declaration, and two in the uses of the variable "sortedness". You can improve this all the way down to O(0) (which is as low as you can go) by renaming the function, changing the double to a decimal, disemvoweling "sortedness" to "srtdnss", and converting the for loops to while loops.

Comintern

Posted 2014-02-27T16:33:02.227

Reputation: 3 632

2I painstakingly recalculated the complexity and determined it to be O(8). You're handwaving away the output, which I believe should factor in. To have a truly O(7) complexity, you might consider returning "ascending"/"haphazard", instead of "sorted"/"unsorted". – Geobits – 2014-03-01T07:03:55.190

@Geobits - I looked at it again, and of course you are correct. I guess this shows that there is a minimum complexity of O(1) when returning the strings. This is a small price to pay though, because returning a boolean is twice as bad. – Comintern – 2014-03-01T16:24:07.350

1+1 for the O() calculation. -1 for not also calculating a Spearman rho, because aren't two correlations better than one? And +1 for stats in C#, the proven favorite of statisticians. – Jonathan Van Matre – 2014-03-03T14:03:52.030

Please tell me the O(7) thing is a joke – mbatchkarov – 2014-03-04T13:43:17.217

@mbatchkarov - It's little O notation. :-) – Comintern – 2014-03-04T14:53:03.407

16

Ruby

Following strategy will eventually reveal if an array is sorted:

  1. A be an array (either sorted or unsorted, e.g. [1,2,3] or [1,3,2])
  2. P be an array holding all permutations of A
  3. If A is sorted, it is either the maximum or minimum of P (which basically are the sorted versions of A in Ruby)

Online version for testing.

class Array
   def is_sorted?
      permutations = permutation.to_a
      self == permutations.max || self == permutations.min
   end
end

David Herrmann

Posted 2014-02-27T16:33:02.227

Reputation: 1 544

1I don't think I understand the explanation. If the array is, e.g., [1, 9, 100], then the min is 10019 and the max is 91100, but the sorted number is 19100. Playing with the online version, max is [100,9,1] and min is [1,9,100]. I don't see where anything is being "represented by a number"; it looks like the arrays are just being ordered lexicographically. This would be the same, I suppose, if all the numbers are just one digit. – Joshua Taylor – 2014-02-27T19:02:03.827

"...either the maximum or minimum..." loved it. – microbian – 2014-02-27T19:08:02.810

@JoshuaTaylor: Thanks for the heads-up! I wanted to explain it in an easily understandable way - which ended up being plain wrong ;) I corrected my description... – David Herrmann – 2014-02-27T21:15:41.247

2@JoshuaTaylor the ruby methods Array#max and #min select the largest and smallest element with regards to the < and > operators. On Arrays, < and > implement lexicographical sorting. [1,9,100] is the minima of all ordered permutations of 1, 9 and 100 in the lexicographic ordering. – Karl Damgaard Asmussen – 2014-02-28T00:13:17.400

That's almost production quality. – primo – 2014-02-28T04:03:36.917

Please, use proper method name is_sorted?. This one make my eyes bleed. – Hauleth – 2014-03-03T00:30:50.993

Fixed - sorry, still adjusting to Ruby - I started learning it less than 2 weeks ago ;) – David Herrmann – 2014-03-03T16:56:35.060

What about permutation.minmax.include? self? Much better :) – LBg – 2014-03-03T23:06:51.717

12

C# - non-deterministic solution

This code probably works.

static bool isSorted(int[] s)
{
    var rnd = new Random();
    for (var i = 0; i < s.Length * s.Length * s.Length; i++)
    {
        var i1 = rnd.Next(0, s.Length);
        var i2 = rnd.Next(0, s.Length);
        if (i1 < i2 && s[i1] > s[i2] || i1 > i2 && s[i1] < s[i2])
            return false; // definitely not sorted
    }
    return true; // probably sorted
}

fejesjoco

Posted 2014-02-27T16:33:02.227

Reputation: 5 174

8If you set the number of iterations to -n^2*ln(1-p), you can ensure with a probability of p that all combinations will be checked! – Hannesh – 2014-02-27T22:20:25.893

And what values of p are valid for this solution to be accepted as "working code but trolling"? :) – fejesjoco – 2014-02-28T09:16:50.000

2

From http://stackoverflow.com/questions/2580933/, the chance of miscalculation of a comparison due to cosmic rays would be 0.0000018 (1.8e-6) every second. So if: 1) you can figure out how long an iteration takes, 2) We can use @Hannesh 's formula to calculate the probability, and then solve the system of equations to find the number of iterations that make your solution indistinguishable from a standard isSorted method.

– Xantix – 2014-03-03T08:03:47.143

11

Python

If the list is sorted, every number is either less than or equal to the next number. Therefore removing the left-most number will bring the average value up, otherwise the list isn't sorted. We will put this in a loop to check each number

def is_sorted(lst):
    def _avg(lst):
        return sum(lst)/(1.0*len(lst))
    for i in range(len(lst)-1):
        if _avg(lst[i:]) > _avg(lst[i+1:]):
            return False
    return True

is_sorted([1,2,3]) #True
is_sorted([3,2,1]) #False
is_sorted([1,4,3,2,0,3,4,5]) #False


The observant reader will notice that it doesn't exactly work like that.
is_sorted([1,4,3,2,0,3,4,11]) #False
is_sorted([1,4,3,2,0,3,4,12]) #True
is_sorted([1,2,1,2,1,2,1,2,99]) #True

VBCPP

Posted 2014-02-27T16:33:02.227

Reputation: 451

9

Bash

mkdir -p nums
mynums=(1 2 3 4)
for i in "${mynums[@]}"
do
     touch "nums/$i"
done

result=`ls -v nums`
resultarray=(${result})
for i in "${!resultarray[@]}"
do
    if [ ${resultarray[$i]} != ${mynums[$i]} ]; then
        echo "not sorted!"
        rm -rf nums/*
        exit 1
    fi
done
echo "sorted!"
rm -rf nums/*

touch a file for each element in the array, ls the directory and compare the ls result to the original array.

I am not very good with bash, I just wanted to give it a try :)

Zach Thacker

Posted 2014-02-27T16:33:02.227

Reputation: 211

Nice one, this assumes that the directory "./nums" already exists though. Maybe a "mkdir -p nums" somewhere? – camelthemammel – 2014-02-28T09:48:50.070

Oh, yeah that makes sense :P – Zach Thacker – 2014-02-28T13:13:21.273

8

C#

The notions of "smaller" or "bigger" are so much 2013. Real programmers only use the modulo operator!

private static void Main()
{
    List<int> list = new List<int> { 1, 5, 7, 15, 22};
    List<int> list2 = new List<int> { 1, 5, 15, 7, 22 };

    bool a = IsSorted(list); // true
    bool b = IsSorted(list2); // false
}

private static bool IsSorted(List<int> list)
{
    for(int i = 0; i % list.Count != list.Count() - 1; i++)
    {
        if (list[i] % list[i + 1] != list[i] &&
            list[i] != list[i + 1])
        {
            return false;
        }
    }
    return true;
}

Pierre-Luc Pineault

Posted 2014-02-27T16:33:02.227

Reputation: 331

What if the same number appears twice? Then list[i] % list[i+1] == 0. – Simon – 2014-02-27T19:57:26.323

@Simon Oh ho! Indeed, I guess two identical numbers are sorted. Added a comparison for this edge case. Nice find. – Pierre-Luc Pineault – 2014-02-27T20:14:41.070

5Glad to know that {0, -1, 2} is a sorted list. – Pierre Arlaud – 2014-02-28T14:16:25.117

9@ArlaudPierre If you want to be a real 2014 programmer, you have to put aside everything that is negative. The world is positive, the world is absolute, the world is modulo! – Pierre-Luc Pineault – 2014-02-28T15:28:55.140

@Pierre-LucPineault Now THAT is change I can believe in! – WernerCD – 2014-03-01T01:59:36.820

1Since you don't like the notion of "bigger" and "smaller", it's a shame you had to include those less-than and greater-than signs. You should have used arrays rather than lists. – Mr Lister – 2014-03-01T13:44:22.907

8

Scala

Checking if an array is sorted is easy! Just check if the first element is less than the second. Then sort the rest and see if they're equal.

Unfortunately, sorting is a difficult problem. There aren't many well-known or efficient algorithms for sorting an array; in fact it's a huge blind-spot in the current state of computer science knowledge. So I propose a simple algorithm: shuffle the array and then check if it's sorted, which, as already stated, is easy! Keep shuffling until it's sorted.

object Random {
  def isSorted(list: List[Int]): Boolean = {
    if (list.size <= 1) {
      true
    } else {
      sort(list.tail) == list.tail && list.head <= list.tail.head
    }
  }

  def sort(list: List[Int]): List[Int] = {
    val rand = new scala.util.Random()
    var attempt = list
    do {
      attempt = rand.shuffle(attempt)
    } while (!isSorted(attempt))
    attempt
  }

  def main(args: Array[String]): Unit = {
    println(isSorted(List(1, 2, 3)))
    println(isSorted(List(1, 3, 2)))
    println(isSorted(List(1, 2, 3, 4, 5, 6, 7, 8)))
  }
}

I assume this outputs "true, false, true". It's been running for a while now...

Joe K

Posted 2014-02-27T16:33:02.227

Reputation: 1 065

8

A sorted array of integers has the property that every sub-array (say elements n through m of the array) is also a sorted array of integers. This obviously implies that the best method is a RECURSIVE function:

bool isSorted_inner(const std::vector<int> &array, int start, int length){
    if (length == 2){
        if (array[start] < array[start+1]){
            return true;
        }else{
            return false;
        }
    }else{
        return isSorted_inner(array, start, length-1) && isSorted_inner(array, start+1, length-1);
    }
}

bool isSorted(const std::vector<int> &array){
    return isSorted_inner(array, 0, array.size());
}

It may not be the fastest method but it is none-the-less a VERY ACCURATE test of whether or not a list is ordered. It is also incredibly easy to read and understand this code because it uses a FUNCTIONAL paradigm, and is therefore free of the horrors of state changing and iterative loops.

I hope this will be useful information for you.

Allen

Posted 2014-02-27T16:33:02.227

Reputation: 81

6

C# - longest increasing subsequence

For a sorted array, the length of the longest increasing subsequence is equal to the length of the array. I copied the algorithm from here, only modified it to be non-decreasing instead of increasing.

static bool isSorted(int[] s)
{
    return s.Length == LongestIncreasingSeq(s);
}

static public int LongestIncreasingSeq(int[] s)
{
    int[] l = new int[s.Length];  // DP table for max length[i]
    int[] p = new int[s.Length];  // DP table for predeccesor[i]
    int max = int.MinValue;

    l[0] = 1;

    for (int i = 0; i < s.Length; i++)
        p[i] = -1;

    for (int i = 1; i < s.Length; i++)
    {
        l[i] = 1;
        for (int j = 0; j < i; j++)
        {
            if (s[j] <= s[i] && l[j] + 1 > l[i])
            {
                l[i] = l[j] + 1;
                p[i] = j;
                if (l[i] > max)
                    max = l[i];
            }
        }
    }
    return max;
}

fejesjoco

Posted 2014-02-27T16:33:02.227

Reputation: 5 174

6

Stonescript (c) LMSingh - 0 minus (4102 palindromed).

Following is written in Stonescript(c), a language copyrighted and used by me many centuries ago, i.e. in olden times before the midgetframes. NOTE: It is a precursor to Sanskrit.

1. Find a very straight stick in the jungle.  
2. Sum up all the values of the array elements and find that many equal sized stones.  
3. Line up all the values of the array along the side of straight stick from step 1. Each value is to be represented by number of stones for each array element like so...  

Example of an array with 8 elements. Sorted in descending order :-)

o
oo
oo
oooo
ooooo
ooooo
ooooo
oooooo
ooooooo
oooooooo
========
12345678

-- Code continued.

4. E-ball-uate. (In Shakespearean English that means Eye ball it.)  
  4.1 Run your eye from array position 1 top towards array position 8 top.  
  4.2 If it looks sorted, then it is.  
  4.2.1 Start jumping up and down and thumping chest.  
  4.2.2 Go to happy end.  
  4.3 If something isn't quite right, like in case of example below then it isn't.  
  4.3.1 Kick the stones in frustration and anger! Cuz it really is not sorted!  
  4.3.2 Go to sad end.  

Example of an array with 8 elements. Not sorted :-(

o
oo
oo
oo o
ooooo
ooooo
ooooo
oooooo
ooooooo
oooooooo
========
12345678

-- Code continued.

5. Sad end.  
  5.1 Eat an apple.  
  5.2 Fall from grace to next line.  
6. Happy end.  

=-=-=-=-=-=
On further optimization, step 4 punch leaves can be replaced with the following punch leaves.
=-=-=-=-=-=

4. Roll a stone from top of position 1 towards top of position 8, pushing the rolling stone towards the top stone for each position while moving to the right.  
  4.1 If rolling stone reaches the position 8 then it's sorted.  
  4.1.1 Start jumping up and down and thumping chest.  
  4.1.2 Go to happy end.  
  4.2 If the rolling stone gets stuck in a trough, then it isn't.  
  4.3.1 Kick the stones in frustration and anger!  
  4.3.2 Go to sad end.  

=-=-=-=-=-=
For you all code sleuths and power debuggers out there, I've intentionally added a bug in the above second variation of step 4. Can you find it?

LMSingh

Posted 2014-02-27T16:33:02.227

Reputation: 171

3I found the bug - all 4.3.* should be 4.2.* – Timtech – 2014-03-03T18:26:28.817

4

Javascript

This is what made you shocked about the "creativity":

  • Because for a sorted array

    * all the elements on the left side of any element must be smaller 
    * all the elements on the right side of any element must be bigger
    
  • Therefore, run a main loop for all elements and check the above two conditions by running two nested loops inside the main one (one for left side and one for right side)

So, i give a javascript implementation of the described algorithm:

function checkArraySorted(array) {
  for (a = 0; a < array.length; a++) {
    for (b = 0; b < a; b++) {
       if (array[b] > array[a]) return false;
    }
    for (b = a + 1; b < array.length; b++) {
       if (array[b] < array[a]) return false;
    }
  }
  return true;
}

Lets test it:

checkArraySorted([]);
> true

checkArraySorted([1]);
> true

checkArraySorted([1, 2]);
> true

checkArraySorted([2, 1]);
> false

checkArraySorted([1, 2, 3]);
> true

checkArraySorted([1, 2, 3, 4]);
> true

Seems to work perfectly! It has a complexity of O(n²), ideal for an algorithm that should be O(n), but by doing O(n²) it becomes more efficient, since this is a measure of efficiency, so O(n²) is more efficient than O(n).

Victor Stafusa

Posted 2014-02-27T16:33:02.227

Reputation: 8 612

I didn't mean to use a 'mid'. The first nested loop was from 0 to a, and the second was supposed to be from a+1 to length. BTW, 1,2,3 should be sorted, isn't it? – microbian – 2014-02-27T18:50:15.957

@microbian Ok, edited. – Victor Stafusa – 2014-02-27T18:57:35.523

4

C

Hereafter, "sorted" means "sorted in ascending order".

An array is not sorted iff a[i]>a[i+1]

So if we let x=a[i]-a[i+1], x will be positive iff the array is not sorted.

To test for x being positive, we can break it down into two parts: x is not negative, and x is not zero

A simple test for whether x is negative is that we test whether x*x is equal to x*abs(x). This condition should be false if x is negative, since (-1)*(-1)==1.

To test for zero, we can use another simple test: 0./(float)x is Not a Number iff x is zero.

So here's the entire code: (assumes the array has 5 elements)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main() {
    int i, a[5];
    for(i=0;i<5;i++) scanf("%d",&a[i]);
    int sorted=1;
    for(i=0;i<4;i++) {
        int x=a[i]-a[i+1];
        if(x*x==x*abs(x)&&!isnan(0./(float)x)) {
            sorted=0;
            break;
        }
    }
    puts(sorted?"sorted":"not sorted");
    return 0;
}

user12205

Posted 2014-02-27T16:33:02.227

Reputation: 8 752

Actually, testing for a[i]-a[i+1] > 0 is already problematic. Don't need to do all those kinds of stuffs. – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ – 2014-02-28T09:15:05.310

Doing unnecessary stuff is the whole point of code trolling, isn't it? (And what do you mean by problematic?) – user12205 – 2014-02-28T11:01:43.620

1Signed integer overflow is UB. Even if we define wrap around behavior, if we do INT_MAX - INT_MIN then the result will be a negative number (replace a[i] with INT_MAX and a[i+1] with INT_MIN). – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ – 2014-02-28T14:29:02.113

Since it is only a homework problem, let's assume that the teacher won't give so many extreme numbers. – user12205 – 2014-02-28T14:42:45.123

OK. Just that I prefer to troll + being evil. – n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ – 2014-02-28T14:44:40.253

4

It is all about how certain you wish to be. Since no certainty was given the following is actually quite good performance wise. The code below gives a good guess, but if you are sure you should repeat the function a couple of times. If you wish to be really sure, you should run it in a loop and do it a dozen of times. Perfect scalability!

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static const int size = 100;

int issorted(int *array, int size)
{
    int idx = random() % size;
    return (array[idx] >= array[0]);
}

void check_array(int *array, int size)
{
    if (issorted(array, size)) {
        puts("The array is sorted but I am not 100% sure.");
    } else {
        puts("The array is definitely not sorted in ascending order.");
    }
}

int main(void)
{
    int *array = malloc(sizeof(int) * size);
    int i = 0;

    srand(time(NULL));

    for (i = 0; i < size; i++) {
        array[i] = random();
    }

    check_array(array, size);

    for (i = 0; i < size; i++) {
        array[i] = i + 1;
    }

    check_array(array, size);
    free(array);

    return 0;
}

Isn't this a treat?

n0la

Posted 2014-02-27T16:33:02.227

Reputation: 101

4

C

int is_sorted(int *T, int n)
{
return false;
}

Works with probability 1-(1/n!) and complexity O(1). Obviously the best method for very large random arrays.

As the complexity is only O(1), for a better estimation, run twice.

cpri

Posted 2014-02-27T16:33:02.227

Reputation: 727

3

C

This function does more than just tell you if the array is sorted. It tells you how many elements are in the right place. It can be used for any type of data.

Note the importance of using descriptive variable names to make your code easy to follow. On the other hand, we do not need to declare the variable i, as it is bound to be declared somewhere else in the program.

int sortcheck(array_to_be_checked[10])
{
  int number_of_elements_in_right_place=0;

  for (i = 1; i = 10; i++)
    number_of_elements_in_right_place += i == array_to_be_checked[i];

  return number_of_elements_in_right_place;
}

Edit: This is a better way for larger arrays. The advantage of this is that it is similar to the way a human would check.

int sortcheck(array_to_be_checked[32767])
{
  i=rand(); j=rand();
  while( (array_to_be_checked[i] > array_to_be_checked[j]) = (i > j) ) 
  {
    printf("I think it's sorted");
    i=rand(); j=rand();
  };
  printf("It wasn't sorted");
}

Level River St

Posted 2014-02-27T16:33:02.227

Reputation: 22 049

1"We do not need to declare the variable i, as it is bound to be declared somewhere else in the program." was worth a laugh. – Jonathan Van Matre – 2014-02-27T22:53:36.130

@JonathanVanMatre Thanks but it's by no means the only thing wrong with this code. – Level River St – 2014-02-27T22:55:45.547

3

JavaScript + more statistics

I liked the solution suggested by @Cominterm a lot. But comparing to an already sorted list? That's cheating!

Instead, I calculate the array's autocorrelation (correlation between the array and the array left shifted one position). Then, I shuffle the array lots of times and each time compare it's new autocorrelation to the original autocorrelation. If the array was sorted, the original autocorrelation would be the highest most of the time!

http://jsfiddle.net/dB8HB/

Bonus: If your p-value < 0.05, the output will automate the task of claiming that the array is sorted for you. What more could you ask for?

Bonus2: Although this implementation uses JavaScript's O(n) array functions for convenience, the approach could use sampling to run in constant time!

<form name="out"><textarea name="put" cols="80" rows="3">Press the button</textarea></form> 
<button onclick="startstop();">The button</button>
<script>
var iid=input=0, my=document.forms, isit={'true':0.5,'false':0.5}, ownAutocorr;
function startstop(){
     if(iid){
        clearInterval(iid);
        if(1 - isit.true / (isit.true+isit.false)<0.05){my.out.put.value+="\nYour array is sorted! (p<0.05)";}
        iid=input=0;isit={'true':0.5,'false':0.5}
     }
     else   {
        input=JSON.parse("["+prompt("Comma separated integers")+"]");
        ownAutocorr=pearsonCorrelation(input,cloneShiftArray(input));
        iid=setInterval(trial,50);
    }
}

function trial(){

 var newArr=shuffle(input.slice(0));
 var newAutocorr=pearsonCorrelation(newArr,cloneShiftArray(newArr));
 isit[newAutocorr<ownAutocorr]++;
 my.out.put.value="Your array is sorted with probability " + (isit.true / (isit.true+isit.false)).toFixed(2);
}

function cloneShiftArray(oldArr){
    var newArr=oldArr.slice(0); //clone the array
    var len=oldArr.length;
    //shift the array one
    for(var l=0;l<len-1;l++){
     //performance is important so we'll use bitwise operators
     newArr[l]^=newArr[l+1];
     newArr[l+1]^=newArr[l];
     newArr[l]^=newArr[l+1];
    }
    newArr[l]+=newArr[l-1   ];
    return newArr;
}
function pearsonCorrelation(p1, p2) { //Borrowed from teh interwebs
  var len = p1.length;
  var sum1=sum2=sum1Sq=sum2Sq=pSum = 0;
  for (var l = 0; l < len; l++) sum1 += p1[l];
  for (var l = 0; l < len; l++) sum2 += p2[l];
  for (var l = 0; l < len; l++) sum1Sq += Math.pow(p1[l], 2);
  for (var l = 0; l < len; l++) sum2Sq += Math.pow(p2[l], 2);
  for (var l = 0; l < len; l++) pSum += p1[l] * p2[l];
  var num = pSum - (sum1 * sum2 / len);
  var den = Math.sqrt((sum1Sq - Math.pow(sum1, 2) / len) *
      (sum2Sq - Math.pow(sum2, 2) / len));
  if (den == 0) return 0;
  return num / den;
}
function shuffle(array) {//also borrowed
  var currentIndex = array.length, temporaryValue, randomIndex;
  while (0 !== currentIndex) {
    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex -= 1;
    temporaryValue = array[currentIndex];
    array[currentIndex] = array[randomIndex];
    array[randomIndex] = temporaryValue;
  }
  return array;
}
</script>

Fabio Beltramini

Posted 2014-02-27T16:33:02.227

Reputation: 131

3

JavaScript/SVG - sunDialsort

This solution does not use the <,<=,> or >= comparators. I've attempted to make it read as little like a sort function as possible.

Method

  • Plot the values as dots along an arc.
  • For an ascending array each value will make the total width of the drawing wider and not decrease the starting X (exception: two identical values).
  • As width can't shrink a != will suffice,
  • As X cannot increase an == will suffice.
  • to fix for two identical values each dot is actually a line, of increasing length. Where the unit length is less than 1/number of values.

Trolling

I've added the following face-palms along the journey of reading this very bad code.

  • function may look like its going to sort the array, named it sunDialsort (bonus bad capitalization)
  • used lit-geek reference for all variable names
  • used the regex hammer to count the number of elements in the array
  • used an alert box
  • the solution for the edge case where 2 consecutive variables are the same doubled the amount of code (a one liner could have sorted it), put lots of this code early to confuse the purpose of the function.
  • instead of finding the min and max find the longest number and round up to the next power of ten, hopefully this will throw people off the scent.

xml

<body>
<svg id="dial" height="400" width="400" transform=""></svg>
</body>

function

sunDialsort = function (values)
{
    var twas = values.toString();  
    var brillig = twas.match(/,/g).length + 1; //<1>
    //find the sig figs we are working with (longest number)
    var and = [], the = 0;
    for (var jabberwock = 0; jabberwock < twas.length; jabberwock++)
    {
        switch (twas.charAt(jabberwock))
        {
        case ("."):
            break; //dont count
        case (","):
            and.push(the);
            the = 0;
            break;
        default:
            the++;
        }
    }
    and.push(the);
    var slithy = Math.max.apply(Math, and);
    //assume did/toves based on number of characters
    var toves = Math.pow(10, slithy);
    var did = toves * -1;
    console.log(did + "," + toves + "," + brillig);
    //for each number make a horizontal svg line of length (jabberwock*acuuracy)     
    var gyre = 1 / brillig;
    var gimble, wabe, all, mimsy, were, borogoves, mome, raths;
    var outgrabe = true;
    for (jabberwock = 0; jabberwock < brillig; jabberwock++)
    {
        gimble = document.createElementNS('http://www.w3.org/2000/svg', 'path');
        gimble.setAttribute("stroke", "blue"); //green is not a creative colour
        gimble.setAttribute("d", "M0 20 h " + (jabberwock * gyre));
        wabe = (values[jabberwock] - did) / (toves - did);
        mimsy = 90 - (wabe * 180);
        gimble.setAttribute("transform", "rotate(" + mimsy + ")");
        document.getElementById("dial").appendChild(gimble);
        borogoves = document.getElementById("dial").getBBox();
        if (mome)
        {
            raths = (borogoves.width != all && were == borogoves.x);
            console.log("test " + raths);
            all = borogoves.width;
            if (!raths)
            {
                outgrabe = false
            }
        }
        else
        {
            were = borogoves.x;
            all = borogoves.width;
            mome = true;
        }
    }
    return outgrabe
};
alert(sunDialsort([1, 2, 3, 3, 4341, 556]));

If anyone wants to test there is a version here with readable variable names. http://jsfiddle.net/outRideACrisis/r8Awy/

OutRideACrisis

Posted 2014-02-27T16:33:02.227

Reputation: 131

3

C

As a binary search only works on sorted arrays, to check if an array is sorted, all we need to do is verify that a binary search works for all elements of the array. If it fails to find any element, we know the array is not sorted.

The command-line arguments passed must all be decimal integers without leading zeroes.

#include <stdlib.h>
#include <string.h>

int compar(const void *a, const void *b) {
  char *const *sa = a, *const *sb = b;
  int cmp = strlen(*sa) - strlen(*sb);
  if (cmp == 0) cmp = strcmp(*sa, *sb);
  if (cmp == 0) cmp = sa - sb;
  return cmp;
}

int main(int argc, char *argv[]) {
  if (argc-- && argv++) {
    for (int i = 0; i != argc; i++) {
      if (bsearch(argv+i, argv, argc, sizeof *argv, compar) != argv+i) {
        return 1;
      }
    }
  }
  return 0;
}

hvd

Posted 2014-02-27T16:33:02.227

Reputation: 3 664

3

Javascript

a = prompt("Please enter the data");
r = prompt("Does your array arouse moral distaste and contempt?");
if ((/yes/i).test(r))
  alert("The array is sordid.");

Jason C

Posted 2014-02-27T16:33:02.227

Reputation: 6 253

1

{69, 313, 187, 31338}

– Geobits – 2014-03-05T14:33:03.237

2

C

  • Make a copy of the array
  • sort the copy in descending order
  • check if this array is the reverse of the given array
    #include<stdio.h>
    #include<stdlib.h>
    #include <stddef.h>
    #include<string.h>
    int main(){
     int arr[100],i,j,temp;
     int a[] = {1,2,3,4,5,6,7,8,9,10};
     char b[256];

     printf("Loading the program please wait...");
      int s = sizeof(a)/sizeof(a[0]);
     for(i=0; i<999999999; i++);//best way to make the program more realistic
     system("cls");

     for(i=0;i<s; i++ )
     arr[i] = a[i];

     for(i=0;i<s;i++){
          for(j=i;j<s;j++){
               if(arr[i] < arr[j]){
               temp=arr[i];
               arr[i]=arr[j];
               arr[j]=temp;
               }
           }
     } //sorting array in descending order

     int p = 0;
     for(i=0; i<s; i++)
     {
         if (a[s-i-1] != arr[i])
         p++;
     }

     if(p>0)
     printf("No");
     else
     printf("yes");
     getch();


     }

Mhmd

Posted 2014-02-27T16:33:02.227

Reputation: 2 019

2

T-SQL

Database sorting without an ORDER BY clause. I happen to use a string splitter popularized by SQL MVP Jeff Moden, but just about any splitter will do. The magic occurs with a self MERGE join, causing a hidden sort.

EDIT: fixed to sort numerically instead of lexicographical.

USE [Trashcan]; -- or [tempdb]
GO
CREATE PROCEDURE [dbo].[IsArraySortedOrTrash]
    @array VARCHAR(8000) -- comma delimited array
AS

SELECT -- convert array into table
    [ItemNumber] AS [raw_order],-- index in base array
    CAST([Item] AS INT) AS [Item] -- value at index
INTO #raw_array
FROM [dbo].[DelimitedSplit8K](@array,',') A; -- any string splitter will work

SELECT -- magic
    A.[raw_order],A.[Item], 
    IDENTITY(INT,1,1) [sorted_order] 
INTO #tmp
FROM #raw_array A
INNER MERGE JOIN #raw_array B
ON      A.[item] = B.[item];

SELECT -- output
    CASE 
        WHEN EXISTS (SELECT * FROM #tmp WHERE [raw_order] != [sorted_order])
        THEN 'Trash'
        ELSE 'Sorted'
    END [is_sorted]

DROP TABLE #tmp; -- cleanup
GO

-- test solution
USE [Trashcan];
EXECUTE [dbo].[IsArraySortedOrTrash] '1,2,3,42'; -- Output: Sorted
EXECUTE [dbo].[IsArraySortedOrTrash] '42,3,2,1'; -- Output: Trash

CElliott

Posted 2014-02-27T16:33:02.227

Reputation: 121

Upvote for my SQL compadre. Welcome! – Jonathan Van Matre – 2014-02-27T22:32:39.553

2

Mathematica

This algorithm seems to work, but it is a bit slow. There may be quicker ways to sort but I haven't found them.

  1. Take a random ordering of the list and check whether it is in order (with OrderedQ).
  2. If it is, stop. Otherwise, repeat step 1.

The following code sorted the list in just over 18 seconds.

a = {23, 50, 16, 57, 19, 60, 40, 7, 30, 54};
n = 1;
Timing[While[! OrderedQ[a], a = RandomSample[a]; n++]]
n
a

{18.581763, Null}
8980699
{7, 16, 19, 23, 30, 40, 50, 54, 57, 60}

DavidC

Posted 2014-02-27T16:33:02.227

Reputation: 24 524

The task was to check if the input is already sorted. – Ilmari Karonen – 2014-02-28T18:41:58.277

This is the essential idea behind my solution (though, I use a quadratic-time OrderedQ just for funsies) with the added check at the end "now that we've got a sorted one, is it what we started with?" – boothby – 2014-02-28T18:45:55.143

2

JavaScript

function isSorted(arr) {
    if (arr.length === 1 && typeof arr[0] !== 'number' || arr[0].toString().indexOf('.') !== -1 || arr[0] > (-1 >>> 0) || arr[0] !== arr[0] || arr[0] === Infinity) {
        // Return false in the case of one non-number element.
        // isSorted returns false for arrays containing non-numbers for consistency
        // with PHP, but that doesn’t work for one element, so that’s the purpose
        // of this check.
        return false;
    }

    var obj = {};
    var i;

    for (i = arr.length; i--;)
        obj[arr[i]] = true;

    for (var x in obj)
        if (arr[++i] != x) return false;

    return true;
}

This function may return false incorrectly, but not on modern browsers; you can check for this and provide a slower fallback (as described in the question) if necessary:

var isModern = /chrome/i.test(typeof navigator === 'object' && navigator.userAgent);

if (!isModern) {
    isSorted = function() {
        // I develop on good browsers, so the implementation is left as an exercise
        // to the reader if he or she wants to support outdated browsers.
    };
}

They say this gives unpredictable results on negative numbers, but what it’s really all up to is how good you are at predicting things.

Ry-

Posted 2014-02-27T16:33:02.227

Reputation: 5 283

2I wish Chrome would shuffle object properties to prevent people from doing things like this… – Bergi – 2014-03-02T13:29:43.983

2

Java (Levenshtein Distance)

In this implementation, I clone the original array and sort the cloned instance. Then, the Levenshtein distance is calculated. If it is zero, then the original array was sorted.

Note: The getLevenshteinDistance() implementation is taken from Jakarta Commons Lang and modified to work on int[] instead of CharSequence.

import java.util.Arrays;

public class CheckSorting {

    public boolean isSorted(int[] array) {
        int[] sortedArray = Arrays.copyOf(array, array.length);
        Arrays.sort(sortedArray);

        return CheckSorting.getLevenshteinDistance(array, sortedArray) == 0;
    }

    public static int getLevenshteinDistance(int[] s, int[] t) {
        int n = s.length;
        int m = t.length;

        if (n == 0) {
            return m;
        } else if (m == 0) {
            return n;
        }

        if (n > m) {
            int[] tmp = s;
            s = t;
            t = tmp;
            n = m;
            m = t.length;
        }

        int p[] = new int[n + 1];
        int d[] = new int[n + 1];
        int _d[];

        int i;
        int j;

        int t_j;

        int cost;

        for (i = 0; i <= n; i++) {
            p[i] = i;
        }

        for (j = 1; j <= m; j++) {
            t_j = t[j - 1];
            d[0] = j;

            for (i = 1; i <= n; i++) {
                cost = s[i - 1] == t_j ? 0 : 1;
                d[i] = Math.min(Math.min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost);
            }

            _d = p;
            p = d;
            d = _d;
        }
        return p[n];
    }
}

user3001267

Posted 2014-02-27T16:33:02.227

Reputation: 171

2

C

Obviously, if an array is sorted, the smallest element comes first. After we verified this, all we have to do is to test whether the rest of the array is sorted, too.

So what is left is to find the smallest element of an array, also known as its minimum. Clearly this can be done using a divide-and-conquer strategy: Just find the minimum of the first half, and the minimum of the second half, and then return the smaller of the two.

Therefore we arrive at the following code:

/**********************************************/
/*                                            */
/* get the minimal value in an integer array. */
/*                                            */
/* Arguments:                                 */
/*   array: a pointer to the array            */
/*   length: the length of the array          */
/*                                            */
/* Returns:                                   */
/*   the minimal value in the array.          */
/*                                            */
/* Preconditions:                             */
/*   array must be a valid pointer            */
/*   length must be at least 1                */
/*                                            */
/**********************************************/
int minimum(int* array, int length)
{
  /* special case: only one element in the array */
  if (length == 1)
  {
    /* the only value is of course the minimal one */
    return *array;
  }

  /* When we get to here, then length > 1, therefore length/2 > 0 */
  int half = length/2;

  /* get the minimum length of the first half of the array */
  int min1 = minimum(array, half);

  /* get the minimum length of the secons half of the array */
  int min2 = minimum(array + half, length - half);

  /* return the smaller of them */
  if (min1 < min2)
    return min1;
  else
    return min2;
}

/********************************************/
/*                                          */
/* Test if an array is sorted.              */
/*                                          */
/* Arguments:                               */
/*   array: a pointer to the array          */
/*   length: the length of the array        */
/*                                          */
/* Returns:                                 */
/*   1 if the array is sorted, 0 otherwise. */
/*                                          */
/* Preconditions:                           */
/*   array must be a valid pointer          */
/*   length must be at least 0              */
/*                                          */
/********************************************/
int is_sorted(int* array, int length)
{
  /* special case: empty array */
  if (length = 0)
  {
    /* the empty array is certainly sorted */
    return 1;
  }

  /* get minimal element (note that at this point, length > 0) */
  int min = minimum(array, length);

  /* is the minimal element the first? */
  if (min == *array)
  {
    /* if so, test if the rest of the array is sorted */
    int rest_is_sorted = is_sorted(array + 1, length - 1);

    if (rest_is_sorted)
    {
      /* if the rest is also sorted, the whole array is sorted */
      return 1;
    }
    else
    {
      /* otherwise, the array is clearly not sorted. */
      return 0;
    }
  }
  else /* if the first element is not the smallest */
  {
    /* then obviously the array is not sorted */
    return 0;
  }
}

celtschk

Posted 2014-02-27T16:33:02.227

Reputation: 4 650

2

C#

Because I've never met a String function I didn't love, this one goes out to String.Length

String Trolling

    public static bool isSorted(int[] input)
    {
        for (int i = 0; i < input.Length-1; i++)
        {
            string strThis = ((long)(input[i] * Math.Pow(10, input[i]))).ToString();
            string strNext = ((long)(input[i+1] * Math.Pow(10, input[i+1]))).ToString();
            Console.WriteLine(" this: " + strThis);
            Console.WriteLine(" next: " + strNext);
            if (strThis.Length > strNext.Length)
            {
                return false;
            }
        }
        return true;
    }

Console.WriteLine(isSorted(new int[]{0,1,2,3,4,5,6,7,8,9,10,11,12})); Outputs:

 this: 0
 next: 10
 this: 10
 next: 200
 this: 200
 next: 3000
 this: 3000
 next: 40000
 this: 40000
 next: 500000
 this: 500000
 next: 6000000
 this: 6000000
 next: 70000000
 this: 70000000
 next: 800000000
 this: 800000000
 next: 9000000000
 this: 9000000000
 next: 100000000000
 this: 100000000000
 next: 1100000000000
 this: 1100000000000
 next: 12000000000000
True

...sure this will encounter overflow problems pretty quickly and choke on negative numbers but that's nothing we can't fix in production, right?!

Edit:

Turns out we can use System.Numerics.BigInt to test sortedness of numbers up to an integer value of 301 before Math.Pow just starts returning Double.Infinity.

    strThis = (new BigInteger(input[i])*new BigInteger(Math.Pow(10, input[i]))).ToString();
    strNext = (new BigInteger(input[i+1]) * new BigInteger(Math.Pow(10, input[i+1]))).ToString();

Looks good enough to me:

  this: 300000000000000015751428076561326074611340574332447746474756234653540737396672458735911412524134359213111333149865163453082756970608129172693437655436012094854516160277972741121349070138436427017810685970491239983524335711690292264022395822834042748373777636646017052851434700841658916059637820162048000
  next: 3010000000000000158039328368165304948600450429135559056296720887690525398546613669316977838992148070771550375936980473312596994938434896032690824476207988018373645474788993169250869003722312151078700549237262107834694168307292599049024704755768228908683568954348371096942728165111311124465032795625881600

Edit 2:

Customers started having mysterious problems with the checkout process after we reached 302 items in our inventory database. After initially blaming the customer, we were able to isolate a problem with our use of the Math.Pow function and have switched to using a custom BigIntPow function for sortedness determinations. Runtime CPU usage has increased dramatically but we are now able to handle any number of positive integers.

public static BigInteger BigIntPow(BigInteger number, BigInteger positiveExponent)
{
     BigInteger returnInt = new BigInteger();
     returnInt = number;
     for (BigInteger i = new BigInteger(0); i < positiveExponent; i++)
     {
         returnInt = returnInt*number;
     }
     return returnInt;
}

nvuono

Posted 2014-02-27T16:33:02.227

Reputation: 511

Clever answer. Warning: you may be getting a lawsuit from @LMSingh for essentially implementing their "Line up stones next to a log" algorithm in C#. Welcome to PPCG! – Jonathan Van Matre – 2014-03-03T23:17:40.120

What if our patent application is titled "A Stone-less Method for Determining Sortedness"? – nvuono – 2014-03-04T14:50:59.723

2

Without any code.

1:  Fit a curve to the data.  This will be a polynomial of degree arr.length - 1;
2:  Take the derivative of the polynomial.
3:  Test that the derivative is positive at an arbitrary point. (i.e. it's increasing SOMEWHERE)
4:  Take the second derivative 
5:  Evaluate the second derivative over every point in the domain and show that it doesn't change sign.

Chris Cudmore

Posted 2014-02-27T16:33:02.227

Reputation: 121

2

C# WPF

SortCheck LineRider

Now that i got your attention, here is what i did:

  • First we reverse the Array
  • We create a Border control for each Number of height = number and width = 100, placed in a WPF window and align them on the bottom left corner next to eachother
  • Now we create an Image control which starts in the top left corner and drops until it hits the first Border
  • If we hit a Border we move to the right
  • Now if the next Border arrives we drop again and ride again etc.
  • If a Border is higher than we are we stop, the value is higher than the previous one -> not Sorted
  • If we ride into the Sunset (the end) -> Sorted

MainWindow.xaml:

<Window x:Class="WPFLinerider.MainWindow"
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
    Title="MainWindow" Height="Auto" Width="Auto" WindowState="Maximized" Loaded="Window_Loaded">
<Grid Name="MainGrid">
    <ScrollViewer>
        <Grid Name="LineRiderGrid">
            <Image Name="LineRider" Source="Images/LineRider.png" Height="50" Width="50" HorizontalAlignment="Left" VerticalAlignment="Top" Canvas.Top="0" Canvas.Left="0" />
            <DockPanel Name="TrackDockPanel" VerticalAlignment="Bottom" HorizontalAlignment="Left" />
        </Grid>
    </ScrollViewer>
</Grid>

Mainwindow.xaml.cs

using System;
using System.Collections.Generic;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Media;
using System.Windows.Threading;

namespace WPFLinerider
{
public partial class MainWindow : Window
{
    public List<Vector> track;
    public int LineRiderPosition = 0;
    DispatcherTimer tempDisTimer;
    public MainWindow()
    {
        InitializeComponent();

        int[] array = { 0, 15, 200, 20, 50, 70, 80, 90, 100, 101, 130 };
        Array.Reverse(array);
        CreateTrack(array);
    }

    private void Window_Loaded(object sender, RoutedEventArgs e)
    {
        Ride();
    }

    public void Ride()
    {
        tempDisTimer = new DispatcherTimer();
        tempDisTimer.Interval = new TimeSpan(10000);
        tempDisTimer.Tick += tempDisTimer_Tick;
        tempDisTimer.Start();
    }

    void tempDisTimer_Tick(object sender, EventArgs e)
    {
        UpdatePosition();
    }

    public void UpdatePosition()
    {
        if (track != null)
        {
            if (TrackDockPanel.Children.Count > (int)(LineRiderPosition / 100))
            {
                Point relativeTrackPoint = TrackDockPanel.Children[(int)(LineRiderPosition / 100)]
                    .TransformToAncestor(LineRiderGrid).Transform(new Point(0, 0));

                if (relativeTrackPoint.Y < LineRider.Margin.Top + 50)
                {
                    tempDisTimer.Stop();
                    MessageBox.Show("False");
                    return;
                }

                if (relativeTrackPoint.Y > LineRider.Margin.Top + 50)
                {
                    LineRider.Margin = new Thickness(LineRider.Margin.Left, LineRider.Margin.Top + 1, 0, 0);
                    return;
                }

                LineRider.Margin = new Thickness(LineRider.Margin.Left + 1, LineRider.Margin.Top, 0, 0);
                LineRiderPosition++;

                return;
            }

            tempDisTimer.Stop();
            MessageBox.Show("True");
            return;
        }
    }

    public void CreateTrack(int[] heights)
    {
        track = new List<Vector>();

        foreach(var entry in heights)
        {
            track.Add(new Vector(1, entry)); 
        }

        foreach(var entry in track)
        {
            Border trackBorder = new Border();
            trackBorder.Background = new SolidColorBrush(Colors.Blue);
            trackBorder.Width = entry.X * 100;
            trackBorder.Height = entry.Y;
            trackBorder.VerticalAlignment = System.Windows.VerticalAlignment.Bottom;

            TrackDockPanel.Children.Add(trackBorder);
        }
    }
}

}

Background Idea:

First i thought about using Interpolation to create a function based on the array using numeric math, the exam i failed twice and write again on Monday in a week. This function could then be checked to be rising continually with some deriving -> sorted.

But fuck numerics I think graphic aproaches are best aproaches.

If someone is interested i can upload the whole Solution or a Video of it working.

enter image description here

Master117

Posted 2014-02-27T16:33:02.227

Reputation: 389

1

Java

If a > b then -a < -b. Is this creative enough? ;D

public static boolean isSorted(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        if (-arr[i - 1] < -arr[i]) {
            return false;
        }
    }
    return true;
}

This works well... until Integer.MIN_VALUE appears in the array arr.

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳

Posted 2014-02-27T16:33:02.227

Reputation: 5 683

1

Python

# the way we solve the ascending array of integers problem is that we observe
# that in an array that is sorted in ascending order we know that the largest
# item will always be last.  We start by checking that the largest item is
# last.  We also observe that an array that is in ascending order is made up of
# tinier arrays that are also all in ascending order, so we define our
# is_asending function to recursively check if the beginning of the array we're
# looking at is also ascending, and define a base case that an array of length
# zero or one is definitely ascending.


# gets the largest value found in the array of items
def largest(items):
    if len(items) < 1:
        raise TypeError("no you see the items has to be not empty")
    # if the array only has one item, it is the largest
    if len(items) == 1:
        return items[0]
    return really_largest(items)

# don't call this function!!!!!! only largest should call this.
def really_largest(items):
    # really, I mean it!
    big = items[0]
    for item in items:
        if item > big:
            big = item
    # you shouldn't even be here!
    return big

# gets the index of the value in the array items
def find_index(items, value):
    for i in range(len(items)):
        if items[i] == value:
            return i
    # if we didn't find the value then throw an exception because the caller
    # lied
    raise UnboundLocalError("that number doesn't seem to exist?")

# tells us if a given index is the last index for the array
def is_last_index(items, index):
    if index == (len(items) - 1):
        return True
    return False

# removes the last item from the array and returns a new array of the contents
# of the old array except without the last item
def remove_last_item(items):
    last_index = len(items) - 1
    retern = []
    i = 0
    while i < last_index:
        retern.extend([items[i]])
        i += 1
    return retern

# tells us if a given array is in ascending order or not
def is_ascending(items):
    # an empty array or an array with only one item is definitely in ascending
    # order
    if len(items) < 2:
        return True

    big = largest(items)
    big_index = find_index(items, big)
    if is_last_index(items, big_index) == True:
        items2 = remove_last_item(items)
        return is_ascending(items2)

    return False


print is_ascending([1, 2, 3]) # True
print is_ascending([3, 2, 1]) # False
print is_ascending([1, 5, 4, 7, 8, 3, 2, 9, 1]) # False
print is_ascending([1, 3, 3, 1, 5]) # False

jorelli

Posted 2014-02-27T16:33:02.227

Reputation: 111

1

Python

Define the "unsortedness" of a list x = [x_0, x_1,...,x_n] to be the number of pairs i <= j so that x_i >= x_j. It's obvious that a perfectly sorted array will minimize the unsortedness. So all we have to do is check that x attains the minimum unsortedness of all permutations of x.

def unsortedness(x):
    n = len(x)
    u = 0
    for i in range(n):
        for j in range(i,n):
            if x[i] >= x[j]:
                u += 1
    return u

def is_sorted(x):
    from itertools import permutations
    best_so_far = x
    for p in permutations(x):
        if unsortedness(p) < unsortedness(best_so_far):
            best_so_far = p
    return best_so_far == x

boothby

Posted 2014-02-27T16:33:02.227

Reputation: 9 038

1

C#

This was the most obnoxious thing I could come up with:

bool DoSomething(int[] array)
{
    int x=1;
    for(int i=1;i<array.Length;)x=(x<<1)|Math.Sign(Math.Sign(array[i++]-array[i-2])+1);
    for(int i=1;i>0;i*=2)if(i-x==1)return true;return false;
}

Have fun. :)

Smallhacker

Posted 2014-02-27T16:33:02.227

Reputation: 241

1

JavaScript

var isSorted = function(array) { return "" + array == array.sort(function(a, b) { return a - b; }); }

Neil

Posted 2014-02-27T16:33:02.227

Reputation: 95 035

1

Javascript

Checks if an array is sorted without doing < or > comparison. The sign function is a slightly modified version of this answer: https://stackoverflow.com/a/1377165

You can provide a single array, or provide as many numbers as needed to the function.

The function returns true if the values are in ascending or descending order, otherwise it returns false.

function isSorted(x) {
  var dir, diff, next, result, sign, iterate;
  if (!x || !Array.isArray(x)) x = Array.prototype.slice.call(arguments);
  if (!x || !x.length || !(x.length - 1)) return (x || false) && Array.isArray(x);

  result = (dir = NaN, next = x.shift(), true);
  sign = function() { return diff/diff && (!!((diff-1)/diff)); };
  iterate = function() { 
    diff = next, diff -= (next = x.shift());
    return ((dir !== dir) && (dir = sign()) !== dir);
  };

  while (x.length && iterate());
  while (result && x.length) { result = (iterate(), !diff || (dir === sign())); }
  return result;
}

Edit: To check ascending order only, change the last return to:

  return result && (dir || (dir != dir));

test = function() {
  var s = isSorted;
  return 
    s() && s([]) && s(1) && s([1]) &&
    s(2,1) && s(1,2) && s(1,1) && 
    s([2,1]) && s([1,2]) && s([1,1]) && 
    s(1,1,1) && s(1,1,2) && !s(1,2,1) && s(1,2,2) && 
    s([1,1,1]) && s([1,1,2]) && !s([1,2,1]) && s([1,2,2]) && 
    s(2,2,1) && !s(2,1,2) && s(2,1,1) && 
    s([2,2,1]) && !s([2,1,2]) && s([2,1,1]) && 
    !s(1,1,2,1) && !s(2,2,1,2) &&
    !s([1,1,2,1]) && !s([2,2,1,2]);
};
test()
> true

AA-j

Posted 2014-02-27T16:33:02.227

Reputation: 11

1

TI-BASIC

This is, unfortunately, the only way to do it (it does work):

:Input L1:L1:SortA(Ans:L1=Ans:Stop:Start New Loop(SortArray.tib)
:From BananaPie,Math,STDIO Import *
:SortArray.tib function new Main {return banana cream pie}
:If NoInputReceived(SortArray.Main) Throw Old SquashedBananaError
:Else Display "YesNo" ? 3 5
:function old Main ==> NewThread.Create(floor(math.random))

The troll is that only the following code executes (and it does work):

:Input L1:L1:SortA(Ans:L1=Ans:Stop:

Timtech

Posted 2014-02-27T16:33:02.227

Reputation: 12 038

1

Javascript

Recursively pop the last element of the array, and test if it is greater than or equal to the maximum of the remaining elements, using a Y-combinator and misleading indentation for extra trolling.

function is_sorted(arr) {
  return function(x){
    return function(f){
      return (f(f))(x)
        }(function(f) {
          return function(x) {
            return !x.length || x.pop() >= Math.max.apply(null, x) && f(f)(x);
              }})}(arr.slice(0))
}

Paul

Posted 2014-02-27T16:33:02.227

Reputation: 256

1

C

Determine sortedness in sub-linear time.

#include <stdlib.h>

static int issorted_chunk_(const int* x, size_t size, size_t chunk)
{
    size_t i;
    for ( i = chunk; i < size; i += chunk*2 )
       if (x[i] < x[i-1])
          return 0;
    return 1;
}

int issorted(const int* x, size_t size)
{
    size_t chunk = 1;
    for ( ; chunk < size; chunk *= 2 )
       if (!issorted_chunk_(x, size, chunk))
          return 0;
    return 1;
}

user17623

Posted 2014-02-27T16:33:02.227

Reputation: 11

1

C++

Convert the array into a binary search tree by recursively taking the midpoint as the root node, the left 'half' as the left subtree, and the right 'half' as the right subtree.

If the resulting tree is a valid binary search tree, the array is sorted. Inspired by this.

I justify this as code-trolling because it's so obviously over-engineered for such a simple problem.

#include <iostream>
#include <vector>
#include <iterator>
#include <memory>


struct node;
typedef std::shared_ptr<node> node_ptr;

// Node struct to form the tree
struct node {
public:

   node(int value, node_ptr left, node_ptr right)
      : value_(value), left_(left), right_(right)
   {
   }

   int value () const {
      return value_;
   }

   const std::weak_ptr<node> left() const {
      return left_;
   }

   const std::weak_ptr<node> right() const {
      return right_;
   }

private:
   int value_;
   node_ptr left_;
   node_ptr right_;
};


// Less-than operator
bool operator <(const node &l, const node &r) {
   return l.value() < r.value();
}

// Greater-than operator
bool operator >(const node &l, const node &r) {
   return l.value() > r.value();
}


// Build the tree recursively.
// Choose a midpoint in the array. 
// If the count is even, choose the left of the two middle elements.
// The midpoint becomes the root of the subtree,
// the elements to the left of the midpoint form the left subtree,
// the elements to the right of the midpoint form the right subtree.
node_ptr make_tree (const int *values, std::size_t size) {
   if (!size)
      return node_ptr();

   std::size_t mid = (size - 1) / 2;

   return std::make_shared<node>(values[mid],
      make_tree(values, mid),
      make_tree(values + mid + 1, size - mid - 1));
}

// The left child of a node must have a value <= to the root's value
// The right child of a node must have a value >= to the root's value
bool is_valid (node_ptr root) {
   if (root) {

      if (node_ptr left = root->left().lock()) {
         if (*left > *root || !is_valid(left))
            return false;
      }

      if (node_ptr right = root->right().lock()) {
         if (*right < *root || !is_valid(right))
            return false;
      }
   }

   return true;
}


int main () {
   std::vector<int> numbers;

   // Read in numbers from stdin. Send EOF to finish.
   std::copy(std::istream_iterator<int>(std::cin),
             std::istream_iterator<int>(),
             std::back_inserter(numbers));

   // Build the tree
   node_ptr root;
   if (!numbers.empty())
      root = make_tree(&numbers[0], numbers.size());

   // Check validity
   std::cout << "Array is" 
             << (is_valid(root) ? " " : " not ")
             << "sorted" 
             << std::endl;
}

Note, you might not get the expected results if you enter non-integers.

As an added bonus, this algorithm will not only produce a valid binary search tree, it will produce:

  • A balanced binary search tree, and
  • If the number of items is one more than a power of two, a perfectly balanced tree.

Anthony

Posted 2014-02-27T16:33:02.227

Reputation: 111

1

PHP

For those wondering, here is how to improve the interviewee's solution:

  1. You don't need nested loops!
  2. You don't need to check the first and last elements!

I implemented it, with some very uselful comments so you can understand it better:

function smaller($a, $b, $array) {
  global $ret; // very important or we can't have the result of the function

  // this helps working with lists in the OOP paradigm (PHP is really powerful!)
  $list= 'object';
  $object = 'array';

  // extract the elements from the list (caution: the first element is 0!)
  list($ret) = array_slice($$object, +$$object [ 0 ], 1);
  list($a) = array_slice($$object, +$$list     [ 1 ], 1);
  list($b) = array($ret);

  $compare = '"$ret='.$a.'\u003E'.$b.';"'; // security measure
  // using json_decode to protect from injection (security measure)
  eval(json_decode($compare));
}

function is_sorted($list) {
  global $ret; // very important or we can't have the result of smaller

  // all elements of $list must be strings or we can't compare them!!
  $length = sizeof($list);
  $sequence = range(1, $length - $list[0]);

  foreach($sequence as $index => $each_element) { // using every element of the sequence as an index (do NOT use $each_element)
     smaller($index, ++$index, $list); // the element before
    if(!$ret) return;

    smaller($index, ++$index, $list); // the element after
    if(!$ret) return;

  }
  return $list;
}

echo is_sorted(array('2', '3', '4', '5')) ? 'sorted': 'not sorted'; // sorted
echo is_sorted(array('2', '3', '5', '4')) ? 'sorted': 'not sorted'; // not sorted
echo is_sorted(array('2', '5', '4', '3')) ? 'sorted': 'not sorted'; // not sorted

Okay there's so many things that went wrong here. A hint: ['3', '4', '5', '4'] is said to be sorted.

Tell me what you think, I had a lot of fun!

Pierre Arlaud

Posted 2014-02-27T16:33:02.227

Reputation: 179

1

Textbook

The list is sorted.
  It is left as an exercise for the reader to find the comparison operator.

user17672

Posted 2014-02-27T16:33:02.227

Reputation: 11

This might be somewhat cute if the question hadn't clearly specified an array of integers sorted in ascending order. You're poking at a loophole that isn't even there. Moreover, this is a code/programming site. We generally expect code in answers, even for code-trolling, as the tag wiki for that tag will tell you. – Jonathan Van Matre – 2014-02-28T20:04:16.057

1

Python

Determining if it's sorted is too much work for a computer. Of course, you should give the user a chance to verify the input:

def check_sorted(input_list):
    print 'CHECK FOR SORTED'
    print '----------------'
    print 'Please tell me which is the higher number for each of these pairs,'
    print 'and I will tell you whether the list is sorted or not'
    initial_value = input_list[0]
    for test_value in input_list[1:]:
        bigger = input('Which number is bigger, %d or %d: '%(initial_value, test_value))
        bigger = int(bigger)
        if bigger != test_value:
            print 'LIST IS NOT SORTED!'
            return
        initial_value = test_value
    print 'LIST IS SORTED!'
    return

Corley Brigman

Posted 2014-02-27T16:33:02.227

Reputation: 111

1

Python

from random import choice
def is_sorted(seq):
    return choice([True, False])

Note

As the Question never said about the sorting order and or collated sequence, I let the program decide and thereby respond with an answer.

Abhijit

Posted 2014-02-27T16:33:02.227

Reputation: 2 841

1

C

The essential feature of the problem is that we have an array of integers. I looked for a method that works with ints but not with floats.

#include <assert.h>
#include <limits.h>

int is_sorted(int* array, int size) {
  int i, index=0;
  for (i=INT_MIN; i<INT_MAX; i++) {
    while (array[index]==i) { 
      index++;
      if (index==size) return(1);
    }
  }
  return(0);
}

int main() {
  int test1[4] = {1,2,2,3}; int test1length = 4;
  assert(is_sorted(test1,test1length));

  int test2[3] = {1,3,2}; int test2length = 3;
  assert(is_sorted(test2,test2length));
} 

Alexander Hanysz

Posted 2014-02-27T16:33:02.227

Reputation: 141

1

Literate Haskell

This is a literate haskell post, so you can copy and paste it, give it a .lhs extension, and run it. Bogobogosort is like bogosort. As a refresher, in bogosort, if a list is sorted, you return it. If not, you randomly shuffle it, and try to bogosort it again. (Note that some authors will shuffle it first and then check, so that it has uniform behavior on all lists, but the above is simpler.) We will need the random-shuffle package. You can install it with cabal install random-shuffle.

> import System.Random.Shuffle (shuffleM)
> import Control.Monad.Random  (MonadRandom)
> bogobogosort :: (Ord a, MonadRandom m) => [a] -> m [a]
> bogobogosort list= do
>   sorted <- bogoCheck list
>   if sorted
>       then return list
>       else shuffleM list >>= bogobogosort

Note that the original bogosort never specified how it is to be sorted. This problem is solved at http://www.dangermouse.net/esoteric/bogobogosort.html.

> bogoCheck :: (Ord a, MonadRandom m) => [a] -> m Bool
> bogoCheck []  = return True
> bogoCheck [x] = return True
> bogoCheck (x1:xs) = do
>   sTail@(sx2:sxs) <- bogobogosort xs
>   return $ (x1 <= sx2) && (xs == sTail)

To check if it is sorted, we first check if it is empty or only has one item. If it is, it is sorted. If not, we bogobogosort all but the first item. Now we check if the first item of the sorted tail is greater than the original first item. Then we check if the sorted tail equals the original tail. If so, it is sorted. Here is a test.

> main = do
>   putStrLn "Testing [-1,2,2,3,7,9]"
>       print =<< bogoCheck [-1,2,2,3,7,9] --Ignore extra indentiation. I have no idea why I need it.
>   putStrLn "Testing [2,1,3,9,1,3]"
>   print =<< bogoCheck [2,1,3,9,1,3]

This gives:

λ <*Main>: main
Testing [-1,2,2,3,7,9]
True
Testing [2,1,3,9,1,3]
False

PyRulez

Posted 2014-02-27T16:33:02.227

Reputation: 6 547

Reading is FUNdamental! – Jonathan Van Matre – 2014-03-08T13:45:37.527

1

/**
 * @brief Test if a range is sorted
 *
 * @pre the range must be sorted
 * @return true
 */
template< typename Iterator >
static inline bool test_sorted_1(Iterator start, Iterator stop)
{
    return true;
}

/**
 * @brief Test if a range is sorted
 *
 * @pre the range must be unsorted
 * @return false
 */
template< typename Iterator >
static inline bool test_sorted_2(Iterator start, Iterator stop)
{
    return false;
}

user16488

Posted 2014-02-27T16:33:02.227

Reputation:

1

I may have missed it, but has anyone proposed a stochastic version? Stochastic versions are way more fun than deterministic ones:

While you're not yet satisfied:
   Randomly pick i uniformly from 1 to the length of the array
   Randomly pick j uniformly from 1 to the length of the array

   If (i < j) and (array[i] > array[j]) It's not sorted properly
   If (i > j) and (array[i] < array[j]) It's not sorted properly // Optional

It's properly sorted, to your personal satisfaction

The satisfied condition can be anything you want that will terminate: the number of loop iterations, execution time, prompting the user.

Wayne

Posted 2014-02-27T16:33:02.227

Reputation: 111

1

/* The array to be checked is zero-terminated. 
 * Because a zero-termination at the end of code would cause the array to be not sorted anyway, the zero-termination should be inserted at the start of the array. 
 * This is called a reversed zero-terminator.
 * To be able to tell the length of the array, the number 9733567 should be the last element.
 * The number was chosen because the probability for an array to contain that number in the middle is reasonably low.
 * This function is implemented using a technique called safe programming.
 * We don't trust the computer to do it right the first time, so we do it twice (with different methods) and see if we get the same result. */ 

int is_sorted(int *a)
{
    int i, mismatch=0, second_mismatch=0;
    long long mul=1, last_mul=1;

    /* Check if proper reverse zero-terminator has been inserted */
    if (a[0]!=0) abort();

    /* First check: Count number of mismatches using multiplication method */
    for (i=1; a[i]!=9733567; ++i) {
        mul*=a[i-1]-a[i];
        if (mul>0==last_mul>0) mismatch+=!!mul;
        last_mul=mul;
    }

    /* Second check: Count number of mismatches using comparison method */
    for (i=1; a[i]!=9733567; ++i) {
        if (a[i]-a[i-1] < 0) {
            second_mismatch=second_mismatch+1;
        }
    }

    /* Check if we got the same number of mismatches */
    if (mismatch>second_mismatch || second_mismatch>mismatch) abort();

    /* We consider the array sorted if we didn't find any mismatches in the first or second check */
    if (mismatch==0 && second_mismatch==0) return 1;
    else return 0;
}

ahy1

Posted 2014-02-27T16:33:02.227

Reputation: 191

1

C# Exhaustive Sorted Sequence Search

Not sure if somebody has implemented this algorithm, I wanted to be extremely efficient and use some Linq functionality with Extensions to make it all prettier.

If we can generate all sorted sequences with the same length as the input, we could see if one of the generated sequences matches the input sequence, if there is no match then the sequence is obviously not sorted. The algorithm only works with non-negative numbers, and currently only works on the System.Int32 datatype.

public static class StackExchangeCreativeSorted {

private const int Max = int.MaxValue;

// Determines if sequence is sorted
public static bool IsSorted(IEnumerable<int> sequence) {
    var comparer = new IEnumerableEqualityComparer<int>();
    // using LINQ!!!11!
    return GenerateAllSortedSequences(sequence.Count()).Contains(sequence, comparer);
}

/// Generate all sorted sequences for a specific sequence length
private static IEnumerable<IEnumerable<int>> GenerateAllSortedSequences(int length) {
    var seed = new int[length];
    // algorithm to generate all ascending sequences 
    // {0,0,0}, {0,0,1},...,{1,2,3},...,{2,3,3}, {3,3,3}
    Action<int[]> next = null;

    next = (arr) => {
        if(arr[0] == Max) {
            throw new InvalidOperationException("Array is already at maximum sequence.");
        }

        var i = 0;
        while(i < arr.Length - 1 && arr[i + 1] < Max ) {
            i++;
        }   

        if(i == arr.Length - 1) {
            arr[i]++;
        }
        else {
            arr[i]++;
            i++;
            while(i < arr.Length) {
                arr[i] = arr[i - 1];
                i++;
            }
        }
    };

    while(seed[0] < Max) {
        yield return seed;
        next(seed);
    }

    yield return seed; //last one :)
}

/// Used to for comparison
private sealed class IEnumerableEqualityComparer<T> : IEqualityComparer<IEnumerable<T>> {
    public bool Equals(IEnumerable<T> a, IEnumerable<T> b) {
        return a.SequenceEqual(b);
    }

    public int GetHashCode(IEnumerable<T> b) {
        return b.GetHashCode();
    }   
}

We then add an extension method to make it nice:

public static class Extensions {
    public static bool IsSorted(this IEnumerable<int> sequence) {
        return StackExchangeCreativeSorted.IsSorted(sequence);
    }
}

And we can use it like this:

public static void Main(string args[]) {    
    // sorted
    var isSorted   = (new[] {1,2,3}).IsSorted().Dump();
    // unsorted
    var isUnsorted = (new[] {1,3,1}).IsSorted().Dump();
}

Hope you enjoyed it, I will be writing a patent for this!

Jonathan Nazario

Posted 2014-02-27T16:33:02.227

Reputation: 11

1

Javascript

Let's go to the basics, the table is sorted if and only if:

  • the last item is greater than the max of the sub-list of all but last items
  • the rest of the list is sorted

To determine the max item of the list the algorithms is quite simple:

  • if list has just one item : this item
  • if item is greater than the previous to last and the sub-list of all but last items is sorted : the last item
  • in all other cases : the max for the sub-list of all but last items

This can be written :

function isSorted(tableToSort) {
    function isSortedInt(table,i){
        return i==0 || table[i]>=max(table,i-1) && isSortedInt(table,i-1)
    }
    function max(table,i){
        if (i==0 || (isSortedInt(table,i-1) && table[i]>=table[i-1])) {
            return table[i];
        } else { 
            return max(table,i-1);
        }
    }
    return isSortedInt(tableToSort,tableToSort.length-1) 
}

This should execute in a nice O((λn)!)

Julien Ch.

Posted 2014-02-27T16:33:02.227

Reputation: 279

1

You've gotten quite a few answers, but most of them seem rather longer and more complex than necessary for such a simple question. Fortunately, C++ has a function in the standard library that makes this task really easy. One of the first rules of programming well is to use the standard library (well, libraries in general, but especially the standard library) when it can make your job easier.

Along with being shorter and simpler than many, this sorted function is actually a template, so it can be applied to various different kinds of collections--the demo-code shows it for std::list, std::deque and std::vector, but it would work equally well on other containers as well.

#include <algorithm>
#include <vector>
#include <list>
#include <deque>
#include <iostream>

unsigned long long compute_expected(unsigned long long in) {
    if (in == 0)
        return 1;
    return in * compute_expected(in - 1);
}

template <class It>
bool sorted(It begin, It end) {
    unsigned long long count;
    for (count = 1; std::next_permutation(begin, end); ++count);
    return count == compute_expected(std::distance(begin, end));
}

int main() {
    std::vector<int>    in1{ 1, 2, 3, 4, 5 };
    std::list<int>      in2{ 5, 4, 1, 3, 2 };
    std::deque<int>     in3{ 1, 2, 3, 4, 5, 6 };

    std::cout << std::boolalpha;

    std::cout << "Input 1: " << sorted(in1.begin(), in1.end()) << "\n";
    std::cout << "Input 2: " << sorted(in2.begin(), in2.end()) << "\n";
    std::cout << "Input 3: " << sorted(in3.begin(), in3.end()) << "\n";
}

See, the operative part of this (the sorted function) only requires a half dozen lines of code. Many of the other answers are much longer and more complex.


...of course, if the student in question was paying attention when they talked about complexity of algorithms (and he recognized that expected is actually computing the factorial) he might get some premonition of the fact that this could be just the tiniest bit on the inefficient side if the array gets very large. OTOH, at least distance will overflow even a 64-bit integer before he gets to calculations that will exceed the expected lifetime of the universe. Too bad it doesn't use that to limit that number of iterations it'll execute...

Complexity: for a sorted collection, this computes all N! permutations of the inputs. Each of those should be linear, so overall complexity should be O(N * N!).

Jerry Coffin

Posted 2014-02-27T16:33:02.227

Reputation: 539

1

C#

Its clear, we want a solution in O(n) since those are the best, right? Now lets think about what a good function/algorithm needs:

  • Recursion
  • try/catch so everything is save
  • while(true)
  • for loop
  • (useless) type conversion
  • and it has to destroy the input array just to mess around

    public static bool IsSorted(int[] array)
    {
        if (array.Length == 0)
            return true;
    
        try
        {
            while(true)
            {
                for (int i = array.Length - 1; i >= 0; i--)
                {
                    var a = 1 / ++array[i];
                }
            }
        }
        catch(Exception)
        {
            if(array[array.Length-1] == 0)
            {
                var b = array.ToList<int>();
                b.RemoveAt(array.Length - 1);
                return IsSorted(b.ToArray());
            }
            else
                return false;
        }
    }
    

So what does it do? We iterate backwards (heall yeah backwards) over the array and add 1 to each element and divide 1 by each element (we assume the list has only positive entrys and 0).

Sooner or later a value will overflow and even later it will reach 0. an Exception is thrown since we try to divide by zero. Now we know which of our former array entries was the biggest, if it was the last one we remove it with some useless array->list->array conversion and start the method again with our smaller array.

If it wasn't the last element our array isn't sorted correctly, and we return false. We return true if our array becomes empty.

This algorithm is in O(n) but its really slow for O(n) since its more like O(n * 2 * MaxInt). Oh, it also destroys the input array! Yay!

Master117

Posted 2014-02-27T16:33:02.227

Reputation: 389

0

C

It's very simple:

int checkSorted(int *arr, int length) {
    int i = 0, j = 0;
    for (i = 0; i < length; i++) {
        if (arr[i] > arr[j]) {
           return 0;
        }
    }
    return 1;
}

(Another code-only answer).

This can be adapted to many languages. The code only checks that the first element is smaller than or equal to the rest of the elements in the array. This is only necessary but not sufficient condition to check that an array is sorted.

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳

Posted 2014-02-27T16:33:02.227

Reputation: 5 683

0

C#

using System;

class C
{
 static string isSorted(int[] set)
  {
    for (int i = 0; i < set.Length - 1; i++)
    {
        if (set[i] > set[i + 1])
            return "Unsorted";
    }
    return "Sorted";
   }

 static void Main()
 {
    int[] set1 = new int[] {5, 10, 15, 20, 25};
    int[] set2 = new int[] { 5, 10, 15, 15, 0 };

    Console.WriteLine(isSorted(set1));
    Console.WriteLine(isSorted(set2));            
  }
}

Merin Nakarmi

Posted 2014-02-27T16:33:02.227

Reputation: 247

Sorry, but I am not seeing what is the trollish thing here. Could you explain? – Victor Stafusa – 2014-02-27T19:28:20.347

1bad answer for a bad question = good solution :) – fejesjoco – 2014-02-28T10:39:30.053

0

PHP

Easy answer. Not sure if it's the most creative though:

$a=[1,2,3,4];
$i=0;
    while(isset($a[($i+1)]) && ($a[$i] <= $a[($i+1)])) { 
    $i++; 
}
echo (($i==count($a)-1) ? '' : 'not')." sorted"; 

Scott

Posted 2014-02-27T16:33:02.227

Reputation: 1

0

Javascript

function isSorted(array){
    array.sort(function(a,b){
        if(a>b){
            return 1;
        }else{
            return -1;
        }
    });
    return true; //Is always sorted!
}

scrblnrd3

Posted 2014-02-27T16:33:02.227

Reputation: 1 554

0

Delpi XE3

Ofcourse this is an example with arrays hard coded (both length and values) but this will work with input too with a few small adjustments.

Uses
  IdGlobal;

const
  Yes='Array is sorted!';
  No='Array is not sorted!';
var  
  a:array[0..9] of integer =(1,9,6,4,10,3,7,2,9,5);
  b:array[0..9] of integer =(1,2,3,4,5,6,7,8,9,10);

  function IsSorted(ar:array of integer):boolean;
  var
    i:integer;
  begin
    Result:=true;
    for I:=Low(ar)to High(ar)-2do
      if not (ar[i+1]>=ar[i]) then
        exit(false);
  end;  
begin
  Writeln(iif(IsSorted(a),Yes,No)); 
  Writeln(iif(IsSorted(b),Yes,No));
end.

What I used and why

Unit IdGlobal needed for inline if iif
Example: iif(Expression,IsTrueValue,IsFalseValue)
2 strings for showing if array is sorted yes/no (not needed, but makes code prettier imo)
2 arrays 1 unsorted, 1 sorted.
Function to check if array is sorted by checking if each number is greater or equal to the one before, if not then exit function.
2x WriteLn with iif which gives a string as result.

Teun Pronk

Posted 2014-02-27T16:33:02.227

Reputation: 2 599

0

PHP

Maybe not creative but easy and obvious:

$array = range(1, 100);
$test = $array;
sort($test);

if($test === $array) {
    echo 'Sorted';
} else {
    echo 'NOT sorted';
}
// Sorted

$array = array(5, 4, 1, 10, 50);
$test = $array;
sort($test);

if($test === $array) {
    echo 'Sorted';
} else {
    echo 'NOT Sorted';
}
// NOT Sorted

AbraCadaver

Posted 2014-02-27T16:33:02.227

Reputation: 101

0

(stochastic) Ruby

Checking all the values is way to expensive, you can't do that. My solution works better, and is almost guaranteed.

def is_sorted?(ary)
  10_000.times {                #10 000 is a huge number !
    index1 = rand(ary.size) # pick a random element in the array
    index2 = rand(ary.size) # pick another random element in the array

    #Now the tricky  part
    return false if index1 < index2 and ary[index1] > ary[index2] #if this pops, we won't even compute the next part !
    return false if index1 > index2 and ary[index1] < ary[index2]
  }
  return true # At this point we're pretty sure the array is sorted
end

aherve

Posted 2014-02-27T16:33:02.227

Reputation: 181

0

It's easy one - two possible solutions: First one is really simple: we wrote the first method basing on the helloworld example:

private bool myMethod1(int[] array){
   return false;
}

then we set breakpoint on the return line, start debbugger and after manual check of right order of 1*E6 int array changing the returned value from false to true.

Second one is a bit more complicated so I just enlist main points:

At first step look for solution on stack overflow, and throw it away as too simple one (single loop can't work in real world) then:

  1. create all possible permutations of initial array (just n! of possibilities)
  2. calculate the hashes of all arrays
  3. check what permutation is really sorted using stack overflow copy - paste code (do not read it!)
  4. calculate the hash for the sorted array
  5. calculate the hash of input array
  6. calculate if hashes match each other
  7. run program on the small 10k array
  8. get out of memeory error
  9. check what is that 10 try to run program using 10 elements array 11 move your code to some binary lib, delete the source code 12 push your solution to repo

piotrpo

Posted 2014-02-27T16:33:02.227

Reputation: 101

0

C#

using System;

namespace IsSortedAlgorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] array = {82, 69, 109, 12, 78, 79, 114, 1};

            Console.WriteLine("Is array sorted: " + IsSorted(array));

            Array.Sort(array);

            Console.WriteLine("Is array sorted: " + IsSorted(array));
        }

        private static bool IsSorted(int[] array)
        {
            for (int i = 0; i < array.Length; i++)
            {
                bool sorted1 = false;
                bool sorted2 = false;
                if (i > 0)
                {
                    if (array[i] >= array[i - 1])
                        sorted1 = true;
                }
                else sorted1 = true;
                if (i < (array.Length - 1))
                {
                    if (array[i] <= array[i + 1])
                        sorted2 = true;
                }
                else sorted2 = true;

                if (array1.Length > 1 && aray2.Length > 1 && (!sorted1 || !sorted2))
                    return false;
            }

            return true;
        }
    }
}

Icemanind

Posted 2014-02-27T16:33:02.227

Reputation: 101

0

JavaScript

It's always great practice to include recursive! Compares each integer to the "next" integer to determine if the array is sorted. "Inherent error checking" included! Note: maximum index (n) of a given array (x) is 8954 (x[n]).

A bag of fantastic:

function zod(inArray){ 
var len = inArray.length, flag=[];
for(var i=0;i<len-1;i++){
  if(inArray[i]<inArray[i+1]){//compares "left to right"
    flag.push("true");}
    else{flag.push("false");}
 }return comparables(flag,0);
}//endzod    
function comparables(flagged,count) {
this.cnt = count;
this.flag = flagged;
var flagCheck=0;
  while(cnt<(flag.length)){
   if(flag[cnt]==="true"){
    cnt++;
    comparables(flag,cnt); //recursive yay! 
    flagCheck=1;
   }
   else{flagCheck=0;break;}//"perfect" way of doing this...
  }
  if(flagCheck===0){return "Not Sorted";}
  else if(flagCheck===1){return "Sorted";}
  else{return "unknown"}; //"error checking"
}//END comparables

To run:

Wrap in a simple HTML page:

<!DOCTYPE html>
<html>
<head>
<script>
//copy+paste above JS code from above (saving space)
function testZodOutput(){
var testArray=[];
for(i=0;i<8954;i++){testArray[i]=i;}
document.getElementById("catcher").innerText=zod(testArray);
}
</script>
</head>
<body><div id="catcher" style="color:red"><button onclick="testZodOutput()">CLICK ME FOR TESTING!</button></div>
</html>

The above will display "sorted" as testArray is filled with sequential integers. To test the opposite: Add a random number to a random index directly after the for loop. ex: testArray[34]=9001;.

Rich

Posted 2014-02-27T16:33:02.227

Reputation: 1

0

Python

All problems in computer science can easily be solved by recursion. Well, until you happen to pass it a sorted array of 999 or more elements.

def is_sorted(seq):
    if not seq:
        return True
    first = seq[0]
    for x in seq[1:]:
        if x < first:
            return False
    return is_sorted(seq[1:])

dan04

Posted 2014-02-27T16:33:02.227

Reputation: 6 319