# “Creative” ways to determine if an array is sorted

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.

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

• 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. – microbian Feb 27 '14 at 17:16
• At the end of the contest I would like to know the "creative" solution, too! :) – Vereos Feb 27 '14 at 17:23
• @micro Diamond moderators are community elected. You are confusing moderators with the privilege system. – Doorknob Feb 27 '14 at 17:58
• @microbian So have you hired that guy? – VisioN Feb 28 '14 at 8:17
• If only StackExchange API allowed write access, I'd ask the question "Is this array sorted?" and count upvotes on positive/negative answers.. – Michael Foukarakis Mar 1 '14 at 8:31

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


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

• Clever answer. Warning: you may be getting a lawsuit from @LMSingh for essentially implementing their "Line up stones next to a log" algorithm in C#. Welcome to PPCG! – Jonathan Van Matre Mar 3 '14 at 23:17
• What if our patent application is titled "A Stone-less Method for Determining Sortedness"? – nvuono Mar 4 '14 at 14:50

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.


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

• Upvote for my SQL compadre. Welcome! – Jonathan Van Matre Feb 27 '14 at 22:32

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

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

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;

}
}
}


}

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.

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

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


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

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


JavaScript

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


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


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


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


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

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

## Textbook

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

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

# 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


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


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.

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


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

• Reading is FUNdamental! – Jonathan Van Matre Mar 8 '14 at 13:45

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

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


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.

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

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

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

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!

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


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.

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

• Sorry, but I am not seeing what is the trollish thing here. Could you explain? – Victor Stafusa Feb 27 '14 at 19:28
• bad answer for a bad question = good solution :) – fejesjoco Feb 28 '14 at 10:39