In the mostly defunct “Currently Listening To” series, today we feature Moustache (half a scissor), the new album by Mr. Oizo.

Most (some?) people will still remember Mr. Oizo from the famous 1999 Levi’s commercials in which the song “Flat beat” and the yellow puppet figure “Mr. Oizo” were featured. What most people don’t know however, is that in the same year, Mr. Oizo (a pseudonym for Quentin Dupieux, the producer behind the commercial) also released an album called Analog Worms Attack. In fact I didn’t know either, until some years ago I bought it for a euro or so in some obscure shop in the Czech Republic. It’s sort of very minimalistic electronic techno-ish music, but in a very strange kind of way.

Anyway, now after 6 years, Quentin Dupieux managed to pull another 30 minutes of strange techno together. The album doesn’t seem to be out yet, but it is featured on the 3voor12 luisterpaal this week, so anyone can listen to it which is quite nice. I haven’t finished listening to it (currently at track 14, calld “1$44″), but the first impression is that the second album is even stranger than the first. While the first had tracks that were clearly recognizable as songs, even with some repeating parts in it, any such structure seems to be missing from this new disc. Also, it has the effect of making me feel slightly sick when listening intently to it. I do seem to like it though, so I would advise anyone to take a listen to it.

On 3 to 7 October, the Dutch alternative radio station KinkFM [www.kinkfm.com], to celebrate their 10-year anniversary, will broadcast a chart show called the “Outlaw 666″, with the 666 best alternative songs of the last 10 years. On the website, you can pick your favorite 14 songs from a rather long list. It promises to become quite a neat list. Ateaseweb, a Radiohead fan website, already noted the remarkable fact that there are exactly 14 Radiohead songs to choose from:

On KinkFM.com you can find a shortlist of tracks you can choose from and vote for your 14 favourite tracks… easy questions… easy answers… there are 14 (!) Radiohead tracks shortlisted.

Even though I’m a pretty big Radiohead fan, the Top-14 I submitted is a bit different from this recommendation:

0. Radiohead – Paranoid Android (1997)
1. Muse – New Born (2001)
2. Kaiser Chiefs – Oh My God (2005)
3. Mars Volta – Inertiatic Esp (2003)
4. Bloodhound Gang – Fire Water Burn (1997)
5. Limp Bizkit – N 2 Gether Now (200)
6. Gorillaz – Clint Eastwood (2001)
7. Air – All I Need (1998)
8. Manic Street Preachers – If You Tolerate This (1998)
9. Fatboy Slim – Praise You (1999)
10. Mando Diao – Down In The Past (2005)
11. Datsuns – Motherfucker From Hell (2003)
12. Therapy? – Church Of Noise (1998)
13. Kings Of Leon – Four Kicks (2005)
Own choice: Radiohead – Polyethylene Part 1 & 2

Filling in the list did pose a bit of a difficulty though. Since, while browsing the shortlist, one cannot already say at which position in the Top-14 a song should be (because you don’t know how much better songs will follow), I ended up just adding songs at consequitive places in the list to sort it later, and when the list was full, just replacing the worst song in the list with a new one. Suppose in the end, one ends up with this list:

Air – All I Need (1998)
Bloodhound Gang – Fire Water Burn (1997)
Datsuns – Motherfucker From Hell (2003)
Fatboy Slim – Praise You (1999)
Gorillaz – Clint Eastwood (2001)
Kaiser Chiefs – Oh My God (2005)
Kings Of Leon – Four Kicks (2005)
Limp Bizkit – N 2 Gether Now (200)
Mando Diao – Down In The Past (2005)
Manic Street Preachers – If You Tolerate This (1998)
Mars Volta – Inertiatic Esp (2003)
Muse – New Born (2001)
Radiohead – Paranoid Android (1997)
Therapy? – Church Of Noise (1998)

How does one put the songs in the right order. Obviously, one would like to sort them, but how? The Kink FM forms only allows swapping two consequitive songs, as can be seen in the image:

So, if one only has this possibility, how can one sort the songs as quickly as possible? If possible, we would both like to minimize the number of times one have to ask himself the question “Which song is better, song A or song B?” (the number of comparisons), and clicking a button on the screen two swap two songs (the number of swaps).

The method I eventually used was the following:

• Look at the first song in the list
• Move all songs that are better than that song above it
• Repeat the process for the list of songs above the first song, and for the list of songs below the first song, until you are done

For example, say All I Need by Air was the first song in the list. Then I would place the 7 songs I liked better above it, leaving the other 6 songs below it. Then I would sort the songs 0-6, which would probably have Fire Water Burn as the first song, in the same way, and songs 8-13, with Motherfucker From Hell by the Datsuns as first song. And so on, and so on. This is actually a variation of what is known as quicksort. But is this the best method in our situation?

This is of course a specific case of the general theory of efficiency of sorting algorithms. This is quite an important topic in the Computer Science field, and much theory is available on it. Many sorting algorithms are discussed in this Wikipedia article. Here, the efficiency of sorting algorithm is given in the so-called “Big-Oh” notation. If a sorting algorithm is said to be O(n^2) (O of n squared), this means that if the number of items in a list is doubled, the time needed to sort it will quadruple (i.e., it increases quadratically). Similarly, if a sorting algorithm is O(n), if the number if items in a list is doubled, the time needed to sort it will double too. There is a theorem which states that a general sorting algorithm can never be better than O(n log n), which is somewhere between O(n) and O(n^2). There are several algorithms that are O(n log n), of which quicksort is usually the fastest.

This is all quite nice, but unfortunately, it doesn’t apply to our problem. In the theory on efficiency of sorting algorithms, it is assumed that swapping two arbitrary elements in a list always takes the same amount of time — i.e., it is O(1). But in our case, this is not true. Suppose we have a list [1 2 3 4 5], we could use the following 7 swap operations to get the 1 and the 5 swapped:

[1 2 3 4 5] -> [2 1 3 4 5] -> [2 3 1 4 5] -> [2 3 4 1 5] -> [2 3 4 5 1] -> [2 3 5 4 1] -> [2 5 3 4 1] -> [5 2 3 4 1]

Maybe we could do better, but we need at least 4 steps since the 1 needs to move 4 positions to the right. In contrast, swapping the 1 and 2 only takes one swap operation. In fact, swapping two arbitrary elements is O(n) since if the list doubles, the number of steps we need doubles, too.

So the question we actually want to answer, is: given only two operations on a list, which is comparing two arbitrary elements, and swapping two consequitive elements, which both take constant time (i.e., are O(1)), what is the fastest way to sort the list?

Now, surprisingly, there doesn’t seem to be an answer readily available to this question. This may be due to the fact that in practice, when one wants to sort a linked list, one first converts the linked list to an array, then sorts the array using a normal, efficient, sorting algorithm, and then converts the array back to a linked list. This is the approach that, for example, the Java Runtime Enviroment, use. Quoting from their documentation on the Collection class:

This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place.

So here it is claimed that in fact, any algorithm directly operating on a linked list, will be at least O(n^2 log n). This result seems to stem from the fact that swapping two arbitrary elements in a linked list takes O(n) rather than O(1) in the usual case, so any algorithm using swapping which is normally O(n log n) would become O(n^2 log n).

This cannot however be directly related to our question since a linked list has a set of operations different from our set, which only contains the swap oeration: in a linked list, one can add and remove entries in O(1), but access a random element in O(n). In our case, we can access random elements in O(1), but we cannot insert or remove elements at all. Do notice that swapping two consequitive elements in a linked list takes O(1) provided we have located the element.

Still, the O(n^2 log n) figure for linked lists mentioned in the Java documentation seems a bit strange if one considers Bubble Sort [http://en.wikipedia.org/wiki/Bubble_sort]: this algorithm iterates through all elements in the list, which is O(1) in a linked list, and swaps two consequitive elements, which is O(1), too. So, by the same analysis used to conclude that it is O(n^2) for normal lists, it should be O(n^2) for linked lists, too, which is better than O(n^2 log n).

And what’s more, the same goes in our case with consequitive swapping and comparing as the only operations: in total, O(n^2) consequitive swappings and O(n^2) comparisons are done, making it an O(n^2) algorithm. Which is quite nice, since, by the above reasoning, modifying an algorithm like quicksort to work in our case would make it O(n^2 log n).

But still, we ask ourselves, can we do better than O(n^2)? The answer is no, and it can be seen quite easily. Suppose we have a list which is completely in the wrong order, the swapping of elements alone will take O(n^2) steps. For example, sorting the list [5 4 3 2 1] to [1 2 3 4 5] could, in a naive implementation, be done like this:

       4        3      2    1 = 10 steps
5 | 5 5 5 1 | 1 1 1 | 1 1 | 1
4 | 4 4 1 5 | 5 5 2 | 2 2 | 2
3 | 3 1 4 4 | 4 2 5 | 3 5 | 4
2 | 1 3 3 3 | 2 4 4 | 3 5 | 4
1 | 2 2 2 2 | 3 3 3 | 4 4 | 5

This takes 4+3+2+1=10 steps (which is the sum of all numbers < n, which is n(n-1)/2=O(n^2). And what's more, a smarter implementation can't do much better. Call the "distance" between a list and its sorted version the number of steps each element needs to move to get to the right position. In the above example, the 5 would need to move 4 places down, the 4 needs to move 2 places down, the 2 needs to move 2 places up, and the 1 needs to move 4 places up, making the distance 4+4+2+2=12. One can easily see that in general, the distance is O(n^2). Now any swap of two consequitive elements, if both elements move in the right direction, can only decrease this distance by 2. Hence, the number of swaps needed is at least O(n^2) (and as we saw, we can do it in O(n^2)).

In conclusion, any sorting algorithm in our situation is at least O(n^2), and the bubble sort is O(n^2), hence it is, by a constant factor, the best sorting algorthm available in our situation. An added advantage is that while the quicksort algorithm require some book-keeping to remember what sublist we are actually sorting, this algorthm just works by repeatedly running over the list. Here’s how it works:

• For each song X, starting by the last one:
  • Start with the first song, and go down the list to song X, swapping songs that are wrongly ordered in relation to each other on the way

One final remark: all of the discussion above assumes that there actually is a decent total ordening of the songs in the list. However, when I tried to sort the same list according to my wishes using bubble sort, I got a different result from the one displayed above:

Radiohead – Paranoid Android (1997) / Bloodhound Gang – Fire Water Burn (1997) / Muse – New Born (2001) / Mars Volta – Inertiatic Esp (2003) / Limp Bizkit – N 2 Gether Now (200) / Air – All I Need (1998) / Kaiser Chiefs – Oh My God (2005) / Mando Diao – Down In The Past (2005) / Fatboy Slim – Praise You (1999) / Gorillaz – Clint Eastwood (2001) / Manic Street Preachers – If You Tolerate This (1998) / Datsuns – Motherfucker From Hell (2003) / Therapy? – Church Of Noise (1998) / Kings Of Leon – Four Kicks (2005)

Does this make this whole story useless? Why, no of course Oh, and I didn’t feel like making all O’s proportional, for which I apologize. — Meilof — meilof@gmail.com