## 1185: "Ineffective Sorts"

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

Moderators: Moderators General, Prelates, Magistrates

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

### Re: 1185: "Ineffective Sorts"

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.

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"

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.

Knight Temporal, and Archdeacon of buttermongery and ham and cheese sandwiches. Nobody sells butter except through me.
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.

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

### Re: 1185: "Ineffective Sorts"

Well, sort of.

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

### Re: 1185: "Ineffective Sorts"

Klear wrote:

Well, sort of.

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

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

### Re: 1185: "Ineffective Sorts"

orthogon wrote:
Klear wrote:

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"

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"

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"

Negrebskoh wrote:
orthogon wrote:
Klear wrote:

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?

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"

airdrik wrote:
Negrebskoh wrote:
orthogon wrote:
Klear wrote:

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

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

### Re: 1185: "Ineffective Sorts"

Angelastic wrote:
airdrik wrote:
Negrebskoh wrote:
orthogon wrote:
Klear wrote:

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

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

### Re: 1185: "Ineffective Sorts"

Klear wrote:
Angelastic wrote:
airdrik wrote:
Negrebskoh wrote:
orthogon wrote:
Klear wrote:

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"

Awesome and inspirational!

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

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

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: 3633
Joined: Wed Nov 16, 2011 6:35 pm UTC

### Re: 1185: "Ineffective Sorts"

Voracle wrote:Awesome and inspirational!

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

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:

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

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

### Re: 1185: "Ineffective Sorts"

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=010 FOR I=0 TO 920 IF SC(I)<SC(I+1) THEN GOSUB 100030 NEXT I40 IF C>=0 THEN GOTO 5(...)999 REM SWAP PROCEDURE1000 A=SC(I):SC(I)=SC(I+1):SC(I+1)=A1010 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 sortreturn`

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

### Re: 1185: "Ineffective Sorts"

Um, the first one is an endless loop.

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

### Re: 1185: "Ineffective Sorts"

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!

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

### Re: 1185: "Ineffective Sorts"

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"

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"

orthogon wrote:Does any language have a swap function?

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

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

### Re: 1185: "Ineffective Sorts"

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.

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

### Re: 1185: "Ineffective Sorts"

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.

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

### Re: 1185: "Ineffective Sorts"

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

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

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.

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

### Re: 1185: "Ineffective Sorts"

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.

Pfhorrest
Posts: 5448
Joined: Fri Oct 30, 2009 6:11 am UTC
Contact:

### Re: 1185: "Ineffective Sorts"

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"

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.

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

### Re: 1185: "Ineffective Sorts"

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?

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

### Re: 1185: "Ineffective Sorts"

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: 3633
Joined: Wed Nov 16, 2011 6:35 pm UTC

### Re: 1185: "Ineffective Sorts"

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

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

### Re: 1185: "Ineffective Sorts"

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"

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"

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?

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

### Re: 1185: "Ineffective Sorts"

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 GAME20 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: 3633
Joined: Wed Nov 16, 2011 6:35 pm UTC

### Re: 1185: "Ineffective Sorts"

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"

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: 2354
Joined: Mon Sep 03, 2012 4:54 pm UTC
Location: wien

### Re: 1185: "Ineffective Sorts"

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

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

### Re: 1185: "Ineffective Sorts"

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

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

### Re: 1185: "Ineffective Sorts"

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"

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"

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

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"

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.

### Who is online

Users browsing this forum: Google [Bot], rhomboidal and 41 guests