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

Question

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

^{Note: This is a code-trolling question. Please do not take the question and/or answers seriously. More information here.}

Answer 1

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?

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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.

Answer 6

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

Answer 7

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.

Answer 8

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.

Answer 9

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!

Answer 10

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

def add(n_val, list):
    n_list = []
    found = False

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

    for val in list:
        if val > n_val and not found:
            n_list.append(n_val)
            found = True
        n_list.append(val)
    if not found:
        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:
        n_list = add(val, n_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!

Answer notes:

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.

Answer 11

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

Answer 12

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.

Answer 13

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() {
    this(Executors.newCachedThreadPool());
  }

  /**
   * 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
     * if you're unsure about the impact of this tradeoff.
     */
    for (double value : array) {
      Runnable task = new AppenderTask(value, indexCounter, array,
          preLatch, postLatch);
      executor.execute(task);
      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;

    public AppenderTask(double value, AtomicInteger indexCounter,
        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.
         */
        Thread.sleep((long) value);

      } 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
       * next task.
       */
      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.

Answer 14

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.

Answer 15

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]

Answer 16

Shell Script

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

Answer 17

Python

print "the array sorted"

Answer 18

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)

Answer 19

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

Answer 20

PYTHON

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

Answer 21

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