“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

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 2

C#

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

String Trolling

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

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

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

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

Edit:

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

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

Looks good enough to me:

  this: 300000000000000015751428076561326074611340574332447746474756234653540737396672458735911412524134359213111333149865163453082756970608129172693437655436012094854516160277972741121349070138436427017810685970491239983524335711690292264022395822834042748373777636646017052851434700841658916059637820162048000
  next: 3010000000000000158039328368165304948600450429135559056296720887690525398546613669316977838992148070771550375936980473312596994938434896032690824476207988018373645474788993169250869003722312151078700549237262107834694168307292599049024704755768228908683568954348371096942728165111311124465032795625881600

Edit 2:

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

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

Answer 3

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 4

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 5

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 6

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 7

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 8

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 9

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 10

JavaScript

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

Answer 11

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 12

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 13

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 14

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 15

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 16

Textbook

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

Answer 17

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 18

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 19

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 20

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 21

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 22

/**
 * @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 23

/* 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 24

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 25

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 26

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 27

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 28

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 29

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 30

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