Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
Please login if you are a repeated visitor or register for an (optional) free account first.

1. 比较与非比较策略，
   
2. 迭代与递归实现，
   
3. 分而治之范式（这个或这个），
   
4. 最佳/最差/平均情况时间复杂性分析，
   
5. 随机算法等

Pro-tip: Since you are not logged-in, you may be a first time visitor who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown] to advance to the next slide, [PageUp] to go back to the previous slide, [Esc] to toggle between this e-Lecture mode and exploration mode.

1. 在数组 A 中搜索特定值 v，
   
2. 查找（静态）数组 A 中的最小/最大/第 k 个最小/最大值，
   
3. 测试唯一性并删除数组 A 中的重复项，
   
4. 计算特定值 v 在数组 A 中出现多少次，
   
5. 设置数组 A 和另一个排序数组 B 之间的交集/联合，
   
6. 寻找一个目标对 x∈A 和 y∈A，使得 x + y 等于目标 z 等。
   

Another pro-tip: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2017). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.

1. 完全随机的
2. 随机排序（按升序/降序排列），
3. 随机但几乎排序（按升序/降序排列）或
   
4. 完全由你自己定义。
   

第二个操作是最重要的操作：通过单击“Sort”菜单然后单击“Go”执行主动排序算法。
请记住，您可以通过单击此可视化页面顶部的相应缩写来切换活动算法。
一些排序算法有一些额外的选项。 在点击“开始”之前，您可以根据需要切换选项。 例如，在冒泡排序（和归并排序）中，还可以选择计算输入数组的反向指数（这是一个高级主题）。

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

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

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

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.

You need to already understand/remember all these:
-. Logarithm and Exponentiation, e.g., log₂(1024) = 10, 2¹⁰ = 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-2¹¹)/(1-2) = 2047
-. Linear/Quadratic/Cubic function, e.g., f1(x) = x+2, f2(x) = x²+x-1, f3(x) = x³+2x²-x+7
-. Ceiling, Floor, and Absolute function, e.g., ceil(3.1) = 4, floor(3.1) = 3, abs(-7) = 7

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.

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|java|py.

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.

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|java|py 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 2n² + 100n operations to solve problem of size n.

If the time t needed for one operation is known, then we can state that algorithm X takes (2n² + 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 2n² + 100n to solving problem of size n.

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) = 2n² + 100n, we have:
f(1000) = 2*1000² + 100*1000 = 2.1M, vs
f(100000) = 2*100000² + 100*100000 = 20010M.
(notice that the lower order term 100n has lesser contribution).

Suppose two algorithms have 2n² and 30n² 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 n³, the difference in growth rate is a much more dominating factor.

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

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.

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).

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

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
Note that many others are not shown (also see the visualization in the next slide):
O(1)/constant time < O(log n)/logarithmic time < O(n)/linear time <
O(n log n)/quasilinear time < O(n²)/quadratic time < O(n³)/cubic time <
O(2ⁿ)/exponential time < O(n!)/also-exponential time < ...

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

1. 如果元素大小关系不正确，交换这两个数（在本例中为a> b），
   
2. 比较一对相邻元素（a，b），
   
3. 重复步骤1和2，直到我们到达数组的末尾（最后一对是第（N-2）和（N-1）项，因为我们的数组从零开始）
   
4. 到目前为止，最大的元素将在最后的位置。 然后我们将N减少1，并重复步骤1，直到N = 1。
   

比较和交换需要一个以常量为界的时间，我们称之为c。
（标准）Bubble Sort中有两个嵌套循环。
外循环正好运行N次迭代。 但内部循环运行变得越来越短：

1. 当 i = 0，（N-1）次迭代（比较和可能交换）时。
   
2. 当 i = 1，（N-2）次迭代时，...
   
3. 当 i =（N-2）时，1次迭代,
   
4. 当 i=（N-1），0迭代.

1. 在 [L ... N-1] 范围内找出最小项目 X 的位置，
   
2. 用第 L 项交换X，
   
3. 将下限 L 增加1并重复步骤1直到 L = N-2。
   

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(N²) — To be precise, it is similar to Bubble Sort analysis.

插入排序类似于大多数人安排扑克牌的方式。

1. 从你手中的一张牌开始，
   
2. 选择下一张卡并将其插入到正确的排序顺序中，
   
3. 对所有的卡重复上一步。
   

不用多说，让我们在小例子阵列[40,13,20,8]上尝试Insertion Sort。

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
  }
}

1. 在最好的情况下，数组已经排序并且（a [j]> X）总是为假所以不需要移位数据，并且内部循环运行在O（1），
   
2. 在最坏的情况下，数组被反向排序并且（a [j]> X）始终为真插入始终发生在数组的前端，并且内部循环以O（N）运行。
   

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

我们将在接下来的几张幻灯片中讨论两种（加一半）基于比较的排序算法：

1. 归并排序，
   
2. 快速排序和它的随机版本（只有一个变化）。
   

1. 将每对单个元素（默认情况下，已排序）归并为2个元素的有序数组，
   
2. 将2个元素的每对有序数组归并成4个元素的有序数组，重复这个过程......，
   
3. 最后一步：归并2个N / 2元素的排序数组（为了简化讨论，我们假设N是偶数）以获得完全排序的N个元素数组。

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]; // 讨论: 为什么我们需要一个临时的数组 b?
  int left = low, right = mid+1, bIdx = 0;
  while (left <= mid && right <= high) // 归并
    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
}

在示例数组[1,5,19,20,2,11,15,17]上尝试Merge Sort，其前半部分已经排序[1,5,19,20]，其下半部分也已经排序[2 ，11,15,17]。 专注于合并排序算法的最后一次合并。

1. 划分步骤：将大的原始问题划分成较小的子问题并递归地解决较小的子问题，
   
2. 解决步骤：结合较小的子问题的结果来产生较大的原始问题的结果。
   

归并并排序是分而治之的排序算法。
划分步骤很简单：将当前数组分成两半（如果N是偶数，则将其完全平等，或者如果N是奇数，则一边稍大于一个元素），然后递归地对这两半进行排序。
解决步骤是最有效的工作：使用 前面讨论的

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); // 解决: 归并子程序
  }
}

无论输入的原始顺序如何，归并排序中最重要的部分是其O（N log N）性能保证。 就这样，没有任何敌手测试用例可以使归并排序对于任何N个元素数组运行比O（N log N）更长的时间。
因此，归并排序非常适合分类非常大量的输入，因为O（N log N）比前面讨论的O（N²）排序算法增长得慢得多。
归并排序也是一个稳定的排序算法。 讨论：为什么？
然而，归并排序有几个不太好的部分。 首先，从零开始实施起来并不容易（但我们不必这样做）。 其次，它在归并操作期间需要额外的O（N）存储，因此不是真正的存储效率和不到位。顺便说一句，如果你有兴趣看看为解决这些（经典）归并排序不那么好的部分做了什么，你可以阅读这个。

快速排序是另一个分而治之排序算法（另一个在这个可视化页面中讨论的是归并排序）。
我们将看到，这种确定性的，非随机化的快速排序的版本可能在对手输入中具有O（N2）的很差的时间复杂度，之后再继续随机化的和可用的版本。

划分步骤：选择一个项目 p（称为枢轴点）然后将 a[i..j] 的项目分为三部分：a [i..m-1]，a [m] 和 a[m + 1..j]。 a [i..m-1]（可能为空）包含小于 p 的项目。 a [m] 是枢轴点 p，例如：指数 m 是已排序数组 a 的排序顺序中 p 的正确位置。 a [m + 1..j]（可能为空）包含大于或等于 p 的项目。 然后，递归地对这两部分进行排序。
解决步骤：不要惊讶......我们什么都不做！
如果您将其与归并排序进行比较，您会发现快速排序的 D＆C 步骤与归并排序完全相反。

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: Is it good to always put item(s) that is/are == p on S2 at all times?

int partition(int a[], int i, int j) {
  int p = a[i]; // p 是枢纽
  int m = i; // S1 和 S2 一开始是空的
  for (int k = i+1; k <= j; k++) { // 探索未知的区域
    if (a[k] < p) { // case 2
      m++;
      swap(a[k], a[m]); // C++ STL algorithm std::swap
    } // 注意：在情况1的时候我们什么不做: a[k] >= p
  }
  swap(a[i], a[m]); // 最后一步, 用a[m]交换枢纽
  return m; // 返回枢纽的指数, 用于快速排序（Quick Sort）
}

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); // 然后将右子阵列排序
  }
}

首先，我们分析跑一次分区的成本。
在内部分区（a，i，j）中，只有一个for循环遍历（j-i）次。 由于j可以和 N-1一样大，i 可以低至0，所以分区的时间复杂度是O（N）。
类似于归并排序分析，快速排序的时间复杂度取决于分区（a，i，j）被调用的次数。

在这种最坏情况的输入场景中，会发生以下情况：

当分区总是将数组分成两个相等的一半时，就会发生快速排序的最佳情况，如归并排序。
当发生这种情况时，递归的深度只有O（log N）。
由于每个级别进行O（N）比较，时间复杂度为O（N log N）。
在这个手工制作的示例输入数组[4,1,3,2,6,5,7]上尝试Quick Sort。 在实践中，这很少见，因此我们需要设计一个更好的方法：随机快速排序。

除了执行分区算法之外，它与快速排序相同，它随机选择 a[i..j] 之间的枢轴，而不是始终选择 a[i]（或 a[i..j]之间的任何其他固定索引）。
尝试Random Quick Sort这个大，但也有点随机的示例数组。
小练习：将上面的想法贯彻到本幻灯片中的实现中！

在接下来的幻灯片，我们将讨论两种不基于比较的排序算法:

1. 计数排序,
2. 基数排序.

这些排序算法可以通过不比较数组的项目来比时间复杂度为Ω（N log N）的基于比较的排序算法的下限更快。

我们都知道（在这个可视化中也没有证明，因为它需要花费一个小时的讲座来证明），所有基于比较的排序算法都具有Ω（N log N）的下限时间复杂度。
因此，任何具有最坏情况复杂度O（N log N）的基于比较的排序算法（如归并排序）都被认为是最优算法，即我们不能做得比这更好。
然而，如果存在输入数组的某些假设，我们可以避免比较这些项目来确定排序顺序， 然后实现更快的排序算法 - 比如在O（N）中

假设：如果要排序的项目是大范围但小数位的整数，我们可以将计数排序（Counting Sort）思想与基数排序（Radix Sort）结合起来，以实现线性时间复杂度。
在基数排序中，我们将每个项目排序为一个 w 数字串（如果需要，我们填充小于w数字的前几个零的整数）。
对于最低有效位（最右边）到最高有效位（最左边），我们通过 N 个项目并将它们按照活动数字放到10个队列中（每个数字[0..9]一个），就好像 一个修改的计数排序，因为这保留了稳定性。 然后我们再次重新连接组，以便进行后续迭代。
请尝试上面示例数组的Radix Sort来了解更清晰的解释。
请注意，我们只执行O（w×（N + k））次迭代。 在这个例子中，w = 4，k = 10。

如果排序算法在排序过程中仅需要恒定量（即，O（1））的额外空间，则称其为就地排序算法。就是这样，少量的额外变量的常量是可以的，但我们不允许具有可变长度的变量，这取决于输入大小N.
归并排序，由于其合并子例程需要额外的大小为N的临时数组，因此不在原位。
讨论：冒泡排序，选择排序，插入排序，快速排序（是否随机），计数排序和基数排序如何？哪些是就地？

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

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, std::stable_sort, or std::partial_sort in STL algorithm.
In Java, you can use Collections.sort.
In Python, you can use sort.
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.

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

Return to 'Exploration Mode' to start exploring!

Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.