Started with ReactiveCocoa, I stepped into the world of functional world. The paradigm of functional programming is not so easy to pick up, even for me, I started to program when I was an elementary school student. But after I looked into this deeper, I realize that the reason is because we were already used to think in an imperative way. In these three years, people in the industry start to utilize the power of functional programming. As one of them, I decide to write some thought down, to share my experience with you. Please don’t hesitate to give me any suggestions or corrections after reading this.
Some notice:
1. I’m going to write sample code with the syntax of JavaScript es6.
2. This is not an article for the beginner of JS.
3. Here is the Chinese version of this article.
So let’s start with short one. Today’s topic is Sort. You may think why sort? Isn’t there already a standard library that you can just invoke? Yes and no, although most of the cases, developers could use the built-in sort function. But in my opinion, sort is a function that can judge whether can a person do programming. Because we should already know how to sort numbers, right? And programming is just like telling the computer to do whatever you want it to do for you. So if one person could program sort function, then we know that he know exactly how to sort things, and can translate it to code. Sort is a relatively easy task, but also not that simple. Which is just in the right position. I’m going to introduce three kinds of sort algorithms starting with its concept and implementation and reveal the name later.
Try to think how do you sort! What will you do when you have hands of playing cards? I would pick the smallest cards 2s (for the Texas Hold’em Poker). After all 2s picked, go with 3s, then As are the final. Next, how to translate this procedure into code? Assume there is an array with length N. If we reuse this array in the middle of calculation, then the algorithm should be: focus on the first element, then compare others after current focused element, if the anyone smaller then the focused one, then swap them. After all elements are compared, the first element must be the smallest one. Repeat this process N times, then you’ll get the sorted array. This is the most intuitive sort algorithm came to my mind.
The second one: compare two adjacent elements, if the left one is larger, then swap. Repeat until no swap happens, then all done.
Next, the third one: first, pick the first element. Place it in the center, then check the rest elements, if the element is smaller, then the picked one, place to the left, else, to the right. Repeat this process until finish.
OK! Above are the three algorithms I want to discuss. Which one do you think is the easiest in your opinion?
Before introducing the formal names of these algorithms, let’s do a little comparison:
- For the first and second one, we need to declare the variables i and j. We also need to manage nested for loop including the edge cases of i and j. But you couldn’t see those in the third one.
- For the first and second one, we need to do swap. Some language has syntax that supports swap conveniently, but in javascript, you need to declare extra variable t. As 1. we don’t have this problem in the third one. Actually, I accidentally created a bug while implement this sample code.
- The third one used the function itself. Which as known as the recursive function. This didn’t appear in the previous algorithms. And I believe most of the developers were, to some degree, afraid of recursion when they were learning.
Let’s reveal the formal names of these algorithms in sequence:
- selection sort
- bubble sort
- quick sort
You may think: What!? Why is the quick sort so simple comparing to other implementations easily found by google? Well, the main reason for the complexity of other implementations is they try to optimize the memory usage. However, this is out of scope for this sort article. And some reader may argue that this is unfair to use filter, concat functions. But I would say most functional language support these. And I consider these functions as the fundamental infrastructure built into the language. So it doesn’t matter. Also, It’s not meaningful to discuss the fairness of different programming language.
Back to the topic: Functional. The reason of why the implementation of functional quick sort is so simple is because writing code in a declarative way: I want the smaller one go to the left, and larger one go to the right. And hand the rest tasks to computer. I’m not saying that we couldn’t implement selection sort or bubble sort in a functional way. But think twice, then you’ll know the most intuitive way to implement sort is the quick sort. And which, fortunately, in the most of the cases, is the fastest algorithm.
Well, this is the end of this article, I probably, maybe, perhaps will discuss the relation of DP and recursion.
UPDATE 2016/06/06: Fix bubble sort. Thanks to Chieh-Min Wang
