Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Quicksort is the new Hello World

blog.rmontanaro.com

Post reply on HN
Print view View original

31–40 of 64 posts

Re: Quicksort is the new Hello World

#31

Post by amalcon »

l0stman wrote: post #9

qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater where lesser = filter ( = p) xs I know nothing about Haskell but I don't think this code implements the original quicksort algorithm which sorts the input in-place. Moreover the two-pass of filter over the list and the concatenations cause unnecessary overhead. Thus, even if the sample code is simple and elegant, a real-wor…

It would be pretty difficult to write an in-place sort in Haskell, given that it only has mutable state through monads (and I doubt anyone wants to go into a monad just to sort something). GHC is pretty good at optimizing list concatenations, so that's probably not a big deal either. You're absolutely right about the two-pass filter, though.

Re: Quicksort is the new Hello World

#32

Post by alextgordon »

This article is misguided.

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

    1. It's traditional
    2. It lets you check everything is working
It isn't a way to evaluate or compare languages. How could it be? It only uses a very small fraction of the language. Note that the Hello World for C is rather long and inelegant. But C itself is definitely an elegant language. So its predictive power is poor.

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.
http://en.wikipedia.org/wiki/Trabb_Pardo%E2%80%93Knuth_algor...

    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

Re: Quicksort is the new Hello World

#35

Post by _tef »

It is like fizzbuzz/binary search in that most people think they can write it and they get it wrong.

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.

Re: Quicksort is the new Hello World

#38

Post by DanielBMarkham »

Yet another article that completely misses the point. The point of "Hello World" is to show a noob how to fire up the editor, compile, and see something happen.

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

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

Re: Quicksort is the new Hello World

#39

Post by pauljonas »

The only way to learn a new programming language is by writing programs in it. The first program to write is the same for all languages:

Print the words

    hello, world
This is a bug hurdle; to leap over it you have to be able to create the program text somewhere, compile it successfully, load it, run it, and find out where your output went. With these mechanical details mastered, everything else is comparatively easy.

The C Programming Language [Kernighan, Ritchie]

Re: Quicksort is the new Hello World

#40

Post by ctdonath »

gsivil wrote: post #2

I think your point is valid and of course interesting for programmers, but KR's "Hello, world!" is still relevant for students and novices. Maybe reading/writing on a file would be more useful nowadays, since it does not demand knowledge of algorithms.

It is very relevant for total novices. When someone has no concept about programming, this is the fastest way to "here are the barest basics, and you have already written a program."

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.

Post reply on HN