1185: "Ineffective Sorts"

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

Moderators: Moderators General, Prelates, Magistrates

User avatar
PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: 1185: "Ineffective Sorts"

Postby PM 2Ring » Fri Mar 15, 2013 7:57 am UTC

I was reading an old article on sorting algorithms earlier this week. It said that the only reason that it mentioned Bubble Sort was so that readers could recognise it and replace it with a better algorithm if they ever encountered it in code that they were maintaining. :)

If you have an almost-sorted list that you're tempted to use Bubble Sort on, try the bidirectional version, Cocktail Sort, instead.


To sort a deck of cards, I like to use a base 4 Radix Sort, which lets you sort a normal deck in 3 passes using only 4 piles of cards. With practice, the process can be rather fast.

Radix Sort can be very efficient in situations like that where you expect your keys to be a complete set of integers starting from a low integer. I first encountered Radix Sort back in the day of punched cards. It was commonly used to mechanically sort cards that had numbers encoded in binary (or BCD) as (potentially) notched holes along a card edge. A normal hole represented a 0 bit, a hole with a notch to the card edge represented a 1 bit, so a large deck of such cards could be Radix sorted by hand using a knitting needle (or similar) very quickly.

As you might guess, I have a soft spot for Radix Sort; in fact, it was the first sorting algorithm I ever implemented in a program.

User avatar
Angelastic
Posts: 700
Joined: Thu Nov 03, 2011 8:36 am UTC
Location: .at (let's see what's through here!)
Contact:

Re: 1185: "Ineffective Sorts"

Postby Angelastic » Fri Mar 15, 2013 8:43 am UTC

mathmannix wrote: (I think this might be the order a new deck comes in, but it might not be exactly, and the internet couldn't give me a definitive answer here.)

There is no definitive answer. I have a large collection of souvenir playing cards. Some come with Aces high, others with Aces low, and they put the suits in various different orders, and the (zero to four) jokers in different places in the deck. Usually it's consistent across a given manufacturer.

Anyway, what I wanted to say about this comic: It takes all sorts.
Knight Temporal, and Archdeacon of buttermongery and ham and cheese sandwiches. Nobody sells butter except through me.
Image Smiley by yappobiscuits. Avatar by GLR, buffygirl, BlitzGirl & mscha, with cari.j.elliot's idea.
Haiku Detector
starts a trend to make way for
my robot army.

User avatar
Klear
Posts: 1965
Joined: Sun Jun 13, 2010 8:43 am UTC
Location: Prague

Re: 1185: "Ineffective Sorts"

Postby Klear » Fri Mar 15, 2013 9:18 am UTC

Angelastic wrote:Anyway, what I wanted to say about this comic: It takes all sorts.


Well, sort of.

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

Re: 1185: "Ineffective Sorts"

Postby orthogon » Fri Mar 15, 2013 10:03 am UTC

Klear wrote:
Angelastic wrote:Anyway, what I wanted to say about this comic: It takes all sorts.


Well, sort of.

I would contribute another algorithm, but I'm feeling out of sorts.
xtifr wrote:... and orthogon merely sounds undecided.

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

Re: 1185: "Ineffective Sorts"

Postby Negrebskoh » Fri Mar 15, 2013 10:08 am UTC

orthogon wrote:
Klear wrote:
Angelastic wrote:Anyway, what I wanted to say about this comic: It takes all sorts.


Well, sort of.

I would contribute another algorithm, but I'm feeling out of sorts.


Think you need some help to sort that out?

Oktalist
Posts: 79
Joined: Thu Apr 22, 2010 10:13 pm UTC

Re: 1185: "Ineffective Sorts"

Postby Oktalist » Fri Mar 15, 2013 1:16 pm UTC

sep332 wrote:Funny. It's basically Python: ... no variable type declarations ...

There's no variable declarations at all. There's no need to qualify it.
philip1201 wrote:Not everything which maps countable infinities onto finite areas is a Lovecraft reference.

Kit.
Posts: 1117
Joined: Thu Jun 16, 2011 5:14 pm UTC

Re: 1185: "Ineffective Sorts"

Postby Kit. » Fri Mar 15, 2013 2:15 pm UTC

Oktalist wrote:
sep332 wrote:Funny. It's basically Python: ... no variable type declarations ...

There's no variable declarations at all. There's no need to qualify it.

There is. The global statement.

(TBH, I hadn't heard of this statement before I read your comment, but I was pretty sure there ought to be some mechanism to distinguish between local and global scope during assignments)

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

Re: 1185: "Ineffective Sorts"

Postby airdrik » Fri Mar 15, 2013 3:14 pm UTC

Negrebskoh wrote:
orthogon wrote:
Klear wrote:
Angelastic wrote:Anyway, what I wanted to say about this comic: It takes all sorts.


Well, sort of.

I would contribute another algorithm, but I'm feeling out of sorts.


Think you need some help to sort that out?

Hey, what sort of place do you think this is, anyway?

User avatar
Angelastic
Posts: 700
Joined: Thu Nov 03, 2011 8:36 am UTC
Location: .at (let's see what's through here!)
Contact:

Re: 1185: "Ineffective Sorts"

Postby Angelastic » Fri Mar 15, 2013 4:24 pm UTC

airdrik wrote:
Negrebskoh wrote:
orthogon wrote:
Klear wrote:
Angelastic wrote:Anyway, what I wanted to say about this comic: It takes all sorts.


Well, sort of.

I would contribute another algorithm, but I'm feeling out of sorts.


Think you need some help to sort that out?

Hey, what sort of place do you think this is, anyway?
Going by some of the algorithms, it's an extravagant resort.
Knight Temporal, and Archdeacon of buttermongery and ham and cheese sandwiches. Nobody sells butter except through me.
Image Smiley by yappobiscuits. Avatar by GLR, buffygirl, BlitzGirl & mscha, with cari.j.elliot's idea.
Haiku Detector
starts a trend to make way for
my robot army.

User avatar
Klear
Posts: 1965
Joined: Sun Jun 13, 2010 8:43 am UTC
Location: Prague

Re: 1185: "Ineffective Sorts"

Postby Klear » Fri Mar 15, 2013 4:41 pm UTC

Angelastic wrote:
airdrik wrote:
Negrebskoh wrote:
orthogon wrote:
Klear wrote:
Angelastic wrote:Anyway, what I wanted to say about this comic: It takes all sorts.


Well, sort of.

I would contribute another algorithm, but I'm feeling out of sorts.


Think you need some help to sort that out?

Hey, what sort of place do you think this is, anyway?
Going by some of the algorithms, it's an extravagant resort.


But you should only use some of them as a last resort.
also orthogon should post next, to keep the same order of posters

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

Re: 1185: "Ineffective Sorts"

Postby orthogon » Fri Mar 15, 2013 5:13 pm UTC

Klear wrote:
Angelastic wrote:
airdrik wrote:
Negrebskoh wrote:
orthogon wrote:
Klear wrote:
Angelastic wrote:Anyway, what I wanted to say about this comic: It takes all sorts.


Well, sort of.

I would contribute another algorithm, but I'm feeling out of sorts.


Think you need some help to sort that out?

Hey, what sort of place do you think this is, anyway?
Going by some of the algorithms, it's an extravagant resort.


But you should only use some of them as a last resort.
also orthogon should post next, to keep the same order of posters

Since you insist...
I don't have a further sort-based pun1, but I do have a question: In the competition for inefficient algorithms, how did they arrive at the final league table? Did they sort the entries by complexity, in which case what algorithm did they use? Using any halfway decent one would demonstrate a lack of real commitment to the cause...
1 [Edit:] Except perhaps for this: If the particular period and pattern of movement caused by travelling in a particular Spanish-manufactured train caused discomfort in the passengers, that might constitute a "sore Talgo rhythm".
Last edited by orthogon on Fri Mar 15, 2013 5:22 pm UTC, edited 1 time in total.
xtifr wrote:... and orthogon merely sounds undecided.

Voracle
Posts: 3
Joined: Tue Nov 16, 2010 1:40 am UTC

Re: 1185: "Ineffective Sorts"

Postby Voracle » Fri Mar 15, 2013 5:20 pm UTC

Awesome and inspirational!

Here's a few I just pondered up from this comic:

function ParadoxSort(list, Future* temporalVariable) {
temporalVariable = getSortFromFuture(list);
//the list is now sorted and ready for reading by another processor somewhere else, but now you have to do the work

system.thread.beginsort(list); //if you list returns unsorted, that's cuz you turned off this process before it could finish
return 0;
}

CaptchaSort:

Users are given some items to sort in place of a captcha. The list is matched against the average of various tries by other users then sent on for output. This has the advantage of being able to sort nearly anything known by humans, whether it be jelly bean colors or depth of submarines.

GeneticSort:

Various sorting algorithms break up their code into "operation" characteristics. They then decide to mate and have offsprings with their own sorting characteristics. May be the best sorting algorithm win, sexually.


RelativitySort:

A sorter starts sorting at the same time that the user is sent in near the event horizon of a blackhole. When the user returns, sufficient time has passed for the original frame such that the user has a sorted list in relatively little time.

RouletteSort:

A bullet is fired at the user for each step of the sorting algorithm takes until the user accepts the state as the answer.

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

Re: 1185: "Ineffective Sorts"

Postby rmsgrey » Fri Mar 15, 2013 10:50 pm UTC

Voracle wrote:Awesome and inspirational!

Here's a few I just pondered up from this comic:

function ParadoxSort(list, Future* temporalVariable) {
temporalVariable = getSortFromFuture(list);
//the list is now sorted and ready for reading by another processor somewhere else, but now you have to do the work

system.thread.beginsort(list); //if you list returns unsorted, that's cuz you turned off this process before it could finish
return 0;
}


Surely you can just return the sorted list to the past. Something like:

function ParadoxSort(list)
{
list = getSortFromFuture(list);
if (list.IsSorted)
{
SendSortToPast(list);
return list;
}
else
{
//MoR check
if (list == "Do not mess with time.")
{
SendSortToPast(list);
Throw (SmartassError)
}
else
{
list = list.Shuffle();
SendSortToPast(list);
}
}
}

User avatar
Don Calvus
Posts: 54
Joined: Fri Sep 21, 2012 10:57 am UTC

Re: 1185: "Ineffective Sorts"

Postby Don Calvus » Fri Mar 15, 2013 11:53 pm UTC

I am 17% nerd. I used to do some programming in Basic on 8-bit and 16/32-bit machines. During the 8-bit era, I owned a French computer called Hector and the Basic included in ROM didn't have anything close to a SORT function, of course. It also didn't even have a SWAP function. And I would try to write a good sorting algorithm to be able to display a proper "Hall of Fame" in the games I (poorly) designed.

Something like this, I guess, for a 10 "hi-scores" list (all-caps mode courtesy of the 1980s), sorted in descendent order:

Code: Select all

5 C=0
10 FOR I=0 TO 9
20 IF SC(I)<SC(I+1) THEN GOSUB 1000
30 NEXT I
40 IF C>=0 THEN GOTO 5
(...)
999 REM SWAP PROCEDURE
1000 A=SC(I):SC(I)=SC(I+1):SC(I+1)=A
1010 C=C+1:RETURN


It began to be more elegant without line numbers and the introduction of structured and functional BASICs like GFA or Omikron (on the Atari ST platform):

Code: Select all

procedure sort(score())
   :sort
   counter%=0
   for i%=1 to 10
      if score(i%) < score(i%+1) then
         swap score(i%),score(i%+1)
         inc counter%
      endif
   next i%
   if counter% <> 0 then goto sort
return

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

Re: 1185: "Ineffective Sorts"

Postby speising » Sat Mar 16, 2013 12:24 pm UTC

Um, the first one is an endless loop.

User avatar
Don Calvus
Posts: 54
Joined: Fri Sep 21, 2012 10:57 am UTC

Re: 1185: "Ineffective Sorts"

Postby Don Calvus » Sat Mar 16, 2013 1:20 pm UTC

speising wrote:Um, the first one is an endless loop.


Indeed. Don't know why I didn't write IF C <> 0 or simply > 0. I was tired, I guess!

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

Re: 1185: "Ineffective Sorts"

Postby orthogon » Sat Mar 16, 2013 1:39 pm UTC

Does any language have a swap function?
VHDL is quite interesting because you can do it the "rookie mistake" way and it actually works:

Code: Select all

swap: process (x,y)
begin
  x<=y;
  y<=x;
end process;


VHDL is the devil's language in most ways.
xtifr wrote:... and orthogon merely sounds undecided.

bfeist
Posts: 12
Joined: Mon May 07, 2012 10:54 am UTC

Re: 1185: "Ineffective Sorts"

Postby bfeist » Sat Mar 16, 2013 1:46 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 does, however have a half-life.

bfeist
Posts: 12
Joined: Mon May 07, 2012 10:54 am UTC

Re: 1185: "Ineffective Sorts"

Postby bfeist » Sat Mar 16, 2013 1:51 pm UTC

orthogon wrote:Does any language have a swap function?


FORTH, although it's not directly useful in the context of sorting.

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

Re: 1185: "Ineffective Sorts"

Postby orthogon » Sat Mar 16, 2013 4:15 pm UTC

I've just realised what this reminds me of: the -h switch on diff that made it "do a fast, half-hearted job".

I move that all *ix commands should have this option. (In Windows, -h is the default). Here are some examples:

sort -h: half-hearted merge sort
ls -h: list some of the files in the directory
find -h: randomly ignore whole directories, whilst possibly looking multiple times in others (the technique I use for searching for objects in my flat)
mv -h: Move about half of the file into the new directory. May alternatively move the entire file but into a directory "halfway between" its current location and the specified destination.
xtifr wrote:... and orthogon merely sounds undecided.

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

Re: 1185: "Ineffective Sorts"

Postby Negrebskoh » Sat Mar 16, 2013 8:07 pm UTC

orthogon wrote:mv -h: Move about half of the file into the new directory. May alternatively move the entire file but into a directory "halfway between" its current location and the specified destination.


That's going to be so much fun once a BOFH adds "alias mv='mv -h'" to everyone's .bashrc. :twisted:

webgiant
Posts: 252
Joined: Mon Aug 17, 2009 5:36 pm UTC

Re: 1185: "Ineffective Sorts"

Postby webgiant » Sat Mar 16, 2013 8:56 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

I think the sole requirement is "you've taken a class in coding". I haven't coded in 9 years and didn't hear about all the coding jokes even when I did write code, and I couldn't stop laughing. Non-programmers could get away with taking one of those meta coding classes, where you never write software, only describe what your code would eventually do.

User avatar
5th Earth
Posts: 62
Joined: Sat Aug 18, 2007 7:22 pm UTC
Location: Santa Cruz, California

Re: 1185: "Ineffective Sorts"

Postby 5th Earth » Sat Mar 16, 2013 10:00 pm UTC

Aedl Foxe wrote:
Daniel on StackOverflow wrote:I had a lecturer who once suggested generating a random array, checking if it was sorted and then checking if the data was the same as the array to be sorted.


I was so entertained by this that I had to write an implementation. This might not be the most efficient way to do it, but it's been a while since I really dug into C++.

Code: Select all

some code


I clocked the floating-point generation code at 8.2e-7 s, and since it'll take on average 264 generations to get one element to match, I figure it'll take this code about 480000 years to sort a list containing one element.

The analysis is a little confusing, though. Anyone care to do the math?


Thought: this sort could be made even slower and less efficient by, if the random list isn't sorted, recursively using the same sort to sort the random list you are using for the comparison to the original list.
It seemed like a good idea at the time.

User avatar
Pfhorrest
Posts: 5447
Joined: Fri Oct 30, 2009 6:11 am UTC
Contact:

Re: 1185: "Ineffective Sorts"

Postby Pfhorrest » Sat Mar 16, 2013 10:53 pm UTC

webgiant wrote:I think the sole requirement is "you've taken a class in coding".

Not even that. I've never taken a single class in coding and I got the joke well enough. (Then again I have the title "Software Engineer" on my CV, but totally don't deserve it. I've never written a sort algorithm in my life, though I wouldn't put it past me to reinvent one of the simpler ones if I had to).
Forrest Cameranesi, Geek of All Trades
"I am Sam. Sam I am. I do not like trolls, flames, or spam."
The Codex Quaerendae (my philosophy) - The Chronicles of Quelouva (my fiction)

webgiant
Posts: 252
Joined: Mon Aug 17, 2009 5:36 pm UTC

Re: 1185: "Ineffective Sorts"

Postby webgiant » Mon Mar 18, 2013 1:16 am UTC

Pfhorrest wrote:
webgiant wrote:I think the sole requirement is "you've taken a class in coding".

Not even that. I've never taken a single class in coding and I got the joke well enough. (Then again I have the title "Software Engineer" on my CV, but totally don't deserve it. I've never written a sort algorithm in my life, though I wouldn't put it past me to reinvent one of the simpler ones if I had to).

I say "class" because this is where most people get their formal training in coding, but opening a coding book all on your own would suffice.

User avatar
pitareio
Posts: 128
Joined: Wed Sep 19, 2012 7:03 pm UTC
Location: the land of smelly cheese

Re: 1185: "Ineffective Sorts"

Postby pitareio » Mon Mar 18, 2013 2:10 am UTC

I've been working as a programmer for almost 15 years and I never, ever had to code a sort algorithm since I left university. If I found myself in a situation in which I had to code it myself instead of using existing libraries or a database, I'd think I got wrong somewhere.

Off the top of my head, I'm not sure I could code anything but a lousy bubble sort.

Has anyone here actually had to write a sort in a job interview?

User avatar
Flumble
Yes Man
Posts: 2249
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: 1185: "Ineffective Sorts"

Postby Flumble » Mon Mar 18, 2013 3:44 pm UTC

5th Earth wrote:
Aedl Foxe wrote:
Daniel on StackOverflow wrote:I had a lecturer who once suggested generating a random array, checking if it was sorted and then checking if the data was the same as the array to be sorted.

...

I clocked the floating-point generation code at 8.2e-7 s, and since it'll take on average 264 generations to get one element to match, I figure it'll take this code about 480000 years to sort a list containing one element.


Thought: this sort could be made even slower and less efficient by, if the random list isn't sorted, recursively using the same sort to sort the random list you are using for the comparison to the original list.

You are a horrible person.

For 2 elements ranging 0..9, there's a 55% chance the elements will be sorted, in which case there's a 1.8% chance the algorithm will finish, and 45% chance the algorithm will be called again, in which case there's a 45% chance it will be called again (and only a 1% chance it will return) etcetera.
While in some cardinality of infinity the algorithm will almost surely return, in reality your computer will grow arms and slap you in the face so hard you dedicate your life to praising modern art and jumping around in your neighbour's back yard whistling Losing my Religion.

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

Re: 1185: "Ineffective Sorts"

Postby rmsgrey » Mon Mar 18, 2013 4:04 pm UTC

pitareio wrote:I've been working as a programmer for almost 15 years and I never, ever had to code a sort algorithm since I left university. If I found myself in a situation in which I had to code it myself instead of using existing libraries or a database, I'd think I got wrong somewhere.

Off the top of my head, I'm not sure I could code anything but a lousy bubble sort.

Has anyone here actually had to write a sort in a job interview?


I coded heapsort about 6 months ago - had a project where it would be useful, performance wasn't an issue (having to keep a heap of maybe a dozen items, with the heap only needing to be valid once per minute) and it was easier than figuring out how to hand a comparison function into the standard library...

It was as much to have done it as to take the most efficient solution path (bubblesort would work just as well under the circumstances...)

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

Re: 1185: "Ineffective Sorts"

Postby orthogon » Mon Mar 18, 2013 4:14 pm UTC

Flumble wrote:... you dedicate your life to praising modern art and jumping around in your neighbour's back yard whistling Losing my Religion.

Welcome to my world.
xtifr wrote:... and orthogon merely sounds undecided.

sep332
Posts: 11
Joined: Thu Sep 16, 2010 10:42 pm UTC

Re: 1185: "Ineffective Sorts"

Postby sep332 » Mon Mar 18, 2013 7:00 pm UTC

Oktalist wrote:
sep332 wrote:Funny. It's basically Python: ... no variable type declarations ...

There's no variable declarations at all. There's no need to qualify it.

There is "N" as the loop counter. Also the function itself has no return type specified.

quassnoi
Posts: 1
Joined: Sat Jan 01, 2011 11:30 pm UTC

Re: 1185: "Ineffective Sorts"

Postby quassnoi » Tue Mar 19, 2013 1:59 pm UTC

pitareio wrote:I've been working as a programmer for almost 15 years and I never, ever had to code a sort algorithm since I left university. If I found myself in a situation in which I had to code it myself instead of using existing libraries or a database, I'd think I got wrong somewhere.

Off the top of my head, I'm not sure I could code anything but a lousy bubble sort.

Has anyone here actually had to write a sort in a job interview?


Google asks to implement sort on screening interviews.

User avatar
AlexTheSeal
Posts: 53
Joined: Mon Oct 26, 2009 12:57 am UTC

Re: 1185: "Ineffective Sorts"

Postby AlexTheSeal » Tue Mar 19, 2013 5:09 pm UTC

webgiant wrote:Non-programmers could get away with taking one of those meta coding classes, where you never write software, only describe what your code would eventually do.

Doesn't this just describe any CS graduate program?

*rimshot*

*ducks*

Code: Select all

10 REM WORLD'S SMALLEST ADVENTURE GAME
20 PRINT "YOU ARE IN A CAVE (N, S, E, W)? ";
30 INPUT A$
40 GOTO 10

Lulled to sleep by the one-hertz chuckle of Linux logfile writes since 1997.

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

Re: 1185: "Ineffective Sorts"

Postby rmsgrey » Tue Mar 19, 2013 5:15 pm UTC

AlexTheSeal wrote:
webgiant wrote:Non-programmers could get away with taking one of those meta coding classes, where you never write software, only describe what your code would eventually do.

Doesn't this just describe any CS graduate program?

*rimshot*

*ducks*


Sounds like my programming job - describe what the code will eventually do, and refine the description until the computer understands it (also known as top-down design)

bfeist
Posts: 12
Joined: Mon May 07, 2012 10:54 am UTC

Re: 1185: "Ineffective Sorts"

Postby bfeist » Wed Mar 20, 2013 12:22 am UTC

rmsgrey: isn't it more traditional to write the program, observe what it does, and then refine the specifications until the program works as specified?

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

Re: 1185: "Ineffective Sorts"

Postby speising » Wed Mar 20, 2013 8:42 am UTC

more like: write the program, and, six months later, get asked what it does so someone can write a specification.

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

Re: 1185: "Ineffective Sorts"

Postby rmsgrey » Wed Mar 20, 2013 10:30 am UTC

bfeist wrote:rmsgrey: isn't it more traditional to write the program, observe what it does, and then refine the specifications until the program works as specified?

You haven't seen the specifications we get given... "We need to tell the customer what time it is."

With a "spec" like that, it's hard to get the program to not meet the spec...

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 20, 2013 1:35 pm UTC

Not sure if it's been posted already, but it appears someone built StackSort.

jabakobob
Posts: 1
Joined: Tue Mar 19, 2013 4:11 pm UTC

Re: 1185: "Ineffective Sorts"

Postby jabakobob » Wed Mar 20, 2013 3:07 pm UTC

I'm a bit disappointed that of all the nerds in this thread, nobody could write down the complexity of sleep sort. Everyone seemed to be confused about what "N" in the big-O notation usually stands for. In complexity theory, N usually stands for the length of the input. This is not the same as the number of elements in the list. (you need more input symbols to write larger numbers)

So what is the maximum number that can be represented with input of length N? Since we are using decimal numbers, the maximum number that can be represented is approximately 10^N, or exp(ln(10)*N), so the running time of sleep sort in big-Oh notation is O(exp(N))

bfeist
Posts: 12
Joined: Mon May 07, 2012 10:54 am UTC

Re: 1185: "Ineffective Sorts"

Postby bfeist » Wed Mar 20, 2013 4:48 pm UTC

jabakobob wrote: In complexity theory, N usually stands for the length of the input. This is not the same as the number of elements in the list. (you need more input symbols to write larger numbers)


Wouldn't this reasoning make the sorts that the literature refers to as O(n log n) different? If k = the # of items to sort, and we assume that the length of each item (assuming fixed-length) is proportional to log k, then n, the total length, would be O(k log k). Time to compare or swap two items would be proportional to the length of an item, so that's O(log k). The total number of swaps and comparisons is O(k log k), so the algorithms would be O(k log^2 k) = O(, which is O(n log k) -- slower than O(n) but faster than the claimed O(n log n).

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 20, 2013 5:25 pm UTC

If

n = O(k log k)

then

log n = O(log(k log k)) = O(log k + log log k) = O(log k)

Hence there is no asymptotic difference between log n and log k.
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.


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: rmsgrey and 29 guests