51
votes
\$\begingroup\$

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

\$\endgroup\$

locked by Doorknob May 10 '14 at 16:12

This question exists because it has historical significance, but it is not considered a good, on-topic question for this site so please do not use it as evidence that you can ask similar questions here. This question and its answers are frozen and cannot be changed. See the help center for guidance on writing a good question.

Read more about locked posts here.

  • 58
    \$\begingroup\$ This is not a duplicate. Some moderators feel it necessary to mark every question duplicate to others without reading it. This is not a sorting question at all. Read it. \$\endgroup\$ – microbian Feb 27 '14 at 17:16
  • 3
    \$\begingroup\$ At the end of the contest I would like to know the "creative" solution, too! :) \$\endgroup\$ – Vereos Feb 27 '14 at 17:23
  • 16
    \$\begingroup\$ @micro Diamond moderators are community elected. You are confusing moderators with the privilege system. \$\endgroup\$ – Doorknob Feb 27 '14 at 17:58
  • 3
    \$\begingroup\$ @microbian So have you hired that guy? \$\endgroup\$ – VisioN Feb 28 '14 at 8:17
  • 3
    \$\begingroup\$ If only StackExchange API allowed write access, I'd ask the question "Is this array sorted?" and count upvotes on positive/negative answers.. \$\endgroup\$ – Michael Foukarakis Mar 1 '14 at 8:31

69 Answers 69

0
votes
\$\begingroup\$

Javascript

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

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.

\$\endgroup\$
0
votes
\$\begingroup\$

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
\$\endgroup\$
0
votes
\$\begingroup\$

(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
\$\endgroup\$
0
votes
\$\begingroup\$

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
\$\endgroup\$
0
votes
\$\begingroup\$

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"; 
\$\endgroup\$
0
votes
\$\begingroup\$

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

\$\endgroup\$
0
votes
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
0
votes
\$\begingroup\$

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:])
\$\endgroup\$

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