276
votes
\$\begingroup\$

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.

Note: This is a question. Please do not take the question and/or answers seriously. More information here.

\$\endgroup\$
30
  • 48
    \$\begingroup\$ Stack Oversort \$\endgroup\$ Commented Dec 27, 2013 at 13:26
  • 6
    \$\begingroup\$ @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. \$\endgroup\$
    – IQAndreas
    Commented Dec 27, 2013 at 16:21
  • 2
    \$\begingroup\$ @Dukeling Yes, this is true. But since this is the first question in the category, I added the description here to introduce it. Further questions could simply reference the category and go to what the lazy OP asks. \$\endgroup\$ Commented Dec 27, 2013 at 17:14
  • 18
    \$\begingroup\$ 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! \$\endgroup\$
    – SimonT
    Commented Dec 28, 2013 at 4:21
  • 4
    \$\begingroup\$ I'm surprised no one has offered a solution based on sleep sort yet \$\endgroup\$ Commented Dec 28, 2013 at 11:02

141 Answers 141

1
2 3 4 5
179
votes
\$\begingroup\$

Here it is in java. It is utter cheating, unacceptable and unfixable because it creates a MySQL database, insert the number there, do a select with an ORDER BY clause and outputs the numbers given by MySQL. In fact, it is MySQL who is doing the sorting, not the program.

package sorter;

import java.sql.Connection;
import java.sql.DriverManager;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.util.ArrayList;
import java.util.List;
import javax.swing.JOptionPane;

public class SortingAlgorithm {

    private static final String CREATE_DB = "CREATE DATABASE sorting";
    private static final String DROP_DB = "DROP DATABASE sorting";
    private static final String CREATE_TABLE = "CREATE TABLE sorting.sorting ( num double not null )";

    public static void main(String[] args) throws Exception {
        Class.forName("com.mysql.jdbc.Driver");
        List<Double> doubles = new ArrayList<>(50);
        String typed;
        do {
            typed = JOptionPane.showInputDialog(null, "Type a double:");
            if (typed != null) doubles.add(Double.parseDouble(typed));
        } while (typed != null);

        List<Double> sorted = new ArrayList<>(50);

        try (Connection con = DriverManager.getConnection("jdbc:mysql://localhost:3306", "root", "root")) {
            try (PreparedStatement ps = con.prepareStatement(CREATE_DB)) {
                ps.executeUpdate();
            }
            try (PreparedStatement ps = con.prepareStatement(CREATE_TABLE)) {
                ps.executeUpdate();
            }

            for (Double d : doubles) {
                try (PreparedStatement ps = con.prepareStatement("INSERT INTO sorting.sorting (num) VALUES (" + d + ")")) {
                    ps.executeUpdate();
                }
            }

            try (
                    PreparedStatement ps = con.prepareStatement("SELECT * FROM sorting.sorting ORDER BY num");
                    ResultSet rs = ps.executeQuery())
            {
                while (rs.next()) {
                    sorted.add(rs.getDouble("num"));
                }
            }
            try (PreparedStatement ps = con.prepareStatement(DROP_DB)) {
                ps.executeUpdate();
            }
        }

        JOptionPane.showMessageDialog(null, "The array sorted is: " + sorted);
    }
}
\$\endgroup\$
17
  • 103
    \$\begingroup\$ That's actually a little too close to home for what many Java coders would consider an acceptable match of solution to spec!! \$\endgroup\$ Commented Dec 27, 2013 at 12:00
  • 10
    \$\begingroup\$ Also consider the case where you need to sort a very large number of objects. Sorting them "outside the program" in a database is a feasable solution. \$\endgroup\$ Commented Dec 27, 2013 at 12:44
  • 40
    \$\begingroup\$ Not enough abstraction here. You need at least 10 interfaces, 20 implementations, enums, unit tests, coverage tests, Maven, integration tests, mocks... \$\endgroup\$ Commented Dec 27, 2013 at 19:47
  • 6
    \$\begingroup\$ @NaftuliTzviKay We should create a MySQLSortEnterpriseEdition to implement your idea. Will Victor agree to GPL-license the code here so we can get started? \$\endgroup\$
    – Joe Z.
    Commented Dec 27, 2013 at 21:32
  • 14
    \$\begingroup\$ @JoeZ. Yes, my answer is lacking comments about the licensing model and I should make the user accept an EULA in the start of the program. But since I am giving it to the lazy OP, it is free for non-commercial use, including being useful to create the long-awaited premium MySQLSortEnterpriseEdidtion. \$\endgroup\$ Commented Dec 27, 2013 at 21:39
177
votes
\$\begingroup\$

Sometimes the community here doesn't like to help with homework. That's why you are getting so many joke answers. But I like to help. Here is a complete solution in 'C' (since I assume you want to learn "programming", not "scripting" with Java or Ruby). I've included many tips that I wish I had known when I was first learning

#include <stdio.h>

//Always use meaningful names for types
typedef unsigned char boolean;
#define True 't'
#define FALSE (!True)

//this is a really neat trick for swapping values efficiently
void swap(long* a,long *b) { *a=*a^*b;*b=*b^*a;*a=*a^*b; }

//Here's a readability improvement
#define until(condition) while(!(condition))

int main(int n, char*args[]){
  double *d;
  int i;
  char input[5];  //should be long enough for most doubles.
  boolean sorted = FALSE;

  //In C, you need to specify the array size beforehand, so ask
  printf("Please enter the length of the array\n");
  gets(input);
  //scan the input string and convert to a value
  sscanf(input,"%s",&input[0]);
  n=(long)atol(input);

  //allocate space, make sure you get the order of arguments right.
  d = calloc(sizeof(double),n); 

  //Get and sort the array
  until (sorted) {

     for (i=0;i<n;i++) {
        //It's important to always ask nicely
        printf("Please enter the %d%s array item\n",i,i==1?"st":"th");
        scanf("%lf",d+i);
     }
     //do a compare and exchange sort:
     sorted = !sorted;  //not sorted
     //check all the items
     printf("%d %d\n",i,n);
     for (i=1;i<n;i++) {
        //compare
        if (d[i]<d[i-1]) {
          //exchange 
          swap(d+i,d+i-1);
          sorted = FALSE;
        }
     }
     //show results
     printf("The array is%ssorted\n",sorted?" ":" not "); }
  //use the --> "downto operator" for counting downto 0. 
  for (;n-->0;) printf("%lf\n",*d++);
  }
\$\endgroup\$
18
  • 32
    \$\begingroup\$ almost all the advice is wrong, and it simply keeps asking for the input list until you enter it already sorted. \$\endgroup\$
    – AShelly
    Commented Dec 27, 2013 at 16:44
  • 47
    \$\begingroup\$ +1, for 1st, 2th, 3th, 4th... and the downto operator--very advanced C programing techniques. \$\endgroup\$
    – Kaya
    Commented Dec 27, 2013 at 17:31
  • 5
    \$\begingroup\$ Should use sscanf(input, "%5s", &input[0]), otherwise there might be overrun bugs while parsing the input. And input should be declared char input[sizeof(int)+1], for backward compatibility with 64-bit systems. \$\endgroup\$
    – sh1
    Commented Dec 28, 2013 at 1:17
  • 12
    \$\begingroup\$ i==1?"st":"th" hahaha... \$\endgroup\$
    – Guy Sirton
    Commented Dec 28, 2013 at 7:42
  • 15
    \$\begingroup\$ Java has garbage collection. Therefore Java is for "scripting", not real programming. That's basic CS101. (so says the troll.) \$\endgroup\$
    – AShelly
    Commented Dec 28, 2013 at 8:20
142
votes
\$\begingroup\$

C# - There's no kill like overkill

First of all, dear GiMmEtHaCoDeZ, let's try to break down your task:

  1. Read the numbers
  2. Sort them
  3. Output the sorted numbers.

As "Divide and conquer" is very important strategy when working with software problems, lets tackle them one at a time

1. Reading

Another important issue in software is versatility. Since it's not specified how the user will input the numbers, that can happen via the console, via a file, via a web service, etc. Maybe even some method that we can't think of at the moment. So, it's important that our solution will be able to accommodate various types of input. The easiest way to achieve that will be to extract the important part to an interface, let's say

public interface IDoubleArrayReader
{
  IEnumerable<double> GetDoubles();

  DoubleArrayReaderType Type {get;}
}

where DoubleArrayReaderType is an enumeration given with

public enum DoubleArrayReaderType
{
  Console,
  File,
  Database,
  Internet,
  Cloud,
  MockService
}

It's also important to make the software testable from the ground up, so an implementation of the interface will be

public class MockServiceDoubleArrayReader : IDoubleArrayReader
{
    IEnumerable<double> IDoubleArrayReader.GetDoubles()
    {
      Random r = new Random();  
      for(int i =0; i<=10; i++)
      {
        yield return r.NextDouble();
      }
    }

    DoubleArrayReaderType IDoubleArrayReader.Type 
    {
      get
      {
        return DoubleArrayReaderType.MockService;
      }
    }
}

Next, the logical question is how we will know to load the appropriate IDoubleArrayReader into the code. That's easy as long as we use a simple factory:

public static class DoubleArrayInputOutputFactory
{
  private static Dictionary<DoubleArrayReaderType, IDoubleArrayReader> readers;

  static DoubleArrayInputOutputFactory()
  {
      readers = new Dictionary<DoubleArrayReaderType, IDoubleArrayReader>();
      foreach (Type type in Assembly.GetExecutingAssembly().GetTypes())
      {
        try
        {
          var instance = Activator.CreateInstance(type);
          if (instance is IDoubleArrayReader)
          {
            readers.Add((instance as IDoubleArrayReader).Type, 
                        (instance as IDoubleArrayReader));
          }
        }
        catch
        {
          continue;
        }
      }
  }

  public static IDoubleArrayReader CreateDoubleArrayReader(DoubleArrayReaderType type)
  {
    return readers[type];
  }
}

Note that, we use reflection to load all active readers, so any future extensions will be automatically available Now, in the main body of out code we just do:

IDoubleArrayReader reader = DoubleArrayInputOutputFactory
                           .CreateDoubleArrayReader(DoubleArrayReaderType.MockService);
var doubles = reader.GetDoubles();

2. Processing (sorting)

Now we need to process, i.e. sort the numbers we have acquired. Note that the steps are completely independent of each other, so to the sorting subsystem, it does not matter how the numbers were inputed. Additionally, the sorting behavior is also something that is subject to change, e.g. we might need to input a more efficient sorting algorithm in place. So, naturally, we'll extract the requested processing behaviour in an interface:

public interface IDoubleArrayProcessor
{
  IEnumerable<double> ProcessDoubles(IEnumerable<double> input);

  DoubleArrayProcessorType Type {get;}
}

public enum DoubleArrayProcessorType
{
  Sorter,
  Doubler,
  Tripler,
  Quadrupler,
  Squarer
}

And the sorting behaviour will just implement the interface:

public class SorterDoubleArrayProcessor : IDoubleArrayProcessor
{
    IEnumerable<double> IDoubleArrayProcessor.ProcessDoubles(IEnumerable<double> input)
    {
      var output = input.ToArray();
      Array.Sort(output);
      return output;
    }

    DoubleArrayProcessorType IDoubleArrayProcessor.Type 
    {
      get
      {
        return DoubleArrayProcessorType.Sorter;
      }
    }
}

Of course, we will need a factory to load and manage the processing instances.

public static class DoubleArrayProcessorFactory
{
  private static Dictionary<DoubleArrayProcessorType, IDoubleArrayProcessor> processors;

  static DoubleArrayProcessorFactory()
  {
      processors = new Dictionary<DoubleArrayProcessorType, IDoubleArrayProcessor>();
      foreach (Type type in Assembly.GetExecutingAssembly().GetTypes())
      {
        try
        {
          var instance = Activator.CreateInstance(type);
          if (instance is IDoubleArrayProcessor)
          {
            processors.Add((instance as IDoubleArrayProcessor).Type, (instance as IDoubleArrayProcessor));
          }
        }
        catch
        {
          continue;
        }
      }
  }

  public static IDoubleArrayProcessor CreateDoubleArrayProcessor(DoubleArrayProcessorType type)
  {
    return processors[type];
  }

}

3. Writing the output

Nothing much to say here, as this is a process that mirror the input. In fact, we could combine the reading and writing factories into a single DoubleArrayInputOutputFactory, like this:

public interface IDoubleArrayWriter
{
  void WriteDoublesArray(IEnumerable<double> doubles);

  DoubleArrayWriterType Type {get;}
}

public enum DoubleArrayWriterType
{
  Console,
  File,
  Internet,
  Cloud,
  MockService,
  Database
}

public class ConsoleDoubleArrayWriter : IDoubleArrayWriter
{
    void IDoubleArrayWriter.WriteDoublesArray(IEnumerable<double> doubles)
    {
      foreach(double @double in doubles)
      {
        Console.WriteLine(@double);
      }
    }

    DoubleArrayWriterType IDoubleArrayWriter.Type 
    {
      get
      {
        return DoubleArrayWriterType.Console;
      }
    }
}


public static class DoubleArrayInputOutputFactory
{
  private static Dictionary<DoubleArrayReaderType, IDoubleArrayReader> readers;
  private static Dictionary<DoubleArrayWriterType, IDoubleArrayWriter> writers;

  static DoubleArrayInputOutputFactory()
  {
      readers = new Dictionary<DoubleArrayReaderType, IDoubleArrayReader>();
      writers = new Dictionary<DoubleArrayWriterType, IDoubleArrayWriter>();
      foreach (Type type in Assembly.GetExecutingAssembly().GetTypes())
      {
        try
        {
          var instance = Activator.CreateInstance(type);
          if (instance is IDoubleArrayReader)
          {
            readers.Add((instance as IDoubleArrayReader).Type, (instance as IDoubleArrayReader));
          }
        }
        catch
        {
          continue;
        }
      }

      foreach (Type type in Assembly.GetExecutingAssembly().GetTypes())
      {
        try
        {
          var instance = Activator.CreateInstance(type);
          if (instance is IDoubleArrayWriter)
          {
            writers.Add((instance as IDoubleArrayWriter).Type, (instance as IDoubleArrayWriter));
          }
        }
        catch
        {
          continue;
        }
      }

  }

  public static IDoubleArrayReader CreateDoubleArrayReader(DoubleArrayReaderType type)
  {
    return readers[type];
  }

  public static IDoubleArrayWriter CreateDoubleArrayWriter(DoubleArrayWriterType type)
  {
    return writers[type];
  }

}

Putting it all together

Finally, our main program will just use all this awesomeness we have already built, so the code will just be:

var doubles = reader.GetDoubles();
doubles = processor.ProcessDoubles(doubles);
writer.WriteDoublesArray(doubles);

where, e.g. we could define reader, writer and processor using

IDoubleArrayReader reader = DoubleArrayInputOutputFactory.CreateDoubleArrayReader(DoubleArrayReaderType.MockService);
IDoubleArrayProcessor processor = DoubleArrayProcessorFactory.CreateDoubleArrayProcessor(DoubleArrayProcessorType.Sorter);
IDoubleArrayWriter writer = DoubleArrayInputOutputFactory.CreateDoubleArrayWriter(DoubleArrayWriterType.Console);
\$\endgroup\$
18
  • 49
    \$\begingroup\$ Lol, ListSort Enterprise Edition© :-P +1 \$\endgroup\$
    – Doorknob
    Commented Dec 27, 2013 at 22:21
  • 14
    \$\begingroup\$ +1 for crazy overcoding. I suggest you break your answer into 3 or more 'module' answers so that I may +1 them individually \$\endgroup\$
    – greggo
    Commented Dec 27, 2013 at 23:50
  • 15
    \$\begingroup\$ And the cherry on top is that it's actually using a library sort:) It's completely to the spec, and completely useless \$\endgroup\$
    – SWeko
    Commented Dec 28, 2013 at 0:28
  • 9
    \$\begingroup\$ That... was... beautiful. \$\endgroup\$
    – Andrew
    Commented Dec 28, 2013 at 6:55
  • 7
    \$\begingroup\$ Using DI will just confuse the OP, as this is just a quick example. \$\endgroup\$
    – SWeko
    Commented Dec 28, 2013 at 16:29
130
votes
\$\begingroup\$

Even more literal interpretation:

echo " aaehrrty"

that is, "the array" sorted.

\$\endgroup\$
4
  • 5
    \$\begingroup\$ I came here to post this. \$\endgroup\$ Commented Dec 28, 2013 at 17:08
  • 5
    \$\begingroup\$ save as file sort.sh and call as sh sort.sh "an array of doubles" \$\endgroup\$
    – Kyss Tao
    Commented Dec 28, 2013 at 21:29
  • \$\begingroup\$ I think you missed the "the user inputs an array of doubles". \$\endgroup\$ Commented Jan 1, 2014 at 23:25
  • 1
    \$\begingroup\$ @Dukeling that's the point of what Kyss Tao's comment. "an array of doubles" can be passed to the script as a command-line argument. \$\endgroup\$ Commented Jan 2, 2014 at 21:21
106
votes
\$\begingroup\$

Perl

Out of all of the things I've done for CodeGolf.SE, this probably took the most time, at least a few hours.

$_[0]=eval<>;
for(0..$#{$_[0]}**2){
 @_[$#_+1]=[\(@{$_[$#_]}),$#{$_[$#_]}+1];
 for(1..$#{$_[$#_]}-$#_){
  if(eval('${'x$#_.'@{$_[$#_]}[$_-1]'.'}'x$#_)>eval('${'x$#_.'@{$_[$#_]}[$_]'.'}'x$#_)){
   ${$_[$#_]}[$#{$_[$#_]}]=$_;
  }
 }
 (${$_[$#_]}[${$_[$#_]}[$#{$_[$#_]}]-1],${$_[$#_]}[${$_[$#_]}[$#{$_[$#_]}]])=(${$_[$#_]}[${$_[$#_]}[$#{$_[$#_]}]],${$_[$#_]}[${$_[$#_]}[$#{$_[$#_]}]-1]);
}
for(0..~~@{$_[0]}){
 $\.=eval('${'x$#_.'${$_[$#_]}[$_-1]'.'}'x$#_).','
}
$\=~s/,*$//;$\=~s/^,*//;$\="[$\]";
print;

Input is of the form [2,4,5,7,7,3] and output is of the form [2,3,4,5,7,7].

I don't have time to explain now... be back later.

Anyways, there is something called an anonymous array in Perl. It is an array, but it has no name. What we do know, however, is a reference (memory location) that points to it. A series of numbers in square brackets creates an anonymous array, and it returns a reference to it.

This answer is built off of a series of anonymous arrays, the references to which are stored in @_. The input is turned into an anonymous array. We then create other anonymous arrays, each element of which is a reference to an element in the previous array. Instead of sorting the elements in the array, we sort the pointers to the elements in that array. Also, we create a new array for each step (and more) in the sort operation.

\$\endgroup\$
9
  • 3
    \$\begingroup\$ evil! evil! evil! \$\endgroup\$
    – DGM
    Commented Dec 28, 2013 at 0:24
  • 56
    \$\begingroup\$ about as decipherable as any other Perl script to me :) \$\endgroup\$ Commented Dec 28, 2013 at 0:32
  • 6
    \$\begingroup\$ @swelljoe Actually, $_ is an empty string at that point. I stored my desired output in $\ , which is the output record separator. \$\endgroup\$
    – PhiNotPi
    Commented Dec 28, 2013 at 2:58
  • 4
    \$\begingroup\$ @Andy simple. "How does it work?" \$\endgroup\$ Commented Dec 28, 2013 at 18:35
  • 1
    \$\begingroup\$ and all user-created variables have pretty names that follow all thinkable conventions \$\endgroup\$ Commented Dec 29, 2013 at 13:49
79
votes
\$\begingroup\$

Python

Gives the user a sorted array by removing all elements not in sorted order from the input array.

import sys

sorted = []
for number in map(float, sys.stdin.read().split()):
    if not sorted or number >= sorted[-1]:
         sorted.append(number)
print sorted 

The algorithm goes through the list only adding each element if it won't make the list unsorted. Thus the output is a sorted list, just not one that's contains all the elements of the original list. If the op just checks if the list is in sorted order he may not notice that the output is missing values.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Please see other answers before posting your own. You should add the name of your language. To answer this question you also need to briefly explain what you are doing to troll the OP. \$\endgroup\$
    – Wasi
    Commented Dec 27, 2013 at 17:14
  • 5
    \$\begingroup\$ Hehe, this one actually made me laugh out loud. Anyway, I agree that a little better explanation would be helpful. \$\endgroup\$
    – oconnor0
    Commented Dec 28, 2013 at 3:49
  • 2
    \$\begingroup\$ Is the double call to sys.stdin.read() a typo or part of the real trolling-answer? Surely it would frustrate the OP to give the array as input and continue to wait for the result... \$\endgroup\$
    – Bakuriu
    Commented Dec 28, 2013 at 7:51
  • \$\begingroup\$ Wow, that's evil all right. \$\endgroup\$
    – Sylver
    Commented Dec 28, 2013 at 14:02
  • 13
    \$\begingroup\$ A O(n) sort algorithm. Nice. \$\endgroup\$
    – ejrb
    Commented Jan 2, 2014 at 13:59
64
votes
\$\begingroup\$

Bash, 54 characters

A lot of answers using slow inefficient languages like C and Python... let's speed things up a bit by offering a solution in the mother of all scripting languages: Bash.

I know what you're thinking - Bash can't even handle floating point arithmetic, so how is it going to sort, right? Well, behold, my implementation of the mighty SleepSort algorithm:

#!/bin/bash

for i in $@; do echo -n $(sleep $i)$i' '& done
echo "Leveraging the power of your $(grep -c ^processor /proc/cpuinfo) cores to \
sort optimally by spawning $(jobs -l | wc -l) concurrent sorting threads..."
wait
echo -e "\nThe array sorted."

The program is provided with input as commandline arguments. Sample run:

> ./sleepsort.sh 7 1 4 3 2.752 6.9 0.01 0.02
Leveraging the power of your 4 cores to optimally by spawning 8 concurrent sorting threads...
0.01 0.02 1 2.752 3 4 6.9 7
The array sorted.

This also has the advantage of perhaps being the shortest of all working algorithms presented here. That's right - one mighty line of bash, using only bash builtins and not calling any external binaries (that is, if you don't count the purely optional verbose output). Unlike the bogosorts, its runtime is deterministic.

Tip: An effective optimisation is to divide the input numbers by a factor before sorting. Implementation is left up to the reader.

Edit:

Shortened 54-char golf version with less pretty-printing:

#!/bin/sh
for i in $@;do echo $(sleep $i)$i&done;wait
\$\endgroup\$
11
  • 11
    \$\begingroup\$ Trolling 1: The algorithm does work, but is obviously potentially extremely slow - it spawns a thread for each number, sleeping for that number of seconds before outputting the number (which is thus in order). Trolling 2: Additionally, most of the code is spent on writing a nice comment about how many threads its spawning, and unnecessarily and gratuitously reads and parses the system's cpu info just for the sake of some extra verbose output. Trolling 3: It outputs "the array sorted" at the end, which seems to be the done thing. Trolling 4: The user cannot cancel the "sort" by hitting ctrl-c. \$\endgroup\$
    – Riot
    Commented Dec 28, 2013 at 1:03
  • 4
    \$\begingroup\$ 5. It only works on GNU/Linux, due to use of /proc/cpuinfo. \$\endgroup\$
    – kps11346
    Commented Dec 28, 2013 at 2:37
  • 5
    \$\begingroup\$ Extremely creative solution, by the way :) \$\endgroup\$
    – dmitry
    Commented Dec 28, 2013 at 19:37
  • 8
    \$\begingroup\$ This is amazing. I can't even express how awesome that is. I'm considering using that actively, because WHY NOT. \$\endgroup\$
    – user11485
    Commented Dec 28, 2013 at 20:37
  • 4
    \$\begingroup\$ I actually genuinely do have a variant of this in use in production somewhere. But in that situation, the runtime of the process is important, so that's my excuse... \$\endgroup\$
    – Riot
    Commented Dec 28, 2013 at 21:01
63
votes
\$\begingroup\$

JavaScript has a built-in sort() function, you can use it like this:

var numbers = [6, 2.7, 8];
numbers.sort();
// => [2.7, 6, 8]

...oh, totally forgot to mention, it sorts in lexicographic order, i.e. 10 < 9 and 9 < -100. Probably that's what you expect anyway.

\$\endgroup\$
1
  • 8
    \$\begingroup\$ That's even better because it's a built-in function. \$\endgroup\$ Commented Dec 29, 2013 at 22:52
60
votes
\$\begingroup\$

(jPL) jQuery Programming Language

You must use jQuery for that. A simple solution to this problem is the following one:

function jSort() {
    var a = 0.0; // position 1
    var b = 0.0; // position 2
    var c = 0.0; // position 3

    var arr = [];
    var nArr = [];

    // don't forget to validate our array!
    if (window.prompt("You must only type double values. Type 1 if you accept the terms.") != 1) {
        alert("You can't do that.");
        return;
    }

    for (var i = 0; i < 3; i++) {
        if (i == 0) {
            var a = window.prompt("Type a double value");
            arr.push(a);
        }
        if (i == 1) {
            var b = window.prompt("Type a double value");
            arr.push(b);
        }
        if (i == 2) {
            var c = window.prompt("Type a double value");
            arr.push(c);
        }
    }

    // Now the tricky part
    var b1 = false;
    var b2 = false;
    var b3 = false;
    for (var i = 0 ; i < 3; i++) {
        // check if the variable value is the same value of the same variable which now is inside the array
        if (i == 0) {
            if (a == arr[i]) {
                b1 = true;
            }
        }

        if (i == 1) {
            if (b == arr[i]) {
                b2 = true;
            }
        }

        if (i == 2) {
            if (c == arr[i]) {
                b3 = true;
            }
        }
    }

    if (b1 == true && b2 == true && b3 == true) {
        if (arr[0] > arr[1]) {
            if (arr[0] > arr[2]) {
                nArr.push(arr[0]);
            } else {
                nArr.push(arr[2]);
            }
        }

        if (arr[1] > arr[0]) {
            if (arr[1] > arr[2]) {
                nArr.push(arr[1]);
            }
            else {
                nArr.push(arr[2]);
            }
        }

        if (arr[2] > arr[0]) {
            if (arr[2] > arr[1]) {
                nArr.push(arr[2]);
            } else {
                nArr.push(arr[1]);
            }
        }

        console.log(arr.sort(function (a, b) { return a - b }));
        alert(arr.sort(function (a, b) { return a - b }));
    }
}

jSort();
\$\endgroup\$
9
  • 72
    \$\begingroup\$ "-1 not enough jQuery" \$\endgroup\$
    – grc
    Commented Dec 27, 2013 at 14:18
  • 55
    \$\begingroup\$ I particularly like how this doesn’t actually use jQuery. \$\endgroup\$
    – KRyan
    Commented Dec 27, 2013 at 15:24
  • 8
    \$\begingroup\$ -1 Your array naming must include Hungarian notation in it, specifically jQuery objects signified using $, arrays using a and results of window.prompt as p. \$\endgroup\$ Commented Dec 27, 2013 at 15:48
  • 2
    \$\begingroup\$ The "tricky part" is elegant. OP, strive to have that kind of code structure someday. \$\endgroup\$ Commented Dec 28, 2013 at 8:05
  • 2
    \$\begingroup\$ That F'n doble "validation" LOOOOOOOOOOOOL omg omg day made! edited for less caps \$\endgroup\$
    – HC_
    Commented Dec 30, 2013 at 18:00
54
votes
\$\begingroup\$

Ruby

print "Input an array of doubles: "
gets
puts "the array sorted."

Fairly self-explanatory.

Or require the input to actually be "an array of doubles":

print "Input an array of doubles: "
g = gets until /an array of doubles\n/
puts "the array sorted."

Not using gets.chomp for extra evilness. Also using regex after trailing until, which is something I didn't even know you could do (thanks Jan Dvorak) to confuse OP even more!

\$\endgroup\$
9
  • 4
    \$\begingroup\$ Expanding on the idea, I would repeatedly ask for input until the user inputs the string an array of doubles. \$\endgroup\$
    – Wrzlprmft
    Commented Dec 27, 2013 at 17:56
  • \$\begingroup\$ @Wrz Ok, done :-) \$\endgroup\$
    – Doorknob
    Commented Dec 27, 2013 at 17:59
  • 2
    \$\begingroup\$ That's extra great because the poor OP will have to figure out how to get rid of a newline (because you use gets instead of gets.chomp). \$\endgroup\$
    – wchargin
    Commented Dec 27, 2013 at 21:17
  • \$\begingroup\$ @WChargin Yep, I had that in the first revision (see revision history) but removed it to be even more evil >:D EDIT: Oh wait, never mind, that was my other answer. I'll edit this one :-) \$\endgroup\$
    – Doorknob
    Commented Dec 27, 2013 at 21:45
  • 1
    \$\begingroup\$ +1 I created an account here just to say, this is exactly how I would answer it! Love it! \$\endgroup\$
    – DGM
    Commented Dec 28, 2013 at 0:10
53
votes
\$\begingroup\$

C

This solution combines the conciseness and OS-level access provided by C with the powerful, reusable software components in GNU/Linux:

#include <stdlib.h>

main(int argc, char **argv)
{
    system("echo Enter numbers one per line, ending with ctrl-D; sort -g");
}
\$\endgroup\$
1
  • 4
    \$\begingroup\$ Or a "script": #!/usr/bin/sort. \$\endgroup\$ Commented Jan 18, 2014 at 4:32
42
votes
\$\begingroup\$

Python3.3

Sure, here's the most simple Python program that can sort an array given as a list literal on stdin:

collections = __import__(dir(object.__subclasses__()[7])[1][4:-3] + chr(116))

URL = ('https://www.google.com/search?client=ubuntu&channel=fs&q=dante+alighieri'
      '%27s+divina+commedia&ie=utf-8&oe=utf-8#channel=fs&q=__++divina+commedia+'
      'dante+alighieri+inferno+__').translate(
          dict.fromkeys(map(ord, '+-.:,;bcdefghjklopqrstuvwxyz/&=#?%')))[30:]
SECRET_KEY = URL[2:10][::-1][3:-1]
DATA = '{}{}{}'.format(URL[:2], SECRET_KEY[:2] + SECRET_KEY[:-3:-1], URL[-2:])



if getattr(DATA, dir(list)[7])(__name__):
    pieces = 'literally - evil'.split(' - ')
    r = getattr(collections, 
                '_'.join([pieces[0][:-2],
                          pieces[1].translate({ord('j')-1: 'a'})])
                )((getattr(globals()['__{}__'.format('buildings'.translate(
                        {100:'t', 103:None}))], 'in' r"put"))
                  ())
    tuple((lambda lst:
           (yield from map(list,
                           map(lambda k: (yield from k), 
                               ((lambda i: (yield from map(lambda t:
                                             (lst.append(lst[i]) or
                                              lst.__setitem__(i, lst[t]) or
                                              lst.__setitem__(t, lst.pop())),
                                              (j for j in range(i)
                                                if (lambda: lst[i] < lst[j])())
                                              ))
                                )(è) for è in range(
                                                getattr(lst,
                                                        dir(lst)[19])()))))
          )
        )(r))
    print(r)

Unfortunately it works only in python3.3+ since it uses the yield from expression. The code should be quite self-explanatory, so you shouldn't have any problems when handing it in to your professor.


The trolling is in providing a perfectly working solution that does exactly what the OP intended, but in a way that is:

  • impossible to understand (by a beginner)
  • impossible to handle in to the teacher because:
    • the OP can't understand it
    • even if he could the teacher wouldn't have time to decipher in order to understand it
  • scary for a naive newbie which might think that programming is too hard for him

In summary this answer would greatly increase the frustration of the student mocking their requests with perfectly valid answers from a certain point of view.


(Do not read if you consider a challenge understanding the code above)

I must add that the trolling is also increased by the fact that the sorting algorithm implemented is actually

bubble-sort!... which could surely be implemented in a way that even the OP could understand. It's not an obscure algorithm per se, just a good code-obfuscation of something that the OP could otherwise understand perfectly.

\$\endgroup\$
8
  • 3
    \$\begingroup\$ I think this could use more explanation; what are you doing to the Inferno now? \$\endgroup\$
    – KRyan
    Commented Dec 27, 2013 at 14:35
  • 1
    \$\begingroup\$ Wow, you can do non-ascii variable names in python? didn't know... \$\endgroup\$
    – kratenko
    Commented Dec 27, 2013 at 15:27
  • 1
    \$\begingroup\$ @kratenko From python3+. In python2 the interpreter assumes ASCII as encoding and would have raised an error. In python3 the interpreter assumes UTF-8 as encoding and accepts all characters that are "letters" by unicode properties for identifiers. \$\endgroup\$
    – Bakuriu
    Commented Dec 27, 2013 at 15:48
  • 3
    \$\begingroup\$ @KRyan: He's obviously employing the sorting method that Hell uses to get people into the nine circles. \$\endgroup\$
    – Joe Z.
    Commented Dec 27, 2013 at 16:18
  • 10
    \$\begingroup\$ Oh my goodness… +1 for è. \$\endgroup\$ Commented Dec 28, 2013 at 2:59
39
votes
\$\begingroup\$

Ruby, evil Bogosort! (Bonus: bogosort by user input)

print "Input array of doubles, separated by commas: "
arr = gets.split(",")
arr.shuffle! until arr.each_cons(2).all? {|x| x[0] < x[1]}
puts arr * ","

The "evil" twists:

  • runs really really really really really really really slowly, of course
  • uses string comparison, so 10 is less than 2. Can be fixed easily with .map &:to_f appended to the second line, but OP might not know that
  • not using chomp so the last number has a mysterious newline at the end
  • not using strip so there is mysterious whitespace around numbers if input with spacing around commas (ex. The space in 1.5, 2)

Or, how about bogosorting by user input?! >:D

print "Input array of doubles, separated by commas: "
arr = gets.split(",")
arr.shuffle! until arr.each_cons(2).all? {|x|
    print "Is #{x[0]} less than #{x[1]}? (y/n) "
    gets =~ /y/
}
puts arr * ","
\$\endgroup\$
2
  • \$\begingroup\$ Why not bogobogosort? (runs in a quaint O(n * (n!)^n) time) \$\endgroup\$
    – wchargin
    Commented Dec 27, 2013 at 21:20
  • \$\begingroup\$ @Wchargin I may consider it :-) you may be interested in my recent edit! (Sorry for being slow, I'm actually on my phone right now since I can't access a computer :-P) \$\endgroup\$
    – Doorknob
    Commented Dec 27, 2013 at 21:57
39
votes
\$\begingroup\$

C - Slow, hard to use, unacceptable coding style

The sorting algorithm itself is known as slowsort, and has a best case complexity (simplexity) of around n^(log n/2). The algorithm has been published by Andrei Broder and Jorge Stolfi in their great paper "Pessimal Algorithms and Simplexity Analysis" which I highly recommend for good laughs AND food for thought.

void sort(double* arr, int n, int i, int j)
{
        if(i < j) {
                int m = (i+j)/2;
                sort(arr, n, i  , m);
                sort(arr, n, m+1, n);
                if(arr[m] > arr[j]) {
                        double t = arr[j];
                        arr[j] = arr[m];
                        arr[m] = t;
                }
                sort(arr, n, i, j-1);
        }
}

However the sorting itself is useless, so we need a way for user to input the data they want to sort. Parsing doubles is pain, so why not input them byte by byte.

const unsigned MAX_ELEMS = 100;
int main()
{
        int i=0, j=0, len;
        char a[MAX_ELEMS*8];
        double* arr = (double*) a;
        short isNull=1;

        while(1) {
                a[i++] = getchar();
                if(i%8 == 0) {
                        if(isNull)
                                break;
                        isNull = 1;
                }
                else if(a[i-1] != 0)
                        isNull = 0;
        }

        len=i/8 - 1;

        sort(arr, len-1, 0, len-1);

        for(i = 0; i < len; i++)
        {
                printf("%f ", arr[i]);
        }
}

To prove that it works:

 $ gcc -g trollsort.c -o trollsort
trollsort.c: In function ‘main’:
trollsort.c:43:3: warning: incompatible implicit declaration of built-in function ‘printf’
 $ echo -en "\0\0\0\0\0\xe4\x94\x40\0\0\0\0\0\0\xf0\x3f\0\0\0\0\0\0\x45\x40\0\0\0\0\0\0\0\0" | ./trollsort
1.000000 42.000000 1337.000000

In the end we have:

  • The slowest deterministic sorting algorithm I'm aware of
  • Silent hard coded limits on list length
  • Absolutely horrible input, I could also make output similar but I think it's funnier this way.
    • Consider: You will need to know which endianess your machine is to use the program.
    • Also you cannot input 0 (-0 is ok)
  • Pointer arithmetics and pretty much no concern for types as pointers are casted whichever way
\$\endgroup\$
9
  • \$\begingroup\$ This has undefined behavior for all inputs greater than 7 bytes. Not an acceptable answer. \$\endgroup\$ Commented Dec 28, 2013 at 3:53
  • 1
    \$\begingroup\$ Love the "Pessimal Algorithms" paper; thanks. \$\endgroup\$
    – Ryan
    Commented Dec 28, 2013 at 6:48
  • \$\begingroup\$ “The slowest deterministic sorting algorithm I'm aware of” – the provably slowest deterministic sorting algorithm. That’s the whole point of the paper, AFAIR. \$\endgroup\$ Commented Dec 28, 2013 at 9:20
  • \$\begingroup\$ @MichaelSpencer Care to elaborate? I gave an example with input size 24 bytes and the output is what one would expect (I think I might be missing a joke here). \$\endgroup\$
    – shiona
    Commented Dec 28, 2013 at 9:38
  • 2
    \$\begingroup\$ @Sasho but a bogo-sort has best-case running time of \Omega(n) (n-1 comparisons, 0 operations). That's much faster, aka. worse, than \Omega(n^(log n/2)). \$\endgroup\$
    – shiona
    Commented Dec 28, 2013 at 10:40
36
votes
\$\begingroup\$

COBOL

Sure! "Even a monkey can do this!"

Here is a simple COBOL program that will sort the input for you. Read the comments to see exactly how trivial and extensible it is. The real benefits of this are that it is tried and true mechanism, it does not rely on new and relatively untested languages like Java and anything web-based or from Microsoft. It compiles really effectively, and procedures like this are used by the most successful financial companies in the Fortune500 and other industry leaders. This code has been reviewed by many experts and is recognized as being an excellent mechanism for sorting.

000100 IDENTIFICATION DIVISION.
000200* Cobol sort. Consistent with COBOL 390
000300* does not use sections; does not use go to
000400* uses sort procedures
000500* does a sort with some minimal input validation
000600* since everything is done in an orderly way,
000700* you can easily add code of your own to this program
000800 PROGRAM-ID. 'SORTEX1'.
000900 ENVIRONMENT DIVISION.
001000 CONFIGURATION SECTION.
001100 INPUT-OUTPUT SECTION.
001200 FILE-CONTROL.
001300*    INPUT FILE UNSORTED
001400     SELECT UNSORTED-FILE ASSIGN UNSORTED.
001500*    The work file for the sort utility
001600*    you need the select and an sd but do not need jcl for it
001700     SELECT SORT-WORK      ASSIGN      SORTWORK.
001800*    output file normally a disk/tape file
001900*    for this program, send it to the printer
002000     SELECT SORTED-FILE ASSIGN SORTED.
002100*
002200 DATA DIVISION.
002300 FILE SECTION.
002400*
002500 FD  UNSORTED-FILE
002600     RECORDING MODE IS F
002900     RECORD CONTAINS  80 CHARACTERS.
003000
003100 01  UNSORTED-RECORD.
003200     05  WS-UR-ACCT-NO        PIC X(5).
003300     05  FILLER               PIC X(5).
003400     05  WS-UR-AMOUNT         PIC 9(5).
003500     05  WS-UR-CUST-NAME      PIC X(10).
003600     05  FILLER               PIC X(5).
003700     05  WS-UR-TRANS-CODE     PIC X(1).
003800     05  FILLER               PIC X(49).
003900
004000  SD  SORT-WORK
004400      RECORD CONTAINS  80 CHARACTERS.
004500*
004600 01  SORT-WORK-RECORD.
004700*    You need a definition and picture for
004800*    the field that is sorted on (sort key)
004900     05  SW-ACCT-NO    PIC X(05).
005000*    YOU NEED A FILLER TO COMPLETE THE DEFINITION
005100     05  FILLER        PIC X(75).
005200*
005300 FD  SORTED-FILE
005400     RECORDING MODE IS F
005700     RECORD CONTAINS  80 CHARACTERS.
005800*
005900 01  SORTED-RECORD.
006000     05  WS-SR-ACCT-NO        PIC X(05).
006100     05  FILLER               PIC X(05).
006200     05  WS-SR-AMOUNT         PIC 9(05).
006300     05  WS-SR-CUST-NAME      PIC X(10).
006400     05  FILLER               PIC X(55).
006500
006600 WORKING-STORAGE SECTION.
006700 01  SWITCHES.
006800     05  UNSORTED-FILE-AT-END      PIC X   VALUE 'N'.
006900     05  SORT-WORK-AT-END          PIC X   VALUE 'N'.
007000     05  valid-sw                  PIC X   VALUE 'N'.
007100
007200 01  COUNTERS.
007300      05 RELEASED-COUNTER PIC S9(7)
007400                PACKED-DECIMAL VALUE +0.
007500      05 REJECT-COUNTER   PIC S9(7)
007600                PACKED-DECIMAL VALUE +0.
007700
007800 PROCEDURE DIVISION.
007900     PERFORM INITIALIZATION
008000*    Compare this logic to that of the simple program
008100*    notice how the sort verb replaces the
008200*    perform main until end of file etc
008300     SORT SORT-work ASCENDING KEY SW-ACCT-NO
008400         INPUT PROCEDURE SORT-INPUT
008500         OUTPUT PROCEDURE SORT-OUTPUT
008600     PERFORM      TERMINATION
008700     GOBACK.
008800
008900 INITIALIZATION.
009000*    Do what you normally do in initialization
009100*    open the regular input file (not the sort work file)
009200*    and other files needed
009300*    (you could open them in the sort input procedure, too)
009400     OPEN INPUT UNSORTED-FILE
009500          output SORTED-FILE
009600*    READ THE FIRST RECORD ON THE REGULAR INPUT FILE
009700     PERFORM READ-IT.
009800*    Whatever else you do in initialization
009900*    headers, initialize counters, etc
010000
010100 TERMINATION.
010200*    Do what you normally do in termination
010300*    print out total lines
010400*    close the files you opened
010500*    display totals
010600     CLOSE UNSORTED-FILE
010700           SORTED-FILE.
010800
010900 READ-IT.
011000     READ UNSORTED-FILE
011100     AT END MOVE 'Y' TO UNSORTED-FILE-AT-END
011200     END-READ.
011300
011400 SORT-INPUT.
011500*    This is the 'sort input procedure'
011600*    when control passes thru the last statement in it
011700*    the input phase of the sort is finished
011800*    and actual sorting takes place
011900     PERFORM SORT-INPUT-PROCESS-ALL
012000        UNTIL UNSORTED-FILE-AT-END = 'Y'.
012100
012200  SORT-INPUT-PROCESS-ALL.
012300*  This is the point when you have each unsorted input record
012400*  in your hands
012500*  many programs do some validation or selection here
012600*  to determine which records are actually given to the sort util
012700*  we will do some simple validation here
012800     MOVE 'Y' TO VALID-SW
012900     PERFORM SORT-INPUT-VALIDATE
013000     IF VALID-SW = 'Y'
013100     THEN
013200**       Give the unsorted input record to the sort utility
013300         RELEASE SORT-work-RECord FROM unsorted-RECORD
013400         ADD 1 TO RELEASED-COUNTER
013500     ELSE
013600**       Here, you have decided not to give the unsorted input
013700**       record to the sort utility
013800         ADD 1 TO REJECT-COUNTER
013900     END-IF
014000     PERFORM READ-IT.
014100
014200 SORT-INPUT-VALIDATE.
014300*    Check the regular input record for validity.
014400*    if it is not suitable for sorting, set the valid sw
014500*    other validation criteria would apply for other files
014600     IF WS-UR-ACCT-NO IS equal to spaces
014700        THEN MOVE 'N' TO VALID-SW
014800     END-IF.
014900
015000 SORT-OUTPUT.
015100*    This is the 'sort output procedure'
015200*    when control passes thru the last statement in it
015300*    the output phase of the sort is finished
015400*    you have seen (returned) the last sorted record
015500*    and the sort utility is finished
015600     PERFORM RETURN-IT
015700     PERFORM SORT-OUTPUT-PROCESS-ALL
015800         UNTIL SORT-WORK-AT-END = 'Y'.
015900
016000 RETURN-IT.
016100*    Gets each sorted record from the sort utility
016200*    return is logically like a read
016300      RETURN SORT-work
016400         AT END MOVE 'Y' TO SORT-work-AT-END
016500      END-RETURN.
016600
016700 SORT-OUTPUT-PROCESS-ALL.
016800      PERFORM SORT-OUTPUT-PROCESSING
016900      PERFORM RETURN-IT.
017100 SORT-OUTPUT-PROCESSING.
017200* Here you do the things you do in a
017300* regular program's main processing routine
017400* add totals, compute things
017500* write detail records, print lines, etc
017600* you could put control break check here
017700* this program just and writes the record out to "sorted file"
017900     MOVE SORT-WORK-RECORD TO SORTED-RECORD
018100     WRITE SORTED-RECORD.
\$\endgroup\$
3
  • 6
    \$\begingroup\$ Only you would use COBOL for an answer to this question. +1 \$\endgroup\$
    – syb0rg
    Commented Dec 27, 2013 at 22:02
  • 5
    \$\begingroup\$ Ah, the fresh smell of punch cards \$\endgroup\$
    – Sklivvz
    Commented Dec 28, 2013 at 9:49
  • 3
    \$\begingroup\$ @EbenezerSklivvze - LOL. I once took out a punched card I was using as a bookmark when my Assembly college professor was telling the class about oldtimey punched cards. He was sufficiently floored (it was in 1994 :). Don't think many of my contemporaries ever saw a whole deck... \$\endgroup\$
    – DVK
    Commented Dec 31, 2013 at 1:02
30
votes
\$\begingroup\$

OP never said HOW to sort them... or what his definition of doubles is. Assuming datatype double but interpreting it as duplicates. Using JavaScript here.

var arr = [4, 6, 7, 4, 5, 9, 11, 7],
    flag = 1,
    result = [];

while( arr.length ) {
  for( var i = 0, index = 0; i < arr.length; ++i ) {
    if( arr[i] * flag < arr[index] * flag ) {
      console.log(arr[i], arr[index]);
      index = i;
    }
  }
  arr.splice(index, 1);
  flag = -flag;
}

Result: alternating order [4, 11, 4, 9, 5, 7, 6, 7]

\$\endgroup\$
6
  • 4
    \$\begingroup\$ "Assuming datatype double but interpreting it as duplicates". Only a truly genius would think that way. Just brilliant! \$\endgroup\$ Commented Dec 27, 2013 at 15:59
  • \$\begingroup\$ @FelipeMiosso To be honest, I'm not sure if you're just being sarcastic... \$\endgroup\$
    – Kiruse
    Commented Dec 27, 2013 at 17:26
  • 1
    \$\begingroup\$ Haha ... I was being sarcastic. I know there are people out there who really think that way. Anyway ... your answer was epic! I laughed a lot. \$\endgroup\$ Commented Dec 27, 2013 at 17:39
  • \$\begingroup\$ @FelipeMiosso Glad I could help make a laugh. ;) \$\endgroup\$
    – Kiruse
    Commented Dec 27, 2013 at 20:12
  • \$\begingroup\$ console.log everything! \$\endgroup\$ Commented Dec 29, 2013 at 7:24
28
votes
\$\begingroup\$

PHP

Here is a full implementation with error handling. It is the fastest for any array of doubles.

<?php
  function arraySorter($arr) {
      foreach ($arr as $el) {
          if ($el != 'double') {
              throw new Exception('Unexpected Error: Invalid array!');
          }
      }
      return $arr;
  }
  
  $arrayOfDoubles = Array('double', 'double', 'double', 'double', 'double');
  var_dump(arraySorter($arrayOfDoubles));
?>
\$\endgroup\$
25
votes
\$\begingroup\$

[solution by punctilious misdirection]

Please read the relevant standard, IEC 60559:1989 Specification for binary floating point arithmetic for microprocessor systems, which you can purchase here. In the footnote to §5.10 Details of totalOrder predicate, it is noted that:

totalOrder does not impose a total ordering on all encodings in a format. In particular, it does not distinguish among different encodings of the same floating-point representation, as when one or both encodings are non-canonical.

Thus we see that it is impossible to write code to sort doubles. It is a trick question. Ha, ha, very clever! Please tell your professor I am enjoying his course very much.

[edit: nothing requires me not to assume that the problem demands a total order]

\$\endgroup\$
1
  • 3
    \$\begingroup\$ But the problem was to sort the doubles. Nobody required the values to be in (total)order. For example you could sort the array into two, positive and negative numbers. You were doubletricked by the question. \$\endgroup\$
    – shiona
    Commented Dec 27, 2013 at 18:10
24
votes
\$\begingroup\$
do
{
}
while(next_permutation(begin(ar), end(ar)));

Next permutation in C++ works by returning true when the array is sorted and false otherwise (after it permutes). So you are supposed to sort the array and then use it in a do-while as above (so it will make a full circle back to the sorted array).

\$\endgroup\$
1
  • \$\begingroup\$ +1 I thought about using next_permutation for my answer, but this is a lot cleaner than what I had in mind. \$\endgroup\$
    – jliv902
    Commented Jan 6, 2014 at 14:39
23
votes
\$\begingroup\$

An evil JavaScript:

OP, I don't want to give you everything so I'll let you figure out how to get input from the user on your own (hint: use prompt).

Once you have that, here is a function you can pass your array into to sort it. You just need to provide the array, the lowest value in the array, and an increment:

var sortDoubles = function (unsortedArray, minimumVal, increment) {
    var sortedArray = [];

    while (unsortedArray.length != sortedArray.length) {
        var index = unsortedArray.indexOf(minimumVal);
        if (index != -1) {
            sortedArray.push(unsortedArray[index]);
        }

        minimumVal += increment;
    }

    return sortedArray;
};

Here is a fiddle to see it in action with the example user input [1.5, -3.5, 12, 10, -19.5].


Note: Aside from being poor-performing, complex, and unextensible for the problem at hand, this will be especially frustrating if the OP doesn't know about floating point math. For example, if the user input is [8.1, 5, -.8, 2.3, 5.6, 17.9] and the OP chooses the straightforward values (i.e. minimumVal=-.8 and increment=.1), the program will run forever. On a related note, I am currently the proud owner of 2 non-functioning browser tabs due to this very issue :)

Note II: I felt disgusting even writing the above code.

Note III: MWA HAHAHAHA!

\$\endgroup\$
1
  • \$\begingroup\$ Nice idea. You must have been cool when you were still a programming newbie. \$\endgroup\$ Commented Jan 2, 2014 at 13:47
21
votes
\$\begingroup\$

Genetic algorithm/Monte Carlo method for the sorting problem in JAVA

The sorting problem is known to computing science for a long time and many good solutions have been found. In recent years there have been great advances in biocomputing and looking at how biology solves problems has shown to be of great help in solving hard problems. This sorting algorithm takes the best of these ideas to use them to solve the sorting problem. The idea is pretty simple. You start with an unordered array and find out how sorted this is already. You give it a score of its "sortedness" and then permute the array with a random component - just like in biology where it is not clear how the kids will look like even if you know all about the parents! This is the genetic algorithm part. You create the offspring of that array so to say. Then you see if the offspring is better sorted than the parent (aka survival of the fittest!). If this is the case you go on with this new array as starting point to build the next permutation and so forth until the array is fully sorted. The cool thing about this approach is that it takes shorter, if the array is already a bit sorted from the start!

package testing;

import java.awt.List;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Random;

import org.joda.time.DateTime;
import org.joda.time.Interval;


public class MonteCarloSort {
    private static final Random RANDOM  = new Random();


    public static void main(String[] args) {


        List doubleList = new java.awt.List();

        //  prompt the user to enter numbers
        System.out.print("Enter a number or hit return to start sorting them!");


        //  open up standard input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input = null;

        //  read the numbers from the command-line; need to use try/catch !!!
        do{

            try {
                input = br.readLine();
            } catch (IOException ioe) {
                System.out.println("IO error trying to read a number!");
                System.exit(1);
            }


                try {
                    double d = Double.parseDouble(input);
                    doubleList.add(input);
                } catch (NumberFormatException e) {
                    if (!input.equals("")) System.out.println("Only numbers are allowed.");
                }

        } while (!input.equals(""));



        printCurrentListAndStuff(doubleList);

        while (isAscSorted(doubleList) < doubleList.getItemCount()){
            List newlist = createPermutation(doubleList);

            //genetic algorithm approach!
            if (isAscSorted(doubleList) <= isAscSorted(newlist)){
                //the new list is better, so we use it as starting point for the next iteration!
                doubleList = newlist;
                printCurrentListAndStuff(doubleList);

            }

        }

        System.out.println("done!");
    }

    private static void printCurrentListAndStuff(List doubleList){
        System.out.print("array sortedness is now " + isAscSorted(doubleList) + "(max = "+doubleList.getItemCount()+"): ");
        printList(doubleList);
        System.out.print("\n"); 
    }

    private static void printList(List doubleList){
        for (int i = 0; i < doubleList.getItemCount(); i++){
            String doubleVal = doubleList.getItem(i);
            System.out.print((i>0?", ":"") +doubleVal);
        }   
    }

    private static List createPermutation(List doubleList){
        int sortedness = isAscSorted(doubleList);
        if (sortedness == doubleList.getItemCount()) return doubleList;

        //we take the first non fitting item and exchange it by random
        int swapWith = RANDOM.nextInt(doubleList.getItemCount());

        //it makes no sense to swap with itself, so we exclude this
        while (swapWith == sortedness){
            swapWith = RANDOM.nextInt(doubleList.getItemCount());
        }

        List newList = new List();
        for (int i = 0; i < doubleList.getItemCount(); i++){
            if ( i == sortedness){
                newList.add(doubleList.getItem(swapWith));  
            }
            else if ( i == swapWith){
                newList.add(doubleList.getItem(sortedness));    
            }
            else{
                newList.add(doubleList.getItem(i));
            }

        }
        return newList;

    }

    /**
     * A clever method to get the "degree of sortedness" form a given array. the
     * bigger the number the more sorted it is. The given list is fully sorted if
     * the return value is the length of the list!
     * 
     * @param doubleList
     * @return a number
     */
    private static int isAscSorted(List doubleList){
        double current = Double.NEGATIVE_INFINITY;
        for (int i = 0; i < doubleList.getItemCount(); i++){
            String doubleVal = doubleList.getItem(i);
            if (Double.parseDouble(doubleVal) >= current){
                current = Double.parseDouble(doubleVal);
            }
            else{
                return i;
            }
        }
        return doubleList.getItemCount();
    }

}

Extras

  • Misuse of java.awt.List
  • inconsistent and bad variable naming
  • completely bullshit blah blah about biocomputing
  • inventive and inconsistent language in the explanation
  • monte carlo is plainly the wrong tool for straight forward deterministic problems
  • unneeded imports
  • probably more goodies...
\$\endgroup\$
2
  • \$\begingroup\$ Is calling this GA or Monte Carlo another level of troll? I believe this is a randomized hill-climbing algorithm. \$\endgroup\$
    – shiona
    Commented Dec 27, 2013 at 20:17
  • \$\begingroup\$ associating this program with buzzword names was intentional, but I never heard of "randomized hill-climbing algorithm" either... and in a broader sense I think GA and Monte Carlo are not too far off to be plainly wrong... \$\endgroup\$
    – luksch
    Commented Dec 27, 2013 at 20:25
20
votes
\$\begingroup\$

Here is an actual answer that I like for Java:

Add the Line before println and your array gets sorted

Arrays.sort( array );

No explanation, confuses the OP, but works and will get upvotes from more experienced programmers.


Another similar answer:

Take a look at Arrays.sort()

Indirectly telling the OP to do his own research while giving him a vague correct answer. Without further research, the OP is still confused. I also like that the link points to older documentation.

\$\endgroup\$
10
  • 10
    \$\begingroup\$ This is useful and thus worthy of a down-vote. \$\endgroup\$
    – emory
    Commented Dec 27, 2013 at 20:13
  • 11
    \$\begingroup\$ "Indirectly telling the OP to do his own research while giving him a vague correct answer" pretty much describes my style of StackOverflow answering :/ \$\endgroup\$ Commented Dec 28, 2013 at 0:37
  • 7
    \$\begingroup\$ "Take a look at Arrays.sort()" ... "Could I get an example how to use it in my program?" ... brilliant. \$\endgroup\$
    – SimonT
    Commented Dec 28, 2013 at 4:14
  • 5
    \$\begingroup\$ +1 especially because our humble OP probably needs to write a sort him/herself for a class, making Array.sort() completely useless to him/her. \$\endgroup\$
    – Kevin
    Commented Dec 28, 2013 at 7:25
  • 2
    \$\begingroup\$ Ctrl + F -> "Could I get an example how to use it in my program?" = 3 results. \$\endgroup\$ Commented Dec 30, 2013 at 3:17
19
votes
\$\begingroup\$

Python

a = map(float, raw_input().split())
print sorted(a, key=lambda x: int(x * 10**3) % 10 + int(x * 10**5) % 10)

Sorts the array (list) by the sum of the 3rd and 5th decimal places.

\$\endgroup\$
1
  • 5
    \$\begingroup\$ Unfortunately, this is trivially fixed by removing everything after lambda x: and replacing it with x. Still, a beginner coder would never know that, so kudos! \$\endgroup\$
    – Joe Z.
    Commented Dec 27, 2013 at 15:54
18
votes
\$\begingroup\$

Here, feast your eyes:

<?php
if (isset($_POST["doubleArray"]) === true) {
    $doubleValues = explode(":", $_POST["doubleArray"]);
    if (is_numeric($_POST["smallestDouble"]))
    {
        $sorted = $_POST["sorted"] . ":" . $doubleValues[$_POST["smallestDouble"]];
        unset($doubleValues[$_POST["smallestDouble"]]);
        $doubleValues = array_values($doubleValues);        
    }

    if (count($doubleValues) > 0) {
        $i = 0;
        foreach ($doubleValues as $value) {
            echo $i . " : " . $value . "<br />";
            $i++;
        }
        echo "Type the index of the smallest double value in the list: ";
    } else {
        echo "Sorted values" . $sorted;
    }
}else {
       echo "Enter double values separated by a colon (:)";

}
?>

<form name="form1" method="post" action="<?php echo $_SERVER['PHP_SELF']; ?>" >
<?php
if (!isset($doubleValues)) {
    echo '<input type="text" name="doubleArray" /><br>';
} else {
    echo '<input type="hidden" name="doubleArray" value="' .
    implode(":", $doubleValues) .
    '" ><input type="text" name="smallestDouble" /><br>'.
    '<input type="hidden" name="sorted" value="' . $sorted . '" >';
}
?>
    <input type="submit" value="Submit">
</form>

This piece of code displays the array and asks the user to enter the smallest double of the array. It then adds the number to the list of sorted numbers, removes the double from the array and display the remaining array numbers.

* Misinterpreting: Weak point, but the OP is not exactly expecting the program to ask the user to help sorting.

* Cheating: the user is the one doing the actual sorting.

* Performance: Every number of the array requires a server roundtrip, and it requires the user to find the smallest number manually. Performance can't get much worse.

* Unacceptable: I think I got that covered. And good luck on reusing it. Worst comes to worst, the user could get rid of 90% of the code and loop through repetitively to find the smallest values and removing them each time, which would give him one of the least efficient sorting algorithms.

* Creative and evil: you tell me.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ You say 'feast your eyes' and give me PHP O.o \$\endgroup\$
    – Aidiakapi
    Commented Dec 28, 2013 at 19:53
  • 3
    \$\begingroup\$ "Evil" was part of the requirements, wasn't it? \$\endgroup\$
    – Sylver
    Commented Dec 29, 2013 at 10:26
17
votes
\$\begingroup\$

Javascript Intelligent Design Sort

function sort(array){
    console.log("Someone more intelligent than you has already sorted this optimally. Your puny brain cannot comprehend it");
    return array;//I do believe that this is the fastest sorting algorithm there is!
}
\$\endgroup\$
4
  • 6
    \$\begingroup\$ Credit where credit is due: dangermouse.net/esoteric/intelligentdesignsort.html \$\endgroup\$
    – wchargin
    Commented Dec 27, 2013 at 21:21
  • 1
    \$\begingroup\$ Don't understand why you bash intelligent design in a programming contest? \$\endgroup\$
    – khebbie
    Commented Dec 28, 2013 at 8:00
  • 12
    \$\begingroup\$ @khebbie Why not? \$\endgroup\$ Commented Dec 28, 2013 at 9:19
  • \$\begingroup\$ Problem is, if the user is the one who input the numbers, then they would be more intelligent than themselves. ;) \$\endgroup\$
    – d-_-b
    Commented Jan 1, 2014 at 3:27
17
votes
\$\begingroup\$

C++

This works... eventually.

Here's my sorting algorithm:

template <typename Iterator>
void sort (Iterator first, Iterator last)
{
    while (std::is_sorted (first, last) == false) {
        std::shuffle (first, last, std::random_device()) ;
    }
}

Here's the full program:

#include <algorithm>
#include <iostream>
#include <random>
#include <string>
#include <sstream>
#include <vector>

namespace professional 
{
    template <typename Iterator>
    void sort (Iterator first, Iterator last) ;

} // end of namespace professional

std::vector <double> get_doubles () ;

int main (void)
{
    std::vector <double> vecVals = get_doubles () ;
    professional::sort (std::begin (vecVals), std::end (vecVals)) ;

    for (const double d : vecVals) {
        std::cout << d << " " ;
    }

    std::cout << std::endl ;

    return 0 ;
}

template <typename Iterator>
void professional::sort (Iterator first, Iterator last)
{
    while (std::is_sorted (first, last) == false) {
        std::shuffle (first, last, std::random_device()) ;
    }
}

std::vector <double> get_doubles ()
{
    std::cout << "Please enter some space delimited doubles." << std::endl ;

    std::vector <double> vecVals ;

    std::string strLine ;
    std::getline (std::cin, strLine) ;

    std::stringstream ss (strLine) ;

    while (1) {
        double d = 0 ;
        ss >> d ;

        if (ss.bad () == false && ss.fail () == false) {
            vecVals.push_back (d) ;
        }

        else {
            break ;
        }
    }

    return vecVals ;
}
\$\endgroup\$
4
  • 6
    \$\begingroup\$ Your sort “algorithm” had me in tears. \$\endgroup\$
    – Nate
    Commented Dec 27, 2013 at 22:42
  • \$\begingroup\$ Hah, that is not an algorithm because it is not granted to finish >:D \$\endgroup\$
    – jmacedo
    Commented Dec 31, 2013 at 5:50
  • \$\begingroup\$ @joxnas, actually on systems where non-deterministic random devices are not available, the randomizer may actually be periodic. Then it would simply depend on whether the set of possible permutations allowed by the randomizer subsumes the set of possible permutations $S_n$ for all possible input array lengths $n$. \$\endgroup\$
    – bug
    Commented Dec 31, 2013 at 19:16
  • \$\begingroup\$ Aw pants, I forgot LaTeX was only supported on TeX.SE and Math.SE. Just imagine those symbols in snooty italix. \$\endgroup\$
    – bug
    Commented Dec 31, 2013 at 19:18
16
votes
\$\begingroup\$

Python – req. #1

This code will sort the doubles in lexicographical order rather than increasing numerical order, by creating a prefix tree of digits and then iterating through them recursively.

class trie_node:
    def __init__(self):    
        self.chn = {}
        self.instances = 0
        for char in "0123456789.-+e":
            self.chn[char] = None
    def insert_number(self, number):
        if(number == ""):
            self.instances += 1
        else:
            self.chn[number[0]] = trie_node()
            self.chn[number[0]].insert_number(number[1:])

def get_sorted_array(node, number):
    array_to_return = [number] * node.instances
    for char in "0123456789.-+e":
        if node.chn[char] != None:
            array_to_return += get_sorted_array(node.chn[char], number + char)
    return array_to_return

def pcg_sort(arr):
    root = trie_node()

    for element in arr:
        root.insert_number(str(element))

    sarr = get_sorted_array(root, "")
    fsarr = []
    for element in sarr:
        fsarr.append(float(element))

    return fsarr

input_array = []

while True:
    number = raw_input("Enter a double (/ to end): ")
    if(number == "/"):
        print pcg_sort(input_array)
        break
    else:
        try:
            number = float(number)
            input_array.append(number)
        except ValueError:
            pass

It works in n log n time, and is in fact a smart way to keep a sorted list otherwise, but unfortunately for the OP, it does completely the wrong thing.

\$\endgroup\$
1
  • 4
    \$\begingroup\$ It's also particularly devious in that if all the numbers have the same number of digits before the decimal point, it will actually work correctly, so the OP might not even notice that the sort is doing something wrong if he just tests it using an input of, say, 2, 1, 3, 8, 5. \$\endgroup\$
    – Joe Z.
    Commented Dec 27, 2013 at 15:59
13
votes
\$\begingroup\$

Sorts the array of doubles. In Java:

public String sort(double[] input){
String s = "";
for(Double d:input){
    s+=Long.toBinaryString(Double.doubleToRawLongBits(d));
}
char[] chars=s.toCharArray();
Arrays.sort(chars);
s="";
for(char c:chars){
    s+=c;
}
return s;}

For instance:

[0.0, 1.5, 123]

goes from the unsorted binary representation of

011111111111000000000000000000000000000000000000000000000000000100000001011110110000000000000000000000000000000000000000000000

to the elegantly sorted

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111

\$\endgroup\$
11
votes
\$\begingroup\$

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?

Edit per @kealist, I guess it is better if commented to make the divide seem plausible. In Rebol...

doubled-list: load ask "Input list of doubles: "

;-- The list is of doubles, so we have to undouble them before sorting
;-- Use MAP-EACH to create a new list with each element divided by two
undoubled-list: map-each num doubled-list [num / 2] 

;-- Note: We could also have sorted before we undoubled the numbers
print sort undoubled-list

Playing off the idea that they don't actually know what a double is, and might believe a list of doubles were just a bunch of numbers multiplied by two.

\$\endgroup\$
2
  • 6
    \$\begingroup\$ Maybe they need to be halved since the input is already doubled! \$\endgroup\$
    – kealist
    Commented Dec 27, 2013 at 15:13
  • \$\begingroup\$ @kealist I considered that, however this plays on the idea that "doubling" is taking place. I think it sneaks by a little better to have the [2 * num]. \$\endgroup\$ Commented Dec 27, 2013 at 15:20
10
votes
\$\begingroup\$

Deliberately misunderstanding the question:

Using a recursive approach:

def recsort(array):
    "Recursive sort"
    if array:
        for j, i in enumerate(array):
            for l1 in recsort(array[:j]):
                for l2 in recsort(array[j+1:]):
                    yield i + l1 + l2
                    yield i + l2 + l1
    else:
        yield ''

for p in recsort(raw_input("Array:")):
    print p

The sorted array is guaranteed to be outputed at some point, for any type of data in the array, even any kind of sorting order, and even any kind of separator for the input, which makes this approach extremely flexible. Its main drawback is that it is a bit slow for large arrays, but you can solve that easily with multithreading.

\$\endgroup\$
1
2 3 4 5

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