# I need a program where the user inputs an array of doubles and the program outputs the array sorted

Note: This question was severely edited since I first posted it here. The rules were moved to here, read them before posting any answer to understand the purpose of this. This was the first question created in the category.

Imagine a lazy user on Stack Overflow asks this question:

I need a program where the user inputs an array of doubles and the program outputs the array sorted. Could you please give the code?

How could you create a piece of code that will troll this user? Create a piece of code that will appear useful to an inexperienced programmer but is utterly useless in practice.

The winner is the most upvoted answer, except if the answer is somehow not eligible (for eligibility requirements, check the tag wiki description of ). If the previously most upvoted answer is beaten in the future in the number of upvotes after being accepted, the new best answer is accepted and the previous one is unaccepted. In the case of a tie, I will choose the winner at will among the tied ones or just wait a bit more.

Answers that have no code are not eligible. They might be fun and get some upvotes, but they won't be accepted.

Rules can be found at tag description.

• Stack Oversort – ThiefMaster Dec 27 '13 at 13:26
• @bluesm If someone has already decided to ask someone else to solve their problem instead of "wasting" their own time learning, posting a link to where they can learn on their own isn't going to do any good. – IQAndreas Dec 27 '13 at 16:21
• Wow, this question's about to get 100 upvotes and 10,000 views in less than 24 hours! – Joe Z. Dec 28 '13 at 1:37
• My goodness, Victor, your About box is so sad... we all have our ups and downs but you shouldn't beat yourself up man. You're a hero for Code Golfers everywhere now! – SimonT Dec 28 '13 at 4:21
• I'm surprised no one has offered a solution based on sleep sort yet – Frank Farmer Dec 28 '13 at 11:02

Let's try this, in my usual favourite, PowerShell:

$doubles =$(for($s = ''; ($s = Read-Host) -ne '') { if ($s) { +$s } })
-join([char[]]"$doubles" | sort)  Input can be aborted with an empty line. This will output the array sorted. Sort-of. Actually, it will sort every single character in the array. But it's sorted, right? OK, OP. Before we start, we need to really understand what sorting is. Imagine you have ten numbers: 4 6 2 8 5 2 8 1 9  You look for the smallest one, and then the next and then the next, and so on. This suggests our algorithm: 1. Choose the smallest number 2. Count up to the next number 3. Repeat step 2 until done Which give us our (remarkably simple) code! # New-style imports array = __import__("array").array sys = __import__("sys") # Where to store doubles our_doubles = array("d") # Load them our_doubles.fromfile(sys.stdin.buffer, int(input("How many numbers?"))) new_doubles = array("d") # STEP 1 smallest = min(our_doubles) new_doubles.append(smallest) # STEP 2 # Get the smallest difference between the pairs so our steps don't skip anything step = abs(min(__import__("itertools").starmap(__import__("operator").sub, __import__("itertools").combinations(our_doubles, 2)), key=lambda x:abs(x) or float("inf"))) for elemant in our_doubles: if new_doubles.count(elemant) != our_doubles.count(elemant) and elemant < smallest + step: # ^^^^^^ NEXT NUMBER new_doubles.append(elemant) # STEP 3 while len(new_doubles) != len(our_doubles): # STEP 2 # Get the smallest difference between the pairs so our steps don't skip anything smallest = smallest + step step = abs(min(__import__("itertools").starmap(__import__("operator").sub, __import__("itertools").combinations(our_doubles, 2)), key=lambda x:abs(x) or float("inf"))) for elemant in our_doubles: if new_doubles.count(elemant) != our_doubles.count(elemant) and elemant < smallest + step: # ^^^^^^ NEXT NUMBER new_doubles.append(elemant) print(*new_doubles, sep=" ")  If there's anything you need help understanding, just ask. It's quite simply those three steps, though. We're using concurrency here and concurrency is cool. package main import ( "fmt" "time" ) func main() { unsorted := []int{4, 6, 9, 21, 11, 2, 8, 19, 5, 100, 99, 1, 98, 95, 97, 96} sorted := make(chan int) for _, x := range(unsorted) { go func(a int) { time.Sleep(time.Millisecond * time.Duration(a)) sorted <- a }(x) } for i := 0; i < len(unsorted); i++ { fmt.Printf("%d ", <-sorted) } fmt.Println() }  All the answers I see here use only the one old-fashioned concept of numerical sorting. People naturally think of numbers in terms of the words used to name them, and therefore I offer a more human-friendly solution. It's written in Python for readability, you shouldn't have any issues with this. class NumberSorter(): def __init__(self): self.nc = 'zottffssen' def sortNumbers(self,nl): return sorted(nl, key = lambda x: self.nc[int(str(x)[0])]) if __name__ == '__main__': c = NumberSorter() i = [int(x.strip()) for x in raw_input().split()] print(' '.join([str(x) for x in c.sortNumbers(i)]))  C++ #include <iostream> #include <vector> using namespace std; void makeAllCombos(const int length, int pos, vector<int> fromAbove, vector< vector< int > >& comboStore) { vector<int> temp; for(int i = 0; i < length; i++) { temp = fromAbove; temp.push_back(i); if(pos < length) { makeAllCombos(length, pos+1, temp, comboStore); } else { comboStore.push_back(temp); } } return; } void leaveJustPermutations(vector< vector< int > >& combinations) { vector<int> numsPresent; bool add = true; for(int i = (combinations.size() - 1); i >= 0; i--) { numsPresent.clear(); add = true; for(int j = 0; ((j < combinations[i].size()) && (add == true)); j++) { for(int k = 0; k < numsPresent.size(); k++) { if(combinations[i][j] == numsPresent[k]) { combinations.erase(combinations.begin()+i); add = false; break; } } numsPresent.push_back(combinations[i][j]); } } return; } void findSortedArray(vector<double>& numsToSort, vector< vector< int > >& perms) { for(int i = (perms.size() - 1); i >= 0; i--) { for(int j = 0; j < perms[i].size()-1; j++) { if(numsToSort[perms[i][j]] > numsToSort[perms[i][j+1]]) { perms.erase(perms.begin()+i); break; } } } return; } int main() { vector<double> nums; vector< vector < int > > combos; vector<int> seed; seed.clear(); double temp; while(cin >> temp) { nums.push_back(temp); } makeAllCombos(nums.size(), 1, seed, combos); leaveJustPermutations(combos); findSortedArray(nums, combos); for(int j = 0; j < combos[0].size(); j++) { cout << " " << nums[combos[i][j]]; } cout << endl; return 0; }  Here's my sort algorithm. It's super slow -- a list of 7 entries takes about 15 minutes to sort and takes about 42 MB of memory. However, it does complete the task. I hope the student is mighty patient. The code is pretty self explanatory. It computes all combinations of length equal to the number of numbers that need to be sorted. It then throws out all combinations that aren't permutations (i.e. they have the same element more than once or fails to include an element). It then checks all possible permutations for permutations that sort the numbers and then throws away the rest. It then spits out the sorted array resulting from the application of the first successful permutation to the original array. The code could be (somewhat) salvaged, but it involves solving a more difficult problem, i.e. computing permutations of a given length instead of selecting combinations of a given length which are also permutations. Here's an implementation of sleep sort in go. It works with doubles (but ignores sub-integer accuracy as a bonus). package main import ( "fmt" "runtime" "time" ) func main() { numCPU := runtime.NumCPU() maxProcs := numCPU runtime.GOMAXPROCS(maxProcs) nums := []float64{8.0, 9.0, 3.0, 5.0, 6.0, 4.0, 1.0, 2.0} numNums := len(nums) c := make(chan float64) go func() { for _, value := range nums { go func(val float64) { time.Sleep(time.Duration(val) * time.Second) c <- val }(value) } }() readCount := 0 for sortedVal := range c { fmt.Println(sortedVal) readCount++ if readCount == numNums { close(c) } } } package main import ( "fmt" "runtime" "time" ) func main() { numCPU := runtime.NumCPU() maxProcs := numCPU runtime.GOMAXPROCS(maxProcs) nums := []float64{8.0, 9.0, 3.0, 5.0, 6.0, 4.0, 1.0, 2.0} numNums := len(nums) c := make(chan float64) go func() { for _, value := range nums { go func(val float64) { time.Sleep(time.Duration(val) * time.Second) c <- val }(value) } }() readCount := 0 for sortedVal := range c { fmt.Println(sortedVal) readCount++ if readCount == numNums { close(c) } } }  # PHP Absolutely, the best sorting algorythm ever created. Copy code into file: define('SORTED', TRUE); define('NOT_SORTED', FALSE); // Get the numbers from the command line.$nums = $argv; // First arg is the script, so remove that plz. array_shift($nums);

$start_time = microtime(true);$sorted = badsort($nums);$end_time = microtime(true);
$total_time = ($end_time - $start_time); // Amazing sort alogryhmics. print implode(', ',$sorted) . PHP_EOL;
print "Time taken: {$total_time} seconds.\n"; // Sorts an array by awesome methods. function badsort(array$nums = array()) {
while(!sorted($nums)) {$nums = swapnums($nums); } // At this point,$nums has sort.
return $nums; } // Swaps two random keys in the array. function swapnums(array$nums = array()) {
$key1 = rand(0, count($nums) - 1);
$key2 = rand(0, count($nums) - 1);
$tmp =$nums[$key1];$nums[$key1] =$nums[$key2];$nums[$key2] =$tmp;
return $nums; } // Checks to see if an array of numbers is sorted. function sorted(array$nums = array()) {
// Ensure each number is greater than the one before it.
for($i = 1;$i < count($nums);$i++) {
if ($nums[$i] < $nums[$i - 1]) {
return NOT_SORTED;
}
}
return SORTED;
}


Run code by passing in list of numbers:

> php badsort.php 4 3.2 1 1 2 3 8 1 2 8


Output will look like: (times will vary greatly)

> 1, 1, 1, 2, 2, 3, 3.2, 4, 8, 8
> Time taken: 0.76796698570251 seconds.

• Where to pass list of numbers? Is integer only? – Emil Vikström Dec 29 '13 at 11:58
• @EmilVikström - You run it through command-line and pass list of numbers to the script like I showed... – donutdan4114 Dec 29 '13 at 17:05

OK, second attempt at answering since the rules have changed.

O(n) in C

Here's a sort which runs in more-efficient O(n) time:

void sort(double *array, int length)
{
double l;
int i, j;

for (j = 0, l = -DBL_MAX; l < DBL_MAX; l = nextafter(l, DBL_MAX))
{
for (i = j; i < length; i++)
if (array[i] == l)
{
double t = array[j];
array[j] = array[i];
array[i] = t;
j++;
}
}
}


Unfortunately outputting the array is an as-yet un-solved computing problem, so I cannot provide source for that operation, but I hope this gets you at least some of the way there.

# Clojure

I'd probably include some verbiage to the effect of

"I'd love to give you the answer - but since this is obviously homework I'll give you a working version written in a slightly different language and you can just translate it to whatever you need. Best of luck!"

(sort (map read-string (re-seq #"[\d-.]+" (read-line))))


It's complete, correct, and works as expected - but being written in a Lisp variant ought to put it out of reach for the average troller. Best if used in answer to a question tagged as C or Java or something completely unrelated.

The follow-up comments can be hilarious:

OP: What is "map"? I know what is "sort" but I never hear of "map"?

Me: Oh, map is a function which takes as its arguments a function f and a variable number of collections, and returns a lazy sequence consisting of the result of applying f to the set of first items of each collection, followed by applying f to the set of second items in each collection, until any one of the collections is exhausted. Any remaining items in other collections are ignored. Function f should accept number-of-colls arguments. Documentation here. Best of luck!

OP: Umm...OK, but what then what is "re-seq"? I do not know what are values of "re" and "seq"?

Me: Do you understand regular expressions?

OP: I think we cover that in next class?

Me: Well, wait until you get done with that class, then come back to this! Have fun!

# SuperSort

SuperSort is one of the easiest to implement and most efficient sort ever created. Here's what it looks like:

import sys
import random

n_list = []
found = False

if len(list) == 0:
n_list = [n_val]
return n_list

for val in list:
n_list.append(n_val)
found = True
n_list.append(val)
n_list.append(n_val)
return n_list

def rand_numbers():
random.seed(None)
list = [random.randint(-10000000, 10000000)/100000000.0 for i in range(10000)]
return list

def supersort():
list = rand_numbers()
n_list = []
for val in list:
print(n_list)

supersort()


It is able to sort an array in O(n!)! That's incredibly fast for most purposes! It means you can take an array with 10000 numbers and have it run in 7 seconds!

The algorithm doesn't actually sort; it just creates a new list and adds the numbers in order.

On every call of the add function, it makes n-1 iterations.

As such, it makes n*(n-1)/2 iterations in total.

Also, the time taken by Timsort for a 10000 numbers array is the following:

0m0.039s


This isn't the worst sort (wait, it isn't even a sort!), but it's not very efficient either.

Sorting? Wow, what a difficult question.

Thankfully, I have my army of monkeys, ready to bash at the keyboard.

import random
while True: print chr(random.randrange(48,127)),


By the Infinite Monkey Theorem, at some point in time, it will output your array sorted.

(Good luck on waiting for that point, though.)

# Java

This is very similar to my other answer; only many times worse.

public static void sort(double[] array) {
int currentSize = 2;
while (!isSorted(array)) {
double[] copy = Arrays.copyOf(array, currentSize);
if (!isSorted(copy)) {
Random rnd = new Random();
int i1 = rnd.nextInt(copy.length);
int i2 = rnd.nextInt(copy.length);
double val = copy[i1];
copy[i1] = copy[i2];
copy[i2] = val;
currentSize = 2;
}
System.arraycopy(copy, 0, array, 0, copy.length);
currentSize++;

}
}
public static boolean isSorted(double[] array) {
int direction = (((int) (Math.random() * 2)) << 1) - 1;

int index = 0b11111111111111111111111111111111;
index ^= index;
double element = array[0];
while (++index < array.length) {
if ((element - array[index]) * (direction * -1) < 0) {
return false;
}
element = array[index];
}

return true;
}


This is almost bogobogosort, but with some big changes.

1. Like my other answer, it randomly decides which direction to sort in (the question did not specify which one, increasing or decreasing). I only considered the easiest cases, increasing and decreasing.
• as a direct result of this, there is a chance that an ArrayIndexOutOfBoundsException will be thrown.
2. (This one is the real time-sucker). Instead of randomizing the entire array (up to the current size it deals with), it randomly selects two elements and swaps them. Thus, it works as follows:
1. Check if the array is in order. If it is, then we are done. Otherwise:
2. Consider the first (currentSize) elements of the array (currentSize is initially 2). If they are sorted, proceed to step 4. Otherwise, do step 3.
3. Pick two of those elements - they may be the same - and swap them. Reset currentSize to 2. Goto step 1.
4. Increment currentSize. Goto step 1. (could goto 2, but this way is easier implementation (slightly)).

While implementing this (with a strategically placed System.out.println), I discovered that an array that took about a minute with bogobogosort took 4 minutes with this sort and still was not done.

A high concurrency sorting implementation using the "Sleep Sort" algorithm.

package util;
import java.util.Arrays;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;

public class LinearTimeConcurrentSorter {

/**
* An ExecutorService to be reused by all calls for a given instance.
* This is done to allow resource-sharing where applicable.
*/
private final ExecutorService executor;

/**
* Construct a <code>LinearTimeConcurrentSorter</code> using a cached thread
* pool <code>ExecutorService</code>.
*/
private LinearTimeConcurrentSorter() {
}

/**
* Construct a <code>LinearTimeConcurrentSorter</code> that uses a provided
* ExecutorService. Note that this could result in inferior performance if
* you don't know what you're doing, and is provided for more advanced use
* cases.
*
* @param executor
*/
private LinearTimeConcurrentSorter(ExecutorService executor) {
this.executor = executor;
}

/**
* Cleanly shutdown the executor.
*/
public void shutdown() {
executor.shutdown();
}

/**
*
* @param array
* @throws InterruptedException
*/
public void sort(final Double[] array) throws InterruptedException {

/**
* This <code>AtomicInteger</code> is shared between all
* <code>AppenderTask</code> instances to ensure they each write to a
* unique index, thus avoiding race conditions.
*/
final AtomicInteger indexCounter = new AtomicInteger(0);

/**
* Used to ensure each <code>AppenderTask</code> is started
* simultaneously. The loop that prepares the tasks counts down, but
* each task will wait until this reaches 0 to begin.
*/
final CountDownLatch preLatch = new CountDownLatch(array.length);

/**
* This is used to ensure every <code>AppenderTask</code> instance has
* completed before the sort call terminates.
*/
final CountDownLatch postLatch = new CountDownLatch(array.length);

/**
* Note that while this does create some additional overhead per element
* for starting threads, the fact that we only need one loop over the
* array means this will run in O(n) time. Profiling should be conducted
*/
for (double value : array) {
preLatch, postLatch);
preLatch.countDown();
}
postLatch.await();
}

private static class AppenderTask implements Runnable {

/**
* The value this task was created to store.
*/
private final double value;

/**
* A counter shared by all tasks created to sort a given array. This
* ensures each task writes to a unique index of the array.
*/
private final AtomicInteger indexCounter;

/**
* The array to output to.
*/
private final Double[] array;

/**
* Counted down by the sorter to ensure all tasks for a given array are
* started simultaneously.
*/
private final CountDownLatch preLatch;

/**
* Counted down once by each task to let the sorter know when they have
* all completed.
*/
private final CountDownLatch postLatch;

Double[] array, CountDownLatch preLatch,
CountDownLatch postLatch) {
this.value = value;
this.indexCounter = indexCounter;
this.array = array;
this.preLatch = preLatch;
this.postLatch = postLatch;
}

public void run() {
try {
/**
* Wait for all tasks to have been started to ensure fair
* ordering.
*/
preLatch.await();

/**
* Wait based on the value given to this task. In doing so, we
* ensure tasks for lower values are given opportunity to claim
* lower indices in the array.
*/

} catch (InterruptedException e) {
/**
* This should only occur if the <code>ExecutorService</code>
* provided to the <code>ConcurrentSorter</code> is shutdown
* prematurely - in which case we follow best practices and
* "fail fast".
*/
throw new IllegalStateException(e);
}

/**
* Get the current array index and increment the counter for the
*/
int index = indexCounter.getAndIncrement();

/**
* Update our claimed index in the array and count down the latch.
*/
array[index] = value;
postLatch.countDown();
}
}

/**
* This main function simply expects it's arguments to be "well-formed" doubles.
* Alternate input methods are left as an exercise to the reader.
* @param args
* @throws InterruptedException
*/
public static void main(String[] args) throws InterruptedException {

/**
* Convert <code>String</code> arguments to <code>Double</code>s.
*/
Double[] array = new Double[args.length];
int i;
for (i = 0; i < args.length; i++) {
array[i] = Double.parseDouble(args[i]);
}

/**
* Create a new sorter, use it, and clean up any threads it still has running.
*/
LinearTimeConcurrentSorter sorter = new LinearTimeConcurrentSorter();
sorter.sort(array);
sorter.shutdown();

System.out.println("sorted: " + Arrays.deepToString(array));

}
}


Just so we're clear - many of the comments are only superficially correct, if at all. This should "mostly work" for simple test data sets (handful of numbers in the ~1-20 range), but it fails miserably in practice and is an all-around terrible idea.

Just noticed at least one other sleep sort answer submitted before I wrote this, so I definitely can't claim originality.

Here is a java solution that may be of use:

public static <T> void sort(List<T> list){
Collections.sort(list, (T a, T b) -> (System.console().readLine("Is %1$s bigger than %1$s? (y/n) ", a, b).equals("y")?(-1):(System.console().readLine("Is %1$s smaller than %1$s? (y/n) ", a, b).equals("y")?(1):0);
}


It uses cutting-edge java 8 features that the OP certainly doesn't have, plus it requires they launch it in an environment with a console present, plus it requires they manually compare all items to be sorted.

Quasi-bubble sort (bubble sort with first element at the end)

def sort(x):
L = len(x)
while L > 0:
for i in range(L):
if x[i-1] > x[i]:
x[i-1], x[i] = x[i], x[i-1]
L -= 1

return x


Example output:

python bubble.py
10 9 1 3 2
[2.0, 3.0, 9.0, 10.0, 1.0]


# Shell Script

#!/bin/sh
echo "Enter your input, one number a line. Press Ctrl-d when you are done." >&2
sort -n


# Python

print "the array sorted"

• boring ... you can do better than that. – hildred Dec 28 '13 at 17:36

Python

Sort the list, using the slowsort algorithm (from http://ivanych.net/doc/PessimalAlgorithmsAndSimplexityAnalysis.pdf, p4):

def do_sort(ar, i, j):
"""Sorts the array ar from index i to index j."""
if i >= j:
return
else:
m = (i + j) // 2
do_sort(ar, i, m)
do_sort(ar, m + 1, j)
if ar[m] > ar[j]:
tmp = ar[j]
ar[j] = ar[m]
ar[m] = tmp
do_sort(ar, i, j - 1)


This will almost work except when :-)

Language Python

>>> def sort(arr):
_max = max(arr)
buckets = [0]*(_max+1)
for elem in arr:
buckets[elem] = 1
return (index for index, elem in enumerate(buckets) if elem == 1)

>>> list(sort(range(10,1,-1)))
[2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> list(sort([10**10, 1]))

Traceback (most recent call last):
File "<pyshell#2012>", line 1, in <module>
list(sort([10**10, 1]))
File "<pyshell#2010>", line 3, in sort
buckets = [0]*(_max+1)
OverflowError: cannot fit 'long' into an index-sized integer


# PYTHON

myArray = [0.2, 1.7534, 0.63, 12.435, 23.0, 7.6, 8.2, 0.7, 3.9]
myArray.sort()
print(myArray)

• This code-trolling challenge requires your answer to be "utterly useless in practice." I find your answer to be useful and practical. Thumbs down. – Darren Stone Jan 1 '14 at 21:38

I actually saw someone implement this in my undergrad. Start at the min value in the array, and iterate to the max value with some epsilon threshold. An order of magnitude increase in efficiency is an order of magnitude increase in runtime!

Luckily, the code is linear in the size of the array.

https://github.com/artoonie/shittycode/blob/master/sort.cpp

• Whilst this may theoretically answer the question, it would be preferable to include the essential parts of the answer here, and possibly provide the link for reference. – John Dvorak Dec 28 '13 at 23:11