"Creative" ways to determine if an array is sorted

Question

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!!.

Answer 1

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

Answer 2

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.");
    }
}

Answer 3

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 2ⁿ-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, 2ⁿ-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.

Answer 4

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.

Answer 5

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' ";

Answer 6

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.)

Answer 7

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));

Answer 8

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.

Answer 9

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

Answer 10

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
}

Answer 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

Answer 12

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 :)

Answer 13

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;
}

Answer 14

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...

Answer 15

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.

Answer 16

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;
}

Answer 17

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?

Answer 18

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).

Answer 19

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;
}

Answer 20

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?

Answer 21

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.

Answer 22

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");
}

Answer 23

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>

Answer 24

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/

Answer 25

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;
}

Answer 26

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.");

Answer 27

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();


     }

Answer 28

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

Answer 29

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}

Answer 30

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.

Answer 31

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];
    }
}

Answer 32

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;
  }
}

Answer 33

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;
}

Answer 34

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.

Answer 35

C# WPF

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.

Answer 36

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.

Answer 37

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

Answer 38

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

Answer 39

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. :)

Answer 40

JavaScript

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

Answer 41

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

Answer 42

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:

Answer 43

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))
}

Answer 44

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;
}

Answer 45

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.

Answer 46

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!

Answer 47

Textbook

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

Answer 48

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

Answer 49

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.

Answer 50

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));
} 

Answer 51

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

Answer 52

/**
 * @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;
}

Answer 53

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.

Answer 54

/* 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;
}

Answer 55

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!

Answer 56

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)!)

Answer 57

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!).

Answer 58

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!

Answer 59

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.

Answer 60

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));            
  }
}

Answer 61

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"; 

Answer 62

Javascript

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

Answer 63

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.

Answer 64

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

Answer 65

(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

Answer 66

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

Answer 67

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;
        }
    }
}

Answer 68

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;.

Answer 69

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:])