qsort([]) -> [];
qsort([Pivot|T]) ->
qsort([X || X <- T, X < Pivot]) ++ [Pivot] ++ qsort([X || X <- T, X >= Pivot]).
Here is some explanation of above code.
- When the input list is empty, output empty list.
- Otherwise, divide the input list into 2 lists such that, one list will have all the elements whose value are less than Pivot and the other list will have all the elements having values greater than or equal to Pivot. 1st element from input list is a Pivot.
- Do above steps recursively on all the lists that you create and then join them keeping Pivot in middle of lists.
I think the explanation is way too complicated than the code itself ;)
Day by day, I have started realizing the power of pattern matching, list data structure and functional programming.
Note: Above code is taken from Programming Erlang. Similar code is possible with other FP languages like haskell.
Enjoy!
