O'Reilly logo

Haskell Cookbook by Yogesh Sajanikar

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

How it works...

The crux of the preceding code lies in the following line:

    qsort ys ++ [x] ++ qsort zs

In the preceding statement, notice the following:

  • We choose the first element of the list, x as the pivot.
  • The list is then split into two parts ys and zs using the filter function.
  • ys is the list of elements less than x, and zs is the list of elements greater than or equal to x.
  • We recursively sort ys and zs, and combine the two parts and pivot to create a sorted list. We will use list concatenation (++) to do this.

At the outset, the implementation looks like an exact qsort. However, a closer look reveals that we use the filter function to partition the elements in the list. The filter function is an O(n) function. In the worst case, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required