Hello World serves two (and only two!) purposes:

    1. It's traditional
    2. It lets you check everything is working

QuickSort is neither traditional nor something a beginning programmer could use to check everything is working. Therefore it is not a substitute for Hello World.

- - -

If you want to get a feel for a language with one code snippet, allow me to introduce the Trabb-Pardo Knuth algorithm:

    In their 1977 work "The Early Development of Programming Languages",
    Trabb Pardo and Knuth introduced a trivial program which involved
    arrays, indexing, mathematical functions, subroutines, I/O,
    conditionals and iteration. They then wrote implementations of the
    algorithm in several early programming languages to show how such
    concepts were expressed.

    ask for 11 numbers to be read into a sequence S
    reverse sequence S
    for each item in sequence S
        do an operation
        if result overflows
            alert user
        else
            print result

It's not like the first thing you're going to do is write out all of quicksort to see if it's easy. You're going to fiddle with numbers an arrays a bit first, particularly if your language has some kind of interactive console. In fact, I wouldn't be surprised if the first thing you do in the language is actually 1+2.

There's quite a bit of syntax you need to learn before quicksort becomes a relevant test.

If you're looking for a good language to build a quick website backend in you probably don't even care about that, you'll care more about having nice ways of passing information around and checking that it has a decent inbuilt sort method.

For a novice programmer learning their first language, they probably don't understand the quicksort algo and probably have no concept of arrays or any data structure. Visually displaying "Hello World" is very simple and teaches you two basic parts of a language: - Syntax - Printing stuff

On another note, someone learning HTML for the first time will have no reason to do quicksort.

    qsort :: Ord a => [a] -> [a]
    qsort []     = []
    qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater
        where
                lesser = filter (< p) xs
                greater = filter (>= p) xs

I wish more Haskell proponents would spent less time showing off simple and elegant code, and more time showing fast and correct code.

It's pretty elegant, too, if less than the inefficient pseudo-qsort shown by the OP.

That means there is a lot of overhead for doing something simple like an in-place qsort that should be much faster than a mergesort.

I am at a loss on why the provided code is any more elegant than: http://en.literateprograms.org/Merge_sort_%28C_Plus_Plus%29

or this (also taken from rosetta code)?

  #include <iterator>
  #include <algorithm> // for std::partition
  #include <functional> // for std::less
  
  template<typename RandomAccessIterator,
           typename Order>
  void quicksort(RandomAccessIterator first, RandomAccessIterator last, Order order)
  {
    if (last - first > 1)
    {
      RandomAccessIterator split = std::partition(first+1, last, std::bind2nd(order, *first));
      std::iter_swap(first, split-1);
      quicksort(first, split-1, order);
      quicksort(split, last, order);
    }
  }

  template<typename RandomAccessIterator>
 void quicksort(RandomAccessIterator first, RandomAccessIterator last)
  {
    quicksort(first, last, std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
  }

Well, the problem not so much that there is a lot of overhead for doing an in-place qsort. The problem is that "in-place" anything is impossible in Haskell, it violates referential transparency.

Merge sort however needs no in-place update and can trivially (in Haskell world) be parallelized (merge sort is associative, you can use it as the reduce step of MapReduce). So you are correct in concluding that mergesort is used in Haskell.

You state "something simple like an in-place qsort", your statement about qsort being simple makes some assumptions about your programming languages world, which are not the same for all languages especially not Haskell. No whether all this is a pro and a con depends on what sort of coding you're doing of course.

I think that people call Haskell's code more elegant because they (like me) find C++ template and type annotations to be annoyingly verbose and messy for no good reason. For example for the two quicksort functions:

"template<typename RandomAccessIterator> void quicksort(RandomAccessIterator first, RandomAccessIterator last)"

vs

"quicksort :: (Ord a) => [a] -> [a]" (where "Ord a" means that a is an instance of the typeclass of ordered items).

There's a lot of infrastructure behind MapReduce and I bet you any implementation is going to have a lot more code in it than what is in Data.List.

Once things are in RAM (say, less than 1 GB), quicksort is the fastest algorithm (Edit: or some other optimized in-place variation on the theme such as introsort). You can parallelize across cores all you want but all that is going to do is crap up your caches and cause bus contention, making your code more complex and slower. The bottleneck is your databus not the CPU, after all what is the cost of a compare in clock cycles? This is also why mergesort is slower and parallelizing is not going to fix it.

If you want to see things that are parallelizable check out vectorizing libraries such as Thrust that run on massively parallel GPGPUs that have the bus design and RAM to handle that kind of parallelization. They are written in C++ and both the implementation and the code to use them looks almost the same like the code I posted. The compiler technology of other languages is years behind and currently can't even target these kinds of architectures.

I've seen GPU massive parallelization in Haskell and all it did was to generate C code and then invoke the CUDA compiler. This was in a research paper. In the meantime you can fire up nvcc with Thrust and sort bazillion of keys with less than 10 lines of code in C++ using a well-tested library.

Edit: BTW, anyone (and I really don't know who would be doing this) who is even thinking of running a MapReduce Haskell cluster must have lots of free time and $$$ to burn on wasted CPU cycles.

My point wasn't about using Haskell for high performance computing, my point was that Haskell's compiler can convert normal Haskell code to multicore code without (much, if any) work from the programmer. There is a large gap in between sequential single threaded program and a full MapReduce cluster and I think there is a significant amount of software written in this gap where Haskell-like languages could help with the parallelism/concurrency. The only reason I referenced MapReduce is since its a well known example even for people who are not well versed in functional programming (its a very common concept in functional programming).

And it is not true that in-place modification is not possible in Haskell. It is just not considered elegant, but it can be encapsulated in a perfectly Haskell-y way. (Hint: ST monad.)

Also I did not claim that my linked code is more elegant than some other code. Where did I make that claim? So I don't have to defend the claim I did not make, right?

EDIT: As a curious example, Clojure's sort function actually converts the sequence to a (Java) Array and calls java.util.Arrays.sort() on it, then turns it back into a sequence:

https://github.com/clojure/clojure/blob/b578c69d7480f621841e...

You can argue some older languages were written in a way in which it was (reasonably) easy to write a compiler that generates code with little performance overhead when compared to assembly (at worst a factor of 2 to 4, back in the 80s). Some popular languages keep adding abstractions and constructs that the compiler can actually deal with without some new compiler research breakthrough.

Yes; see also http://prog21.dadgum.com/40.html

It's nice he is into the C&C Portland Wiki, there's golden nuggets of wisdom everywhere. I am reposting the link from his blog. http://c2.com/cgi/wiki?SufficientlySmartCompiler

Personally of the higher-level languages, I found SBCL to be crazy good at optimizing, of course given a few nudges with a compiler directive or two. By inspecting the dissasembly, I could validate it was doing the "right-thing" (TM), but then again, I do the same to check the C/C++ compiled code.

Nice thought. What's the purpose of showing code which you won't be using in a real-world application? Making you think the language is more expressive than what it really is?

Many people say Haskell code is elegant and concise. Would this be the case if code we were shown would be real-world Haskell?

Here's a page with some actual haskell quicksorts:

http://www.haskell.org/haskellwiki/Introduction/Direct_Trans...

    qsort :: Ord a => [a] -> [a]
    qsort []     = []
    qsort [x]    = [x]
    qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater
        where
            (lesser, greater) = foldl split ([],[]) xs 
        where 
            split (left, right) x = if x<p then (left:x, right), else (left, right:x)

    split (left, right) x = if x<p then (x:left, right), else (left, x:right)

* especially with naive pivot from the middle of array

http://googleresearch.blogspot.com/2006/06/extra-extra-read-...

  program qsortTest;
  const N = 1000;
  var
    a: array [0..N] of integer;
    i: integer;

  procedure quicksort(var a: array of integer; l, r: integer);
  var
    i, j, temp: integer;
    pivot: integer;
  begin
    pivot := a[(l+r) div 2]; i := l; j := r;
    while i < j do 
    begin
      while a[i] < pivot do inc(i);
      while a[j] > pivot do dec(j);
      if i <= j then 
      begin
        temp := a[i];
        a[i] := a[j];
        a[j] := temp;
        inc(i); dec(j);
      end;
    end;
    if j > l then quicksort(a, l, j);
    if i < r then quicksort(a, i, r);
  end;

  begin
    { populating the array }
    for i := 0 to N do
      a[i] := random(N);
    writeln('initial array');
    for i := 0 to N do write(a[i]:6);
    writeln;
    quicksort(a, 0, N);

    writeln;
    writeln('sorted array');
    for i := 0 to N do write(a[i]:6);
    writeln;

  end.

If they iterate 'up to' then:

It would seem to me that on the initial call to 'quicksort' the '1000' gets passed in to 'r', the value of 'r' then gets passed in to 'j'.

Now if "'a[j]' < p" will refer to the uninitialized value in a[1000] and compare it to p, the first decrement will not take place, i<=j and now the code will swap with a[i] with a[1000].

This should cause the uninitialized value (0?) to end up as the first element in the sorted output array.

I hope I analyzed that correct, I don't have access to a pascal/delphi compiler here.

When you run your code do you see the output starting with a '0' element ?

Is there another element from the input array missing in the output ?

If pascal/delphi loops iterate up-to-and-including did you actually intend to sort an array of 1001 elements ?

Arrays boundaries are [0..N] -> [0..1000] (1001 element actually, sorry if that confused you).

[add]: I could rewrite it in C, it should be trivial bijection, I believe.

But please don't have the audacity of pointing out that original quicksort was supposed to be an efficient in place sort, not a mental exercise in beauty of a language. Then you get a Haskell version that is in place, and supposedly fast. It's about 10 lines longer than the C version, uses Monads, ST, recursion, "unsafeRead/Write", "rscan", "lscan", "swap", "sloop", etc., all together about 20 concepts, built-in functions, etc.

Also, of course, if it really should be fast, you have to use several compiler hints and macros to make it type specialize and all. Obviously.

The C version is shorter, uses nothing but array accesses, do/while, if, int comparisons, and recursion. If you want to explain the C version to a novice programmer, it will maybe take you half a day. The inplace Haskell version? Uhhh, yeah.

I can't help it, but things like these leave me with the impression of Haskell being a theoretically really nice language whose utility in actually getting things done seems somewhat questionable.

As far as familiarizing myself with a new language, I usually write a Hello World, then add some variables, and some functions or whatever is relevant, and just focus on the syntax of the language, or in the case of a platform or framework, take a look at building trivial components.

Not a language, but a platform example: I recently explored ExpressJS (If you're not familiar, its a framework for node.js web apps.) and my workflow was: Make a hello world server, Add a few routes and a static handler, Add some views, Add some middleware, Build it into a basic blog. (Because it's always a blog first, right?)

The whole process was quite quick and gave me a very strong jumping point for ExpressJS. Implementing quicksort or something similar as my first crack would probably have been pretty useless. So for me its all about context; I tend to start at Hello World and quickly grow something simple, but relevant to the language or platform.

And btw, here's the answer in F#:

  let rec qsort = function
       | [] -> []
       | x::xs -> let smaller,larger = List.partition (fun y -> y<=x) xs
                  qsort smaller @ [x] @ qsort larger

For example, is a quicksort 'in-place' if your memory gets swapped to disk?

   qsort (p:xs) = ...

Trying to come up with a single test that is good turns out to be surprisingly hard. In modern languages I'm looking for the ability to do clean functional code, stateful object code, async programming, a solid module system, and a type system that doesn't get in my way. I really can't imagine a single 5 line program that would encapsulate all of these areas.

Print the words

    hello, world

The C Programming Language [Kernighan, Ritchie]

Quicksort requires careful selection of pivots, and is unstable. (Many scripting languages (perl, python) are opting for stable sorts)

Check out Bentley&McIllroy's Engineering Quick Sort for a guide about the problems implementing a production ready quicksort.

If you're going to teach them something easy, simple and relatively hard to implement badly, teach them merge sort.

Then teach them adaptive merge sort.

1) how to write a program that guesses a number you thought of by doing binary search.

2) solve 2-queens

3) solve n-queens

4) solve knapsacking or some other combinatorial problem requiring memoization or DP. Of course, I wouldn't tell them any of those buzzwords that are meant to scare them away from just hacking on it.

Their mind will be blown regardless of the language they used and they'll get a feel for O() without even opening Cormen.

Quick sort means nothing to someone who does not yet grok compiling and output, much less sorting as an algorithmic process.

Question isn't whether "hello world" is obsolete, it's the level of knowledge of the author. A rank noob needs to see the simplest possible program, not the highest density functionality.

Gosu's example code does a good job at covering a lot of aspects in ~50 lines of code:

http://gosu-lang.org/intro.shtml