1185: "Ineffective Sorts"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

User avatar
jc
Posts: 356
Joined: Fri May 04, 2007 5:48 pm UTC
Location: Waltham, Massachusetts, USA, Earth, Solar System, Milky Way Galaxy
Contact:

Re: 1185: "Ineffective Sorts"

Postby jc » Wed Mar 13, 2013 6:30 pm UTC

Gargravarr wrote:
jc wrote:Some years back, perhaps in the 1980s, there was a competition for the "worst" sort algorithm. ...

Please let us know if you remember the winner.
The worst one I've ever used in production code is BubbleSort. Because the boss liked it for some obcure reason.

Maybe I'll try to find it.

I've had a few situations where BubbleSort was actually the fastest of the sorts we tested. The explanation is that sorts are conventionally judged solely on their speed at sorting randomly-ordered data. But in the real world, some kinds of data start out with some internal order. If that's close to the desired order, bubbling a list can be a very fast way of sorting it.

One common example is data being collected from a lot of other sites, with varying transit times to the central data site. If you want them sorted by send time, they're almost in that order, with few items out of place by more than a few slots. If you have millions of items, QuickSort can be horribly slow, while BubbleSort will quickly in O(N) time undo the jitter caused by network transit time. Your main problem then is keeping all the senders' clocks in sync ...

In the Real World (TM), it's often foolish to look for the best sort routine. Rather, you need a collection of sort routines, plus testing to discover which (if any) is best for your actual data sets. Sometimes you're surprised when a "bad" sort algorithm turns out to be consistently the fastest for one of your sources of data. This is generally because the data had a certain amount of order, and one sort algorithm happened to take advantage of the order that existed. But the documentation rarely tells you what kinds of data it sorts the fastest.

I've also seen teams go through long, rancorous discussions of the best sort algorithm for their data, when it turns out their lists are typically under 100 items, and all the routines finish so fast that their clock can't even measure the differences.

dp2
Posts: 346
Joined: Wed Aug 18, 2010 3:06 pm UTC

Re: 1185: "Ineffective Sorts"

Postby dp2 » Wed Mar 13, 2013 6:34 pm UTC

EverVigilant wrote:I don't get the halfhearted mergesort one. I mean, he's forgetting to include the pivot (unless it's implicitly included in either PIVOT: or :PIVOT but not both; I am not familiar with that syntax). Is that it?

It takes a list, splits it in half, does the same thing recursively to each half, then returns a list of the two results.
[6,3,4,6,8,1]
becomes
[[[6], [[3], [4]]], [[6], [[8], [1]]]]

User avatar
super_aardvark
Posts: 54
Joined: Tue Jan 22, 2008 9:26 am UTC

Re: 1185: "Ineffective Sorts"

Postby super_aardvark » Wed Mar 13, 2013 6:47 pm UTC

Ehsanit wrote:I wonder for what kind of list length Panic Sort would actually return the correct list.
It's basically a bogosort, but it "cuts" instead of "shuffles" the deck at each iteration. I imagine that the average case running time would still be n!, so it should handle 7 elements correctly more often than it goes psycho.


Nope. Average case is more like O(∞). For a list of length 3, it will sort it very quickly half the time, and it will never, ever succeed the other half the time.

Take a deck of cards. Look at the top two, and put them back; note their order. For your first cut, put the top card on the bottom of the deck. Now find a way to cut the deck a second time such that those two cards are not adjacent in the same order as before.

User avatar
mrputter
Posts: 24
Joined: Thu Mar 29, 2007 6:52 am UTC
Location: Calgary, AB, Canada
Contact:

Re: 1185: "Ineffective Sorts"

Postby mrputter » Wed Mar 13, 2013 7:16 pm UTC

Gargravarr wrote:
jc wrote:Some years back, perhaps in the 1980s, there was a competition for the "worst" sort algorithm. They were careful to state that 1) the sort had to actually work, 2) speed was measured only by operation count, and 3) "irrelevant" time wasting or sabotage instructions weren't allowed (since we all know how to write a cpu-eating busy loop). I.e., everything in the code had to contribute to improving the sort order. Some of the algorithms were truly incredible, and really, really slow. I wonder if there's an archive of this lying about somewhere ...

Please let us know if you remember the winner.


I think this is a case for the AckermannSort!

(Please let me know if you find an implementation. (On second thought, please don't.))

Appity
Posts: 6
Joined: Wed May 21, 2008 4:33 am UTC

Re: 1185: "Ineffective Sorts"

Postby Appity » Wed Mar 13, 2013 7:45 pm UTC

There is also the infamous Sleep Sort, discovered by a user on 4chan's programming text board: http://dis.4chan.org/read/prog/1295544154

Man, am I a genius. Check out this sorting algorithm I just invented.


Code: Select all

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait


example usage:

Code: Select all

./sleepsort.bash 5 3 6 3 6 3 1 4 7

mtavs
Posts: 18
Joined: Wed Feb 22, 2012 5:02 am UTC

Re: 1185: "Ineffective Sorts"

Postby mtavs » Wed Mar 13, 2013 8:01 pm UTC

Seems like an ineffective sort of way to do things...

Gargravarr
Posts: 74
Joined: Mon Dec 21, 2009 8:34 am UTC

Re: 1185: "Ineffective Sorts"

Postby Gargravarr » Wed Mar 13, 2013 8:06 pm UTC

jc wrote:
Gargravarr wrote:
jc wrote:Some years back, perhaps in the 1980s, there was a competition for the "worst" sort algorithm. ...

Please let us know if you remember the winner.
The worst one I've ever used in production code is BubbleSort. Because the boss liked it for some obcure reason.

Maybe I'll try to find it.

I've had a few situations where BubbleSort was actually the fastest of the sorts we tested. The explanation is that sorts are conventionally judged solely on their speed at sorting randomly-ordered data. But in the real world, some kinds of data start out with some internal order. If that's close to the desired order, bubbling a list can be a very fast way of sorting it.

One common example is data being collected from a lot of other sites, with varying transit times to the central data site. If you want them sorted by send time, they're almost in that order, with few items out of place by more than a few slots. If you have millions of items, QuickSort can be horribly slow, while BubbleSort will quickly in O(N) time undo the jitter caused by network transit time. Your main problem then is keeping all the senders' clocks in sync ...

In the Real World (TM), it's often foolish to look for the best sort routine. Rather, you need a collection of sort routines, plus testing to discover which (if any) is best for your actual data sets. Sometimes you're surprised when a "bad" sort algorithm turns out to be consistently the fastest for one of your sources of data. This is generally because the data had a certain amount of order, and one sort algorithm happened to take advantage of the order that existed. But the documentation rarely tells you what kinds of data it sorts the fastest.

I've also seen teams go through long, rancorous discussions of the best sort algorithm for their data, when it turns out their lists are typically under 100 items, and all the routines finish so fast that their clock can't even measure the differences.

I think you just made a good (though somewhat verbose :wink:) case for std::sort(), or whatever generic library routine is available.

User avatar
mikrit
Posts: 402
Joined: Sat Apr 14, 2012 8:13 pm UTC
Location: Sweden

Re: 1185: "Ineffective Sorts"

Postby mikrit » Wed Mar 13, 2013 8:12 pm UTC

algorerhythms wrote:I'm looking forward to an XKCD comic written in Shakespeare. "Thou art as brave as a beautiful lord! Speak your mind!"


http://xkcd.com/771/
Hatted and wimpled by ergman.
Dubbed "First and Eldest of Ottificators" by svenman.
Febrion wrote: "etc" is latin for "this would look better with more examples, but I can't think of any".

User avatar
Dingbats
Posts: 921
Joined: Tue Mar 20, 2007 12:46 pm UTC
Location: Sweden
Contact:

Re: 1185: "Ineffective Sorts"

Postby Dingbats » Wed Mar 13, 2013 8:20 pm UTC

Appity wrote:There is also the infamous Sleep Sort, discovered by a user on 4chan's programming text board: http://dis.4chan.org/read/prog/1295544154

Man, am I a genius. Check out this sorting algorithm I just invented.


Code: Select all

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait


example usage:

Code: Select all

./sleepsort.bash 5 3 6 3 6 3 1 4 7

WTF, it works. Can someone who hasn't forgotten all their programming skills please explain? Also, when you remove the sleep command it doesn't sort it.

User avatar
henre
Posts: 470
Joined: Sun Oct 29, 2006 10:04 pm UTC
Location: A healthy soul clings to a healthy spirit and a healthy body.

Re: 1185: "Ineffective Sorts"

Postby henre » Wed Mar 13, 2013 8:26 pm UTC

An airplane, a puppet, an orange, a spoon,
A window, and outside: stars, and the moon.

ʇɟıɥs sı ʎɹʇ oʇ ʇɟǝl ƃuıɥʇ ʎluo ǝɥʇ sǝɯıʇǝɯos

User avatar
dash
Posts: 104
Joined: Sat Mar 08, 2008 4:05 am UTC

Re: 1185: "Ineffective Sorts"

Postby dash » Wed Mar 13, 2013 8:28 pm UTC

Flumble wrote:
dash wrote:It can be proven that this WILL sort the list. But it might take a very long time...

No, you cannot be certain (for either real RNGs or pseudo-RNGs) that it will sort the list in any finite time. It has the same problem as bogosort and panicsort, namely using random without a heuristic* to change the list. Pure* randomness, by definition, does not bring you closer to or further from the desired state.


I think it's equivalent to a random walk over a finite space. Given infinite time you're guaranteed to step on every node.

It's similiar to (in a statistical sense) the proof that in the infinite decimal representation of the number pi exist all finite integers.

Strange things happen at infinity.

Of course I'm just talking out of my hat, I haven't seen proofs of any of these things. I just believe such proofs either exist or are possible...
If my wife were a D&D character she'd be all 10's

Gargravarr
Posts: 74
Joined: Mon Dec 21, 2009 8:34 am UTC

Re: 1185: "Ineffective Sorts"

Postby Gargravarr » Wed Mar 13, 2013 8:34 pm UTC

NeatNit wrote:
Isaac5 wrote:I am not a big enough nerd for this webcomic. I have no idea what any of this is.

*hangs head in shame*

I literally could not stop laughing. You don't belong here.

:P

Oh dear. Nerds can be really mean about random revenge. Which I support fully, of course.

"Well hello, old classmate. So you played football and got all the girls and dipped my head in the toilet? Isn't that cute. Came to ask me about your LinkedIn account, did you? Don't worry, I'm sure it's perfecly safe from hacking"

kwan3217
Posts: 27
Joined: Wed Jul 11, 2007 1:44 am UTC
Location: Sun-synchronous Earth Orbit

Re: 1185: "Ineffective Sorts"

Postby kwan3217 » Wed Mar 13, 2013 8:50 pm UTC

Dingbats wrote:
Appity wrote:There is also the infamous Sleep Sort, discovered by a user on 4chan's programming text board: http://dis.4chan.org/read/prog/1295544154

Man, am I a genius. Check out this sorting algorithm I just invented.


Code: Select all

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait


example usage:

Code: Select all

./sleepsort.bash 5 3 6 3 6 3 1 4 7

WTF, it works. Can someone who hasn't forgotten all their programming skills please explain? Also, when you remove the sleep command it doesn't sort it.


I had to think about this one for a moment, but once I got it, I had to try hard to not bust out laughing and disturb my cubemates. What it does is loop through all the command line arguments, and for each one, effectively spawn a background thread. That thread will interpret its argument as a number of seconds to sleep. Each thread will sleep for that many seconds then print its argument. The main thread then waits for all the background threads to finish before allowing the script to exit. It will work, and it will run in O(N) seconds where N is the maximum number in the list.

dash wrote:
Flumble wrote:
dash wrote:It can be proven that this WILL sort the list. But it might take a very long time...

No, you cannot be certain (for either real RNGs or pseudo-RNGs) that it will sort the list in any finite time. It has the same problem as bogosort and panicsort, namely using random without a heuristic* to change the list. Pure* randomness, by definition, does not bring you closer to or further from the desired state.


I think it's equivalent to a random walk over a finite space. Given infinite time you're guaranteed to step on every node.

It's similiar to (in a statistical sense) the proof that in the infinite decimal representation of the number pi exist all finite integers.

Strange things happen at infinity.

Of course I'm just talking out of my hat, I haven't seen proofs of any of these things. I just believe such proofs either exist or are possible...


No, that's not a proof that it will eventually work, it is just a proof that it will work with probability 1. As you said, strange things happen at infinity, and there, probability 1 is not the same thing as certainty, just like probability 0 is not the same thing as impossibility. Go read Wikipedia on "Almost always" or "almost never". For instance, you could flip a fair coin a large number of times. The sequence of outcomes you get has a probability of 1/2^n of happening, and yet you did get your sequence. At n=infinity, the probability of getting the sequence you do is zero, and yet you did get that sequence.

So, your random number generator could generate a sequence which would never ever ever ever sort your list. The probability is zero, but that doesn't make it impossible.
Last edited by kwan3217 on Wed Mar 13, 2013 8:56 pm UTC, edited 1 time in total.
Some people look at what is, and ask "why?"
Some people dream about what isn't, and ask "why not?"
I think about it for a while, then say "Oh, that's why not."

User avatar
Elvish Pillager
Posts: 1009
Joined: Mon Aug 04, 2008 9:58 pm UTC
Location: Everywhere you think, nowhere you can possibly imagine.
Contact:

Re: 1185: "Ineffective Sorts"

Postby Elvish Pillager » Wed Mar 13, 2013 8:53 pm UTC

Sleepsort is wonderful.

I'm a C++ programmer, myself.

Code: Select all

#include <iostream>
#include <sstream>
#include <vector>
#include <cassert>


// O(n)
bool lists_are_equal(std::vector<int> l1, std::vector<int> l2) {
  bool equal = true;
  for (size_t i = 0; (i < l1.size()) && (i < l2.size()); ++i) {
    if (l1[i] != l2[i]) equal = false;
  }
  if (l1.size() != l2.size()) equal = false;
  return equal;
}

// O(n^2)
std::vector<int> get_profile(std::vector<int> original_list, std::vector<int> list_to_profile) {
  std::vector<int> profile;
  for (size_t i = 0; i < original_list.size(); ++i) profile.push_back(0);
 
  for (int i : list_to_profile) {
    for (size_t j = 0; j < original_list.size(); ++j) {
      if (i == original_list[j]) ++profile[j];
    }
  }
  return profile;
}

// O(n^2)
bool is_sorted(std::vector<int> list) {
  bool sorted = true;
  for (size_t i = 0; i < list.size(); ++i) {
    for (size_t j = i + 1; j < list.size(); ++j) {
      if (list[i] > list[j]) sorted = false;
    }
  }
  return sorted;
}

std::vector<int> bureaucratic_sort(std::vector<int> list) {
  // It would be inefficient to just sort the list, when we can make a table of similar lists and their sorted versions for future reference.
  // Let's include all possible lists with elements from the original list, of lesser or equal size.
 
  std::vector<std::vector<int>> list_table;
  for (size_t i = 0; i <= list.size(); ++i) {
    std::vector<size_t> indexes;
    for (size_t j = 0; j < i; ++j) indexes.push_back(0);
    while (true) {
      std::vector<int> new_list;
      for (size_t j = 0; j < i; ++j) new_list.push_back(list[indexes[j]]);
     
      // Wouldn't want to include duplicates
      for (std::vector<int> l2 : list_table) {
        if (lists_are_equal(l2, new_list)) {
          goto listduplicated;
        }
      }
     
      list_table.push_back(new_list);
     
      listduplicated:
      size_t incremented_index = 0;
      while(true) {
        if (incremented_index >= i) goto doublebreak;
        ++indexes[incremented_index];
        if (indexes[incremented_index] >= list.size()) {
          indexes[incremented_index] = 0;
          ++incremented_index;
        }
        else break;
      }
    }
    doublebreak: ;
  }
 
  // Now we've generated the table of all the lists. Go find the sorted version of the list we started with.
  for (std::vector<int> potentially_sorted : list_table) {
    if (lists_are_equal(get_profile(list, potentially_sorted), get_profile(list, list)) && is_sorted(potentially_sorted)) {
      return potentially_sorted;
    }
  }
  assert(false);
}


int main() {
  while (true) {
    std::string line;
    getline(std::cin, line);
    std::stringstream line_stream(line);
    int num;
    std::vector<int> list;
    while (line_stream >> num) list.push_back(num);
    std::vector<int> sortedlist = bureaucratic_sort(list);
    std::cout << "Output: ";
    for(int i : sortedlist) std::cout << i << ", ";
    std::cout << "\n";
  }
}


I tested it on lists of up to 5 elements and it worked. Beyond that it's too slow.

It's not the most obscene possible algorithm (only O(n^(n+1) * n!), I think), but it was fun to write.
Also known as Eli Dupree. Check out elidupree.com for my comics, games, and other work.

GENERATION A(g64, g64): Social experiment. Take the busy beaver function of the generation number and add it to your signature.

speising
Posts: 2367
Joined: Mon Sep 03, 2012 4:54 pm UTC
Location: wien

Re: 1185: "Ineffective Sorts"

Postby speising » Wed Mar 13, 2013 8:55 pm UTC

kwan3217 wrote: It will work, and it will run in O(N) seconds where N is the maximum number in the list.

that's not the way the O notation works. it expresses complexity, not run time. lets just say it will take N seconds.

kwan3217
Posts: 27
Joined: Wed Jul 11, 2007 1:44 am UTC
Location: Sun-synchronous Earth Orbit

Re: 1185: "Ineffective Sorts"

Postby kwan3217 » Wed Mar 13, 2013 8:57 pm UTC

speising wrote:
kwan3217 wrote: It will work, and it will run in O(N) seconds where N is the maximum number in the list.

that's not the way the O notation works. it expresses complexity, not run time. lets just say it will take N seconds.


I knew someone would say that, and I wrote it anyway. Thanks for proving me right.
Some people look at what is, and ask "why?"
Some people dream about what isn't, and ask "why not?"
I think about it for a while, then say "Oh, that's why not."

johnschulien1
Posts: 1
Joined: Wed Mar 13, 2013 8:33 pm UTC

Re: 1185: "Ineffective Sorts"

Postby johnschulien1 » Wed Mar 13, 2013 8:58 pm UTC

I mean, seriously, when was the last time you actually implemented a sort routine? What? You don't have glib? What are you being paid to do?

algorerhythms
Posts: 44
Joined: Fri Nov 02, 2007 4:23 pm UTC

Re: 1185: "Ineffective Sorts"

Postby algorerhythms » Wed Mar 13, 2013 9:04 pm UTC

Issues I could see arising with sleep sort might include that if the main loop takes longer than one second to complete, an incorrect result may occur. Also, if floating point arguments are allowed, then the processing time of the main loop is even more important. Of course, this doesn't matter because nobody would use an algorithm that silly in the real world, right?

mikrit wrote:
algorerhythms wrote:I'm looking forward to an XKCD comic written in Shakespeare. "Thou art as brave as a beautiful lord! Speak your mind!"


http://xkcd.com/771/

I suppose I should have left a link with that post, in case someone hadn't heard of Shakespeare.
The nerdy webcomic that I update on Saturdays: Cesium Comics

User avatar
JohnTheWysard
Posts: 105
Joined: Sun Feb 10, 2008 2:38 am UTC

Re: 1185: "Ineffective Sorts"

Postby JohnTheWysard » Wed Mar 13, 2013 9:09 pm UTC

Well, that was sordid.

User avatar
super_aardvark
Posts: 54
Joined: Tue Jan 22, 2008 9:26 am UTC

Re: 1185: "Ineffective Sorts"

Postby super_aardvark » Wed Mar 13, 2013 9:10 pm UTC

speising wrote:
kwan3217 wrote: It will work, and it will run in O(N) seconds where N is the maximum number in the list.

that's not the way the O notation works. it expresses complexity, not run time. lets just say it will take N seconds.


Just because you happen to know exactly how long it will take for a given value of N doesn't make the notation invalid. O(N) time complexity just means when you double N, you double the amount of time it takes. That still holds in this case. The more confusing part is that N is the magnitude of the largest item in the list, instead of the size of the list, which is usually how sorting algorithms scale. But again, that doesn't make it an invalid use of the notation.

Also, Sleep Sort can't handle negative numbers.

EDIT: Oh... I see what you're saying: you can't say "it will run in O(N) seconds." I agree. But he could have also said "it will run in O(N) time."

kwan3217
Posts: 27
Joined: Wed Jul 11, 2007 1:44 am UTC
Location: Sun-synchronous Earth Orbit

Re: 1185: "Ineffective Sorts"

Postby kwan3217 » Wed Mar 13, 2013 9:21 pm UTC

super_aardvark wrote:EDIT: Oh... I see what you're saying: you can't say "it will run in O(N) seconds." I agree. But he could have also said "it will run in O(N) time."


I thought about writing time instead of seconds. It will run in O(N) seconds, as long as the unit used in sleep is seconds. O(N) time would be incorrect. I can't say that my car runs at 55 speed. I have to say 55 miles/hour.

Edit: I see what you are getting at. You are right. O() is supposed to factor out all the constants, and in a sense, a unit definition is a constant. So my car drives at 55 miles/hour, but my program runs in O(N) time (when I am lucky).

I never imagined having an argument on this particular topic. Ain't XKCD grand? :D
Some people look at what is, and ask "why?"
Some people dream about what isn't, and ask "why not?"
I think about it for a while, then say "Oh, that's why not."

dp2
Posts: 346
Joined: Wed Aug 18, 2010 3:06 pm UTC

Re: 1185: "Ineffective Sorts"

Postby dp2 » Wed Mar 13, 2013 9:25 pm UTC

kwan3217 wrote:
super_aardvark wrote:EDIT: Oh... I see what you're saying: you can't say "it will run in O(N) seconds." I agree. But he could have also said "it will run in O(N) time."


I thought about writing time instead of seconds. It will run in O(N) seconds, as long as the unit used in sleep is seconds. O(N) time would be incorrect. I can't say that my car runs at 55 speed. I have to say 55 miles/hour.

I never imagined having an argument on this particular topic. Ain't XKCD grand? :D

Wait, what? No. O(N) is not a number. So no, you can't say O(N) seconds or any other unit.

teelo
Posts: 783
Joined: Thu Apr 08, 2010 11:50 pm UTC

Re: 1185: "Ineffective Sorts"

Postby teelo » Wed Mar 13, 2013 10:01 pm UTC

That sleepsort is brilliant. I had to think about it for a while, but I can probably come up with a couple of practical applications for it!

Suppose you have a large amount of data to sort overnight, and processing power is your biggest concern, and time isn't that important. Many many lines of numbers to sort. Just run each line on sleepsort as its own process! The sorts all go from O(nlogn) to O(n)!

User avatar
dash
Posts: 104
Joined: Sat Mar 08, 2008 4:05 am UTC

Re: 1185: "Ineffective Sorts"

Postby dash » Wed Mar 13, 2013 10:09 pm UTC

kwan3217 wrote:So, your random number generator could generate a sequence which would never ever ever ever sort your list. The probability is zero, but that doesn't make it impossible.


I'm speaking of a finite list (which exists in reality) coupled with truly random numbers (which may or may not exist in reality). I believe any finite list is guaranteed to be sorted eventually (within infinite time) but within any finite time one can only speak of probabilities. There's no guarantee the sort program will terminate within any finite time.

Now if you're speaking of a pseudo-random number generator, I'll grant that you could construct a list of numbers that would "break" the random number generator, meaning you could prove it would never get sorted.

I think I'm done exploring this concept. Feel free to have the last word.
If my wife were a D&D character she'd be all 10's

rmsgrey
Posts: 3655
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: 1185: "Ineffective Sorts"

Postby rmsgrey » Wed Mar 13, 2013 10:12 pm UTC

O(N) describes the asymptotic behaviour of the (implicit) function as N tends to infinity. The number of seconds taken, expressed as a function of N, will indeed be bounded above by some constant multiple of N, so it's only a mild abuse of notation to say it takes O(N) seconds - to make it rigorous, you could say that sorting list L takes f(L) seconds where f(L)~O(MAX(L)).

User avatar
Elvish Pillager
Posts: 1009
Joined: Mon Aug 04, 2008 9:58 pm UTC
Location: Everywhere you think, nowhere you can possibly imagine.
Contact:

Re: 1185: "Ineffective Sorts"

Postby Elvish Pillager » Wed Mar 13, 2013 10:12 pm UTC

teelo, it only offloads the work onto the part of your system that manages all those separate processes.

If you have a load of ints that fit within that period of time, there's already an O(n) way to do it:
If it can finish "overnight" (let's say that's 10 hours) then all your ints are between 0 and 36000.
So you make a 36000-element array and zero it. Then iterate through your starting list and, for each number n, increment the nth element of the 36000-array.
Then go through the 36000-array in order.
Also known as Eli Dupree. Check out elidupree.com for my comics, games, and other work.

GENERATION A(g64, g64): Social experiment. Take the busy beaver function of the generation number and add it to your signature.

Showsni
Posts: 118
Joined: Wed Sep 14, 2011 9:09 pm UTC

Re: 1185: "Ineffective Sorts"

Postby Showsni » Wed Mar 13, 2013 10:15 pm UTC

Generate every possible permutation of the starting list.
Sort the generated lists by the first element.
Discard all such lists without the least first element.
Now sort by second element.
Discard all lists without the least second element.
and so on...
You're left with the sorted list.

At each sorting stage, use your favourite inefficient sort. But not this one, unless you want to be really inefficient.

airdrik
Posts: 246
Joined: Wed May 09, 2012 3:08 pm UTC

Re: 1185: "Ineffective Sorts"

Postby airdrik » Wed Mar 13, 2013 10:17 pm UTC

I, personally, am a fan of the infamous Drop Sort algorithm, guaranteed to produce a sorted list in O(n) time :twisted:

Code: Select all

define dropSort(list):
  for(i=1; i < list.length();)
    if list[i-1] > list[i]
      list.remove(i)
    else
      i++


Spoiler:
Though if you really needed those extra elements, you could recursively dropsort the dropped elements and merge them back into the sorted list, but you lose the O(n) complexity, but who cares about such things as data integrity when you need a sorted list FAST!
Last edited by airdrik on Wed Mar 13, 2013 10:21 pm UTC, edited 1 time in total.

teelo
Posts: 783
Joined: Thu Apr 08, 2010 11:50 pm UTC

Re: 1185: "Ineffective Sorts"

Postby teelo » Wed Mar 13, 2013 10:21 pm UTC

Code: Select all

DEFINE SearchSort(List):
    int pivot = (int) size(List)/2
    try
        int upperQuad = find(List[:pivot], 4)
    catch (needleNotFoundException)
        return "fuck, what am I doing again?"

User avatar
orthogon
Posts: 3104
Joined: Thu May 17, 2012 7:52 am UTC
Location: The Airy 1830 ellipsoid

Re: 1185: "Ineffective Sorts"

Postby orthogon » Wed Mar 13, 2013 10:22 pm UTC

I say we all go and read (I said read, not edit!) the Wikipedia page on Big O notation and then meet back here. (ninjad by rmsgrey - good work)

Meanwhile, back to this sorting problem. These new languages the kids use are all about functors, functionality injection and all classes are objects, right? So all you need to do is redefine the comparison operator in the class that the objects belong to, such that the list is already in order. Job done, O(1).

The sleep sort is one of the most beautiful things I've seen for a long time. The computer literally sorts the list in its sleep. You could deal with the negative numbers by finding the most negative value first and adding x_min+1. That would be O(N1),

1 where N2N3 obviously - I'm talking about the other N.
2 The largest element
3 The number of elements

[edit] couldn't resist...
xtifr wrote:... and orthogon merely sounds undecided.

jgh
Posts: 146
Joined: Thu Feb 03, 2011 1:04 pm UTC

Re: 1185: "Ineffective Sorts"

Postby jgh » Wed Mar 13, 2013 10:44 pm UTC

mrob27 wrote:For a 1984 example, see "Pessimal Algorithms and Simplexity Analysis" by Broder and Stolfi:
Doh! I've just got a Pratchett joke!

User avatar
Negrebskoh
Posts: 139
Joined: Fri Mar 01, 2013 11:49 pm UTC
Location: The Netherlands

Re: 1185: "Ineffective Sorts"

Postby Negrebskoh » Wed Mar 13, 2013 11:27 pm UTC

Seeing as all the funny jokes are already taken, I'd just like to say that I laughed like a madman for a full five minutes after I read this comic. I loved it.

Now, let's implement that StackSort. I looked at the html source of those pages, and they actually fit the code in <code> tags quite neatly. You'd need some heuristics for error checking and some way to check if the code is actually sensible before running it, of course (and it should probably not run as root either), but I'm half-seriously considering writing a script to do this in a limited fashion.

User avatar
da Doctah
Posts: 997
Joined: Fri Feb 03, 2012 6:27 am UTC

Re: 1185: "Ineffective Sorts"

Postby da Doctah » Wed Mar 13, 2013 11:28 pm UTC

super_aardvark wrote:
kwan3217 wrote: It will work, and it will run in O(N) seconds where N is the maximum number in the list.


Also, Sleep Sort can't handle negative numbers.


Kind of a drag with floating-point data too.

teelo
Posts: 783
Joined: Thu Apr 08, 2010 11:50 pm UTC

Re: 1185: "Ineffective Sorts"

Postby teelo » Wed Mar 13, 2013 11:44 pm UTC

orthogon wrote:Meanwhile, back to this sorting problem. These new languages the kids use are all about functors, functionality injection and all classes are objects, right? So all you need to do is redefine the comparison operator in the class that the objects belong to, such that the list is already in order. Job done, O(1).

Oh yeah? Well I see your "Redefine the comparison" idea and raise you "ignorance is bliss":

Code: Select all

DEFINE IgnorantSort(List):
    return List // ignorance is bliss


There. O(0)

teelo
Posts: 783
Joined: Thu Apr 08, 2010 11:50 pm UTC

Re: 1185: "Ineffective Sorts"

Postby teelo » Wed Mar 13, 2013 11:46 pm UTC

da Doctah wrote:
super_aardvark wrote:
kwan3217 wrote: It will work, and it will run in O(N) seconds where N is the maximum number in the list.


Also, Sleep Sort can't handle negative numbers.


Kind of a drag with floating-point data too.

Square the value and multiply by a thousand or so!

User avatar
Elvish Pillager
Posts: 1009
Joined: Mon Aug 04, 2008 9:58 pm UTC
Location: Everywhere you think, nowhere you can possibly imagine.
Contact:

Re: 1185: "Ineffective Sorts"

Postby Elvish Pillager » Wed Mar 13, 2013 11:46 pm UTC

inb4 someone posts "How to exploit StackSort while it sorts a list?" on StackOverflow, with code suggestions
Also known as Eli Dupree. Check out elidupree.com for my comics, games, and other work.

GENERATION A(g64, g64): Social experiment. Take the busy beaver function of the generation number and add it to your signature.

teelo
Posts: 783
Joined: Thu Apr 08, 2010 11:50 pm UTC

Re: 1185: "Ineffective Sorts"

Postby teelo » Wed Mar 13, 2013 11:49 pm UTC

I thought the windows command for delete directory was "rmdir" and requires the directory to be empty to even work, or "deltree"?

User avatar
tibfulv
Posts: 49
Joined: Tue Nov 27, 2012 11:31 am UTC

Re: 1185: "Ineffective Sorts"

Postby tibfulv » Wed Mar 13, 2013 11:54 pm UTC

Description of the rd command in Win 2000 and later. Apparently /s allows you to do the deltree thing.


Edit: How long has it been since we used the Windows command line? A while, it seems. (I was going to write 'used Windows', then remembered I was using it to type. Apparently, in my heart, i'm still a Unixman, an eternal immigrant in Microsoftland ....)
Last edited by tibfulv on Thu Mar 14, 2013 12:03 am UTC, edited 1 time in total.

User avatar
phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: 1185: "Ineffective Sorts"

Postby phlip » Thu Mar 14, 2013 12:02 am UTC

teelo wrote:I thought the windows command for delete directory was "rmdir" and requires the directory to be empty to even work, or "deltree"?

Unlike POSIX, which has exactly "cd", "mkdir", and "rmdir"... DOS/Windows will accept either of "CD"/"CHDIR", "MD"/"MKDIR" and "RD"/"RMDIR".
As for the other part:
RD/? wrote:RMDIR [/S] [/Q] [drive:]path
RD [/S] [/Q] [drive:]path

/S Removes all directories and files in the specified directory in addition to the directory itself. Used to remove a directory tree.

/Q Quiet mode, do not ask if ok to remove a directory tree with /S

In at least some versions of DOS, RD didn't have these switches, and there was a separate utility DELTREE that did recursive deletes... but now it's all rolled into RD and DELTREE doesn't exist any more.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

teelo
Posts: 783
Joined: Thu Apr 08, 2010 11:50 pm UTC

Re: 1185: "Ineffective Sorts"

Postby teelo » Thu Mar 14, 2013 12:06 am UTC

Ahh okay. Oh the good old days of using someones computer, editing their autoexec.bat file putting "deltree c:\windows\" on the first line, and walking away 8-)


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: No registered users and 102 guests