排序算法

1. Introduction

Sorting is a very classic problem of reordering items (that can be compared, e.g., integers, floating-point numbers, strings, etc) of an array (or a list) in a certain order (increasing, non-decreasing (increasing or flat), decreasing, non-increasing (decreasing or flat), lexicographical, etc).


There are many different sorting algorithms, each has its own advantages and limitations.


Sorting is commonly used as the introductory problem in various Computer Science classes to showcase a range of algorithmic ideas.


Without loss of generality, we assume that we will sort only Integers, not necessarily distinct, in non-decreasing order in this visualization. Try clicking Bubble Sort for a sample animation of sorting the list of 5 jumbled integers (with duplicate) above.

1-1. 动机 - 有趣的计算机科学想法

Sorting problem has a variety of interesting algorithmic solutions that embody many Computer Science ideas:

  1. Comparison versus non-comparison based strategies,
  2. Iterative versus Recursive implementation,
  3. Divide-and-Conquer paradigm (e.g., Merge Sort or Quick Sort),
  4. Best/Worst/Average-case Time Complexity analysis,
  5. Randomized Algorithms, etc.

1-2. 动机 - 应用

When an (integer) array A is sorted, many problems involving A become easy (or easier):

  1. Searching for a specific value v in array A,
  2. Finding the min/max or the k-th smallest/largest value in (static) array A,
  3. Testing for uniqueness and deleting duplicates in array A,
  4. Counting how many time a specific value v appear in array A,
  5. Set intersection/union between array A and another sorted array B,
  6. Finding a target pair xA and yA such that x+y equals to a target z,
  7. Counting how many values in array A is inside range [lo..hi], etc.

Discussion: In real-life classes, the instructor may elaborate more on these applications.

1-3. Some Hints

[This is a hidden slide]

2. 动作

There are two actions that you can do in this visualization.

2-1. 定义你自己的输入

The first action is about defining your own input, an array/a list A that is:

  1. Totally random,
  2. Random but sorted (in non-increasing or non-decreasing order),
  3. Random but nearly sorted (in non-increasing or non-decreasing order),
  4. Random and contain many duplicates (thus small range of integers), or
  5. Defined solely by yourself.

In Exploration mode, you can experiment with various sorting algorithms provided in this visualization to figure out their best and worst case inputs.

2-2. 执行已选择的排序算法

The second action is the most important one: Execute the active sorting algorithm by clicking the "Sort" button.


Remember that you can switch active algorithm by clicking the respective abbreviation on the top side of this visualization page.

3. 可视化

View the visualisation/animation of the chosen sorting algorithm here.


Without loss of generality, we only show Integers in this visualization and our objective is to sort them from the initial state into non-decreasing order state. Remember, non-decreasing means mostly ascending (or increasing) order, but because there can be duplicates, there can be flat/equal line between two adjacent equal integers.

4. 常见的排序算法

At the top, you will see the list of commonly taught sorting algorithms in Computer Science classes. To activate each algorithm, select the abbreviation of respective algorithm name before clicking "Sort".


To facilitate more diversity, we randomize the active algorithm upon each page load.


The first six algorithms in this module are comparison-based sorting algorithms while the last two are not. We will discuss this idea midway through this e-Lecture.


The middle three algorithms are recursive sorting algorithms while the rest are usually implemented iteratively.

4-1. 缩写

为了节省屏幕空间,我们将算法名称缩写为三个字符:

  1. 基于比较的排序算法:
    1. BUB - 冒泡排序,
    2. SEL - 选择排序,
    3. INS - 插入排序,
    4. MER - 归并排序 (递归实现),
    5. QUI - 快速排序 (递归实现),
    6. R-Q - 随机快速排序 (递归实现).
  2. 不基于比较的排序算法:
    1. COU - 计数排序,
    2. RAD - 基数排序.

5. O(N^2) 基于比较的排序算法

在接下来的幻灯片,我们将讨论三种基于比较的排序算法

  1. 冒泡排序
  2. 选择排序
  3. 插入排序
它们被称为基于比较的比较,因为它们比较数组的元素对并决定是否交换它们。
这三种排序算法最容易实现,但不是最有效的,因为它们的时间复杂度是O(N2)。

6. Analysis of Algorithms (Basics)

Before we start with the discussion of various sorting algorithms, it may be a good idea to discuss the basics of asymptotic algorithm analysis, so that you can follow the discussions of the various O(N^2), O(N log N), and special O(N) sorting algorithms later.


This section can be skipped if you already know this topic.

6-1. Mathematical Pre-requisites

You need to already understand/remember all these:
-. Logarithm and Exponentiation, e.g., log2(1024) = 10, 210 = 1024
-. Arithmetic progression, e.g., 1+2+3+4+…+10 = 10*11/2 = 55
-. Geometric progression, e.g., 1+2+4+8+..+1024 = 1*(1-211)/(1-2) = 2047
-. Linear/Quadratic/Cubic function, e.g., f1(x) = x+2, f2(x) = x2+x-1, f3(x) = x3+2x2-x+7
-. Ceiling, Floor, and Absolute function, e.g., ceil(3.1) = 4, floor(3.1) = 3, abs(-7) = 7

6-2. What Is It?

Analysis of Algorithm is a process to evaluate rigorously the resources (time and space) needed by an algorithm and represent the result of the evaluation with a (simple) formula.


The time/space requirement of an algorithm is also called the time/space complexity of the algorithm, respectively.


For this module, we focus more on time requirement of various sorting algorithms.

6-3. Measuring the Actual Running Time?

We can measure the actual running time of a program by using wall clock time or by inserting timing-measurement code into our program, e.g., see the code shown in SpeedTest.cpp | py | java.


However, actual running time is not meaningful when comparing two algorithms as they are possibly coded in different languages, using different data sets, or running on different computers.

6-4. Counting # of Operations (1)

Instead of measuring the actual timing, we count the # of operations (arithmetic, assignment, comparison, etc). This is a way to assess its efficiency as an algorithm's execution time is correlated to the # of operations that it requires.


See the code shown in SpeedTest.cpp | py | java and the comments (especially on how to get the final value of variable counter).


Knowing the (precise) number of operations required by the algorithm, we can state something like this: Algorithm X takes 2n2 + 100n operations to solve problem of size n.

6-5. Counting # of Operations (2)

If the time t needed for one operation is known, then we can state that algorithm X takes (2n2 + 100n)t time units to solve problem of size n.


However, time t is dependent on the factors mentioned earlier, e.g., different languages, compilers and computers, etc.


Therefore, instead of tying the analysis to actual time t, we can state that algorithm X takes time that is proportional to 2n2 + 100n to solving problem of size n.

6-6. Asymptotic Analysis

Asymptotic analysis is an analysis of algorithms that focuses on analyzing problems of large input size n, considers only the leading term of the formula, and ignores the coefficient of the leading term.


We choose the leading term because the lower order terms contribute lesser to the overall cost as the input grows larger, e.g., for f(n) = 2n2 + 100n, we have:
f(1000) = 2*10002 + 100*1000 = 2.1M, vs
f(100000) = 2*1000002 + 100*100000 = 20010M.
(notice that the lower order term 100n has lesser contribution).

6-7. Ignoring Coefficient of the Leading Term

Suppose two algorithms have 2n2 and 30n2 as the leading terms, respectively.


Although actual time will be different due to the different constants, the growth rates of the running time are the same.


Compared with another algorithm with leading term of n3, the difference in growth rate is a much more dominating factor.


Hence, we can drop the coefficient of leading term when studying algorithm complexity.

6-8. Upper Bound: The Big-O Notation

If algorithm A requires time proportional to f(n), we say that algorithm A is of the order of f(n).


We write that algorithm A has time complexity of O(f(n)), where f(n) is the growth rate function for algorithm A.

6-9. Big-O Notation (Mathematics)

Mathematically, an algorithm A is of O(f(n)) if there exist a constant k and a positive integer n0 such that algorithm A requires no more than k*f(n) time units to solve a problem of size n ≥ n0, i.e., when the problem size is larger than n0 algorithm A is (always) bounded from above by this simple formula k*f(n).


Big-O Notation

Note that: n0 and k are not unique and there can be many possible valid f(n).

6-10. Growth Terms

In asymptotic analysis, a formula can be simplified to a single term with coefficient 1.


Such a term is called a growth term (rate of growth, order of growth, order of magnitude).


The most common growth terms can be ordered from fastest to slowest as follows:
O(1)/constant time < O(log n)/logarithmic time < O(n)/linear time <
O(n log n)/quasilinear time < O(n2)/quadratic time < O(n3)/cubic time <
O(2n)/exponential time < O(n!)/also-exponential time < ∞ (e.g., an infinite loop).


Note that a few other common time complexities are not shown (also see the visualization in the next slide).

6-11. Growth Terms (Visualized/Compared)

Common Growth Terms

We will see three different growth rates O(n2), O(n log n), and O(n) throughout the remainder of this sorting module.

7. 冒泡排序

Given an array of N elements, Bubble Sort will:

  1. Compare a pair of adjacent items (a, b),
  2. Swap that pair if the items are out of order (in this case, when a > b),
  3. Repeat Step 1 and 2 until we reach the end of array
    (the last pair is the (N-2)-th and (N-1)-th items as we use 0-based indexing),
  4. By now, the largest item will be at the last position.
    We then reduce N by 1 and repeat Step 1 until we have N = 1.

Without further ado, let's try Bubble Sort on the small example array [29, 10, 14, 37, 14].


You should see a 'bubble-like' animation if you imagine the larger items 'bubble up' (actually 'float to the right side of the array').

7-1. Bubble Sort, C++ Code & Analysis

void bubbleSort(int a[], int N) { // the standard version
for (; N > 0; --N) // N iterations
for (int i = 0; i < N-1; ++i) // except the last, O(N)
if (a[i] > a[i+1]) // not in non-decreasing order
swap(a[i], a[i+1]); // swap in O(1)
}

Comparison and swap require time that is bounded by a constant, let's call it c. Then, there are two nested loops in (the standard) Bubble Sort. The outer loop runs for exactly N iterations. But the inner loop runs get shorter and shorter:

  1. When i=0, (N−1) iterations (of comparisons and possibly swaps),
  2. When i=1, (N−2) iterations,
    ...,
  3. When i=(N−2), 1 iteration,
  4. When i=(N−1), 0 iteration.

Thus, the total number of iterations = (N−1)+(N−2)+...+1+0 = N*(N−1)/2 (derivation).

Total time = c*N*(N−1)/2 = O(N^2).

7-2. 冒泡排序:提前终止

Bubble Sort is actually inefficient with its O(N^2) time complexity. Imagine that we have N = 105 numbers. Even if our computer is super fast and can compute 108 operations in 1 second, Bubble Sort will need about 100 seconds to complete.


However, it can be terminated early, e.g. on the small sorted ascending example shown above [3, 6, 11, 25, 39], Bubble Sort can terminates in O(N) time.


The improvement idea is simple: If we go through the inner loop with no swapping at all, it means that the array is already sorted and we can stop Bubble Sort at that point.


Discussion: Although it makes Bubble Sort runs faster in general cases, this improvement idea does not change O(N^2) time complexity of Bubble Sort... Why?

7-3. 答案

[This is a hidden slide]

8. 选择排序

Given an array of N items and L = 0, Selection Sort will:

  1. Find the position X of the smallest item in the range of [L...N−1],
  2. Swap X-th item with the L-th item,
  3. Increase the lower-bound L by 1 and repeat Step 1 until L = N-2.

Let's try Selection Sort on the same small example array [29, 10, 14, 37, 13].


Without loss of generality, we can also implement Selection Sort in reverse:
Find the position of the largest item Y and swap it with the last item.

8-1. 选择排序:C++ 源代码 & 分析

void selectionSort(int a[], int N) {
for (int L = 0; L <= N-2; ++L) { // O(N)
int X = min_element(a+L, a+N) - a; // O(N)
swap(a[X], a[L]); // O(1), X may be equal to L (no actual swap)
}
}

Total: O(N2) — To be precise, it is similar to Bubble Sort analysis.

8-2. 小测验

Quiz: How many (real) swaps are required to sort [29, 10, 14, 37, 13] by Selection Sort?

3
2
1
4

9. 插入排序

Insertion sort is similar to how most people arrange a hand of poker cards. Poker hand

  1. Start with one card in your hand,
  2. Pick the next card and insert it into its proper sorted order,
  3. Repeat previous step for all cards.

Let's try Insertion Sort on the small example array [40, 13, 20, 8].

9-1. 插入排序,C++ 代码和分析 1

void insertionSort(int a[], int N) {
for (int i = 1; i < N; ++i) { // O(N)
int X = a[i]; // X is the item to be inserted
int j = i-1;
for (; j >= 0 && a[j] > X; --j) // can be fast or slow
a[j+1] = a[j]; // make a place for X
a[j+1] = X; // index j+1 is the insertion point
}
}

9-2. 插入排序:分析 2

外循环执行N-1次,这很明显。
但内循环执行的次数取决于输入:
  1. 在最好的情况下,数组已经排序并且(a [j]> X)总是为假所以不需要移位数据,并且内部循环运行在O(1),
  2. 在最坏的情况下,数组被反向排序并且(a [j]> X)始终为真插入始终发生在数组的前端,并且内部循环以O(N)运行。
因此,最佳情况时间是O(N × 1) = O(N,最坏情况时间是O(N × N) = O(N2).

9-3. 小测验

Quiz: What is the complexity of Insertion Sort on any input array?

O(1)
O(N log N)
O(N^2)
O(N)


Ask your instructor if you are not clear on this or read similar remarks on this slide.

10. 2.5 O(N log N)基于比较的排序

We will discuss two (and a half) comparison-based sorting algorithms soon:

  1. Merge Sort,
  2. Quick Sort and its Randomized version (which only has one change).

These sorting algorithms are usually implemented recursively, use Divide and Conquer problem solving paradigm, and run in O(N log N) time for Merge Sort and O(N log N) time in expectation for Randomized Quick Sort.


PS: The non-randomized version of Quick Sort runs in O(N2) though.

11. 归并排序

给定一个N个项目的数组,归并排序将:
  1. 将每对单个元素(默认情况下,已排序)归并为2个元素的有序数组,
  2. 将2个元素的每对有序数组归并成4个元素的有序数组,重复这个过程......,
  3. 最后一步:归并2个N / 2元素的排序数组(为了简化讨论,我们假设N是偶数)以获得完全排序的N个元素数组。
这只是一般的想法,在我们可以讨论归并排序的真正形式之前,我们需要更多的细节。

11-1. 重要的子程序,O(N)归并

We will dissect this Merge Sort algorithm by first discussing its most important sub-routine: The O(N) merge.


Given two sorted array, A and B, of size N1 and N2, we can efficiently merge them into one larger combined sorted array of size N = N1+N2, in O(N) time.


This is achieved by simply comparing the front of the two arrays and take the smaller of the two at all times. However, this simple but fast O(N) merge sub-routine will need additional array to do this merging correctly.

11-2. 归并子程序C ++实现方法

void merge(int a[], int low, int mid, int high) {
// subarray1 = a[low..mid], subarray2 = a[mid+1..high], both sorted
int N = high-low+1;
int b[N]; // discuss: why do we need a temporary array b?
int left = low, right = mid+1, bIdx = 0;
while (left <= mid && right <= high) // the merging
b[bIdx++] = (a[left] <= a[right]) ? a[left++] : a[right++];
while (left <= mid) b[bIdx++] = a[left++]; // leftover, if any
while (right <= high) b[bIdx++] = a[right++]; // leftover, if any
for (int k = 0; k < N; k++) a[low+k] = b[k]; // copy back
}

Try Merge Sort on the example array [1, 5, 19, 20, 2, 11, 15, 17] that have its first half already sorted [1, 5, 19, 20] and its second half also already sorted [2, 11, 15, 17]. Concentrate on the last merge of the Merge Sort algorithm.

11-3. 分而治之的范式

在我们继续之前,让我们先谈谈分而治之(Divide and Conquer,缩写为D&C),这是一个强大的解决问题的范例。
分而治之算法通过以下步骤解决(某种类型的)问题 - 比如我们的排序问题:
  1. 划分步骤:将大的原始问题划分成较小的子问题并递归地解决较小的子问题,
  2. 解决步骤:结合较小的子问题的结果来产生较大的原始问题的结果。

11-4. 归并排序是分而治之的算法

Merge Sort is a Divide and Conquer sorting algorithm.


The divide step is simple: Divide the current array into two halves (perfectly equal if N is even or one side is slightly greater by one element if N is odd) and then recursively sort the two halves.


The conquer step is the one that does the most work: Merge the two (sorted) halves to form a sorted array, using the merge sub-routine discussed earlier.

11-5. 归并排序的实现方法

void mergeSort(int a[], int low, int high) {
// 要排序的数组是 a[low..high]
if (low < high) { // base case: low >= high (0 or 1 item)
int mid = (low+high) / 2;
mergeSort(a, low , mid ); // 分成一半
mergeSort(a, mid+1, high); // 递归地将它们排序
merge(a, low, mid, high); // 解决: 归并子程序
}
}

11-6. 示范

Contrary to what many other CS printed textbooks usually show (as textbooks are static), the actual execution of Merge Sort does not split to two subarrays level by level, but it will recursively sort the left subarray first before dealing with the right subarray.


That's it, running Merge Sort on the example array [7, 2, 6, 3, 8, 4, 5], it will recurse to [7, 2, 6, 3], then [7, 2], then [7] (a single element, sorted by default), backtrack, recurse to [2] (sorted), backtrack, then finally merge [7, 2] into [2, 7], before it continue processing [6, 3] and so on.

11-7. 归并排序:第一部分 分析

在归并排序中,大部分工作是在解决/归并的步骤中完成的,因为分解步骤并没有真正执行任何操作(视为O(1))。
当我们称之为归并的(a,低,中,高)时候,我们处理k =(高 - 低+ 1)项。 最多会有 k-1 个比较。 从原始数组 a 到临时数组 b k 个移动,而另一个 k 移回。 总的来说,归并子例程内的操作次数 <3k-1 = O(k)。
重要的问题是这个归并子程序被调用了多少次?

11-8. 归并排序:第二部分 分析

The Recursion Tree of Merge Sort

11-9. 归并排序:第三部分 分析

Level 1: 2^0=1 calls to merge() with N/2^1 items each, O(2^0 x 2 x N/2^1) = O(N)
Level 2: 2^1=2 calls to merge() with N/2^2 items each, O(2^1 x 2 x N/2^2) = O(N)
Level 3: 2^2=4 calls to merge() with N/2^3 items each, O(2^2 x 2 x N/2^3) = O(N)
...
Level (log N): 2^(log N-1) (or N/2) calls to merge() with N/2^log N (or 1) item each, O(N)


There are log N levels and in each level, we perform O(N) work, thus the overall time complexity is O(N log N). We will later see that this is an optimal (comparison-based) sorting algorithm, i.e., we cannot do better than this.

11-10. 优缺点

The most important good part of Merge Sort is its O(N log N) performance guarantee, regardless of the original ordering of the input. That's it, there is no adversary test case that can make Merge Sort runs longer than O(N log N) for any array of N elements.


Merge Sort is therefore very suitable to sort extremely large number of inputs as O(N log N) grows much slower than the O(N2) sorting algorithms that we have discussed earlier.


There are however, several not-so-good parts of Merge Sort. First, it is actually not easy to implement from scratch (but we don't have to). Second, it requires additional O(N) storage during merging operation, thus not really memory efficient and not in-place. Btw, if you are interested to see what have been done to address these (classic) Merge Sort not-so-good parts, you can read this.


Merge Sort is also a stable sort algorithm. Discussion: Why?

11-11. The Answer

[This is a hidden slide]

12. 快速排序

Quick Sort is another Divide and Conquer sorting algorithm (the other one discussed in this visualization page is Merge Sort).


We will see that this deterministic, non randomized version of Quick Sort can have bad time complexity of O(N2) on adversary input before continuing with the randomized and usable version later.

12-1. 快速排序是分而治之的算法

Divide step: Choose an item p (known as the pivot)
Then partition the items of a[i..j] into three parts: a[i..m-1], a[m], and a[m+1..j].
a[i..m-1] (possibly empty) contains items that are smaller than (or equal to) p.
a[m] = p, i.e., index m is the correct position for p in the sorted order of array a.
a[m+1..j] (possibly empty) contains items that are greater than (or equal to) p.
Then, recursively sort the two parts.


Conquer step: Don't be surprised... We do nothing :O!


If you compare this with Merge Sort, you will see that Quick Sort D&C steps are totally opposite with Merge Sort.

12-2. 重要的子程序,O(N)分区

We will dissect this Quick Sort algorithm by first discussing its most important sub-routine: The O(N) partition (classic version).


To partition a[i..j], we first choose a[i] as the pivot p.

The remaining items (i.e., a[i+1..j]) are divided into 3 regions:

  1. S1 = a[i+1..m] where items are ≤ p,
  2. S2 = a[m+1..k-1] where items are ≥ p, and
  3. Unknown = a[k..j], where items are yet to be assigned to either S1 or S2.

Discussion: Why do we choose p = a[i]? Are there other choices?


Harder Discussion: If a[k] == p, should we put it in region S1 or S2?

12-3. 答案

[This is a hidden slide]

12-4. 分区排序 - 继续

Initially, both S1 and S2 regions are empty, i.e., all items excluding the designated pivot p are in the unknown region.


Then, for each item a[k] in the unknown region, we compare a[k] with p and decide one of the three cases:

  1. If a[k] > p, put a[k] into S2,
  2. If a[k] < p, put a[k] into S1,
  3. If a[k] == p, throw a coin and put a[k] into S1/S2 if it lands head/tail, respectively.

These three cases are elaborated in the next two slides.


Lastly, we swap a[i] and a[m] to put pivot p right in the middle of S1 and S2.

12-5. Partition - Case when a[k] > p

Case when a[k] ≥ p, increment k, extend S2 by 1 item

12-6. 分区排序 - 当  a[k] < p 的情况

Case when a[k] < p, increment m, swap a[k] with a[m], increment k, extend S1 by 1 item

12-7. 分区排序 C++ 实现方法

int partition(int a[], int i, int j) {
int p = a[i]; // p is the pivot
int m = i; // S1 and S2 are initially empty
for (int k = i+1; k <= j; ++k) { // explore the unknown region
if ((a[k] < p) || ((a[k] == p) && (rand()%2 == 0))) { // case 2+3
++m;
swap(a[k], a[m]); // C++ STL algorithm std::swap
} // notice that we do nothing in case 1: a[k] > p
}
swap(a[i], a[m]); // final step, swap pivot with a[m]
return m; // return the index of pivot
}

12-8. 快速排序 C++ 实现方法

void quickSort(int a[], int low, int high) {
if (low < high) {
int m = partition(a, low, high); // O(N)
// a[low..high] ~> a[low..m–1], pivot, a[m+1..high]
quickSort(a, low, m-1); // 递归地将左子阵列排序
// a[m] = pivot 在分区后就被排序好了
quickSort(a, m+1, high); // 然后将右子阵列排序
}
}

12-9. 示范

Try Quick Sort on example array [27, 38, 12, 39, 29, 16]. We shall elaborate the first partition step as follows:
We set p = a[0] = 27.
We set a[1] = 38 as part of S2 so S1 = {} and S2 = {38}.
We swap a[1] = 38 with a[2] = 12 so S1 = {12} and S2 = {38}.
We set a[3] = 39 and later a[4] = 29 as part of S2 so S1 = {12} and S2 = {38,39,29}.
We swap a[2] = 38 with a[5] = 16 so S1 = {12,16} and S2 = {39,29,38}.
We swap p = a[0] = 27 with a[2] = 16 so S1 = {16,12}, p = {27}, and S2 = {39,29,38}.


After this, a[2] = 27 is guaranteed to be sorted and now Quick Sort recursively sorts the left side a[0..1] first and later recursively sorts the right side a[3..5].

12-10. 快速排序:第一部分 分析

First, we analyze the cost of one call of partition.


Inside partition(a, i, j), there is only a single for-loop that iterates through (j-i) times. As j can be as big as N-1 and i can be as low as 0, then the time complexity of partition is O(N).


Similar to Merge Sort analysis, the time complexity of Quick Sort is then dependent on the number of times partition(a, i, j) is called.

12-11. 快速排序:第二部分 分析

When the array a is already in ascending order, e.g., a = [5, 18, 23, 39, 44, 50], Quick Sort will set p = a[0] = 5, and will return m = 0, thereby making S1 region empty and S2 region: Everything else other than the pivot (N-1 items).

12-12. 快速排序: 分析 第三部分

On such worst case input scenario, this is what happens:


Worst Case analysis of Quick Sort

The first partition takes O(N) time, splits a into 0, 1, N-1 items, then recurse right.
The second one takes O(N-1) time, splits a into 0, 1, N-2 items, then recurse right again.
...
Until the last, N-th partition splits a into 0, 1, 1 item, and Quick Sort recursion stops.


This is the classic N+(N-1)+(N-2)+...+1 pattern, which is O(N2), similar analysis as the one in this Bubble Sort analysis slide...

12-13. 快速排序:最好的情况(极少)

The best case scenario of Quick Sort occurs when partition always splits the array into two equal halves, like Merge Sort.


When that happens, the depth of recursion is only O(log N).


As each level takes O(N) comparisons, the time complexity is O(N log N).


Try Quick Sort on this hand-crafted example input array [4, 1, 3, 2, 6, 5, 7].
In practice, this is rare, thus we need to devise a better way: Randomized Quick Sort.

13. 随机快速排序

Same as Quick Sort except just before executing the partition algorithm, it randomly select the pivot between a[i..j] instead of always choosing a[i] (or any other fixed index between [i..j]) deterministically.


Mini exercise: Implement the idea above to the implementation shown in this slide!


Running Random Quick Sort on this large and somewhat random example array a = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48] feels fast.

13-1. 魔法般的分析

It will take about 1 hour lecture to properly explain why this randomized version of Quick Sort has expected time complexity of O(N log N) on any input array of N elements.


In this e-Lecture, we will assume that it is true.


If you need non formal explanation: Just imagine that on randomized version of Quick Sort that randomizes the pivot selection, we will not always get extremely bad split of 0 (empty), 1 (pivot), and N-1 other items. This combination of lucky (half-pivot-half), somewhat lucky, somewhat unlucky, and extremely unlucky (empty, pivot, the rest) yields an average time complexity of O(N log N).


Discussion: For the implementation of Partition, what happen if a[k] == p, we always put a[k] on either side (S1 or S2) deterministically?

13-2. The Answer

[This is a hidden slide]

14. O(N) 不基于比较的排序算法

We will discuss two non comparison-based sorting algorithms in the next few slides:

  1. Counting Sort,
  2. Radix Sort.

These sorting algorithms can be faster than the lower bound of comparison-based sorting algorithm of Ω(N log N) by not comparing the items of the array.

14-1. 排序算法的下限

It is known (also not proven in this visualization as it will take another 1 hour lecture to do so) that all comparison-based sorting algorithms have a lower bound time complexity of Ω(N log N).


Thus, any comparison-based sorting algorithm with worst-case complexity O(N log N), like Merge Sort is considered an optimal algorithm, i.e., we cannot do better than that.


However, we can achieve faster sorting algorithm — i.e., in O(N) — if certain assumptions of the input array exist and thus we can avoid comparing the items to determine the sorted order.

15. 计数排序

假设:如果要排序的项目是小范围的整数,我们可以计算每个整数(在这个小范围内)的出现频率,然后通过循环该小范围来按排序顺序输出项目。
在上面的示例数组中,对所有整数都在[1..9]内的示例数组尝试Counting Sort,因此我们只需要计算整数1出现的次数,出现整数2,...,出现整数9,然后遍历 如果频率 [y] = x,则 1至9 打印出整数 y x 个副本。
时间复杂度为O(N)来计算频率,O(N + k)以排序顺序输出结果,其中 k 是输入的整数范围,在本例中为9-1 + 1 = 9。 计数排序(Counting Sort)的时间复杂度为O(N + k),如果 k 很小,那么它就是O(N)。
由于内存限制,当 k 相对较大时,我们将无法执行计数排序(Counting Sort)的计数部分,因为我们需要存储那些 k 个整数出现的次数。

16. 基数排序

Assumption: If the items to be sorted are Integers with large range but of few digits, we can combine Counting Sort idea with Radix Sort to achieve the linear time complexity.


In Radix Sort, we treat each item to be sorted as a string of w digits (we pad Integers that have less than w digits with leading zeroes if necessary).


For the least significant (rightmost) digit to the most significant digit (leftmost), we pass through the N items and put them according to the active digit into 10 Queues (one for each digit [0..9]), which is like a modified Counting Sort as this one preserves stability. Then we re-concatenate the groups again for subsequent iteration.


Try Radix Sort on the example array above for clearer explanation.


Notice that we only perform O(w × (N+k)) iterations. In this example, w = 4 and k = 10.

16-1. 最好的排序整数的算法?

Now, having discussed about Radix Sort, should we use it for every sorting situation?


For example, it should be theoretically faster to sort many (N is very large) 32-bit signed integers as w ≤ 10 digits and k = 10 if we interpret those 32-bit signed integers in Decimal. O(10 × (N+10)) = O(N).

16-2. The Answer

[This is a hidden slide]

17. 排序算法的附加属性

除了比较还是非比较,递归或迭代之外,还有其他一些属性可用于区分排序算法。
在本节中,我们将讨论就地与非就地,稳定与不稳定以及高速缓存排序算法的性能。

17-1. 就地排序

A sorting algorithm is said to be an in-place sorting algorithm if it requires only a constant amount (i.e. O(1)) of extra space during the sorting process. That's it, a few, constant number of extra variables is OK but we are not allowed to have variables that has variable length depending on the input size N.


Merge Sort (the classic version), due to its merge sub-routine that requires additional temporary array of size N, is not in-place.


Discussion: How about Bubble Sort, Selection Sort, Insertion Sort, Quick Sort (randomized or not), Counting Sort, and Radix Sort. Which ones are in-place?

17-2. 稳定排序

如果在执行排序后算法保留具有相同键值的元素的相对顺序,则这个排序算法称为稳定的排序。
稳定排序的示例应用:假设我们有按字母顺序排序的学生姓名。 现在,如果此列表按教程组号重新排序(回想一个教程组通常有许多学生),稳定的排序算法会确保同一教程组中的所有学生仍按字母顺序显示其名称。
讨论:在这里讨论过的排序算法中哪些是稳定的?
尝试排序数组A = {3, 4a, 2, 4b, 1}进行排序,即有两个4(4a先,然后4b)的副本。

17-3. 缓存性能

[This is a hidden slide]

18. 小测验

小测验时间!

18-1. 小测验 #3

Quiz: Which of these algorithms run in O(N log N) on any input array of size N?

Merge Sort
Insertion Sort
Bubble Sort
Quick Sort (Deterministic)

18-2. 小测验 #2

Quiz: Which of these algorithms has worst case time complexity of Θ(N^2) for sorting N integers?

Selection Sort
Merge Sort
Radix Sort
Bubble Sort
Insertion Sort
Θ是一个紧密的时间复杂度分析,其中最佳情况Ω和最坏情况的big-O 分析互相匹配。

19. 附加功能

我们已经到了最后的排序的电子讲座。
但是,VisuAlgo中还有另外两种嵌入在其他数据结构中的排序算法:堆排序平衡BST排序。 我们将在这两个数据结构的电子讲座里面讨论它们。

19-1. 挑战

[This is a hidden slide]

19-2. 反向指数/计数

[This is a hidden slide]

19-3. 实现方法

Actually, the C++ source code for many of these basic sorting algorithms are already scattered throughout these e-Lecture slides. For other programming languages, you can translate the given C++ source code to the other programming language.


Usually, sorting is just a small part in problem solving process and nowadays, most of programming languages have their own sorting functions so we don't really have to re-code them unless absolutely necessary.


In C++, you can use std::sort (most likely a hybrid sorting algorithm: Introsort), std::stable_sort (most likely Merge Sort), or std::partial_sort (most likely Binary Heap) in STL algorithm.
In Java, you can use Collections.sort.
In Python, you can use sort (most likely a hybrid sorting algorithm: Timsort).
In OCaml, you can use List.sort compare list_name.


If the comparison function is problem-specific, we may need to supply additional comparison function to those built-in sorting routines.

19-4. 在线测试

Now it is time for you to see if you have understand the basics of various sorting algorithms discussed so far.


Test your understanding here!

19-5. 在线评估测试

现在您已经到了电子讲座的最后部分,您认为排序问题与调用内置排序例程一样简单吗?
尝试这些在线评判问题以了解更多信息:
Kattis - mjehuric
Kattis - sortofsorting,或者
Kattis - sidewayssorting
这不是排序算法的最后部分。 当您在VisuAlgo中探索其他主题时,您会意识到排序是许多其他高难度问题的高级算法的预处理步骤,例如, 作为克鲁斯卡尔算法(Kruskal's algorithm)的预处理步骤,创造性地用于后缀数组(Suffix Array )数据结构等。