1x

Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.

🕑

1. 比较非比较的策略，
2. 迭代与递归实现，
3. 分治范式（例如，归并排序快速排序），
4. 最好/最坏/平均时间复杂度分析，
5. 随机算法等。

Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [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∈Ay∈A，使得 x + y 等于目标 z 等。
7. 计算在区间 [lo..hi] 内共计有多少个值。

Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). 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.

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, / to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.

🕑

🕑

1. 完全随机的
2. 随机但有序的（按升序/降序排列）
3. 随机但几乎有序的（按升序/降序排列）
4. 随机但包含许多重复项（因此在小范围的整数内）
5. 完全由你自己定义。

🕑

🕑

🕑

🕑

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

🕑

🕑

-. 对数和指数, e.g., log2(1024) = 10, 210 = 1024
-. 等差数列, e.g., 1+2+3+4+…+10 = 10*11/2 = 55
-. 等比数列, e.g., 1+2+4+8+..+1024 = 1*(1-211)/(1-2) = 2047
-. 线性/二次/三次函数, e.g., f1(x) = x+2, f2(x) = x2+x-1, f3(x) = x3+2x2-x+7
-. 向上取整 (ceiling), 向下取整 (floor) , 和绝对值 (absolute) 函数, e.g., ceil(3.1) = 4, floor(3.1) = 3, abs(-7) = 7

🕑

🕑

🕑

🕑

🕑

f(1000) = 2*10002 + 100*1000 = 2.1M，相比之下
f(100000) = 2*1000002 + 100*100000 = 20010M。
(注意，低阶项100n的贡献较小)。

🕑

🕑

🕑

🕑

O(1)/常数时间 < O(log n)/对数时间 < O(n)/线性时间 < O(n log n)/准线性时间 < O(n2)/二次时间 < O(n3)/三次时间 <
O(2n)/指数时间 < O(n!)/同样指数时间 < ∞ (如死循环).
🕑

🕑

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

🕑
`method bubbleSort(array A, integer N) // 标准版本  for each R from N-1 down to 1 // 重复 N-1 次迭代    for each index i in [0..R-1] // '未排序区域'，O(N)      if A[i] > A[i+1] // 这两个不是非递减顺序        swap(a[i], a[i+1]) // 在 O(1) 中交换它们`

1. 当 R=N-1 时，(N−1) 次迭代（比较和交换），
2. 当 R=N-2 时，(N−2) 次迭代，
...，
3. 当 R=1 时，1 次迭代（然后完成）。

🕑

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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

🕑
`method selectionSort(array A[], integer N)  for each L in [0..N-2] // O(N)    let X be the index of the minimum element in A[L..N-1] // O(N)    swap(A[X], A[L]) // O(1)，X 可能等于 L (没有实际交换)`

🕑

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

1
3
2
4

🕑

1. 手里只拿一张牌，
2. 拿下一张牌并将其插入到正确的排序位置，
3. 对所有牌重复上一步。

🕑
`method insertionSort(array A[], integer N)  for i in [1..N-1] // O(N)    let X be A[i] // X is the next item to be inserted into A[0..i-1]    for j from i-1 down to 0 // this loop can be fast or slow      if A[j] > X        A[j+1] = A[j] // make a place for X      else        break    A[j+1] = X // insert X at index j+1`

See the code shown in SortingDemo.cpp | py | java.

🕑

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

🕑

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

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

🕑

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

PS：尽管如此，非随机版本的快速排序（Quick Sort）需要 O(N2) 时间来运行
🕑

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

🕑

🕑
`method merge(array A, integer low, integer mid, integer high)  // 子数组1 = a[low..mid], 子数组2 = a[mid+1..high], 都已排序  int N = high-low+1  create array B of size N // 讨论：为什么我们需要一个临时数组b？  int left = low, right = mid+1, bIdx = 0  while (left <= mid && right <= high) // 合并过程    if (A[left] <= A[right])      B[bIdx++] = A[left++]     else      B[bIdx++] = A[right++]  while (left <= mid)    B[bIdx++] = A[left++] // 剩余部分，如果有的话  while (right <= high)    B[bIdx++] = A[right++] // 剩余部分，如果有的话  for (int k = 0; k < N; ++k)    A[low+k] = B[k]; // 复制回去`

🕑

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

🕑
`method mergeSort(array A, integer low, integer high)  // 要排序的数组是 A[low..high]  if (low < high) // 基本情况：low >= high (0 或 1 个项目)    int mid = (low+high) / 2	    mergeSort(a, low  , mid ) // 分成两半    mergeSort(a, mid+1, high) // 然后递归排序它们    merge(a, low, mid, high) // 征服：合并子程序`

🕑

🕑

🕑
🕑

...

🕑

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

🕑

A[i..m-1]（可能为空）包含小于（或等于）p的项目。
A[m] = p，即，索引m是数组a排序顺序中p的正确位置。
A[m+1..j]（可能为空）包含大于（或等于）p的项目。

🕑

1. S1 = A[i+1..m] 其中的项目 ≤ p
2. S2 = A[m+1..k-1] 其中的项目 ≥ p，和
3. 未知 = A[k..j]，其中的项目尚未被分配到S1S2

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

1. 如果 A[k] > p，将 A[k] 放入 S2
2. 如果 A[k] < p，将 A[k] 放入 S1
3. 如果 A[k] == p，抛一枚硬币，如果硬币正面/反面落地，分别将 A[k] 放入 S1/S2

🕑
🕑
🕑
`int partition(array A, integer i, integer j)  int p = a[i] // p 是枢轴  int m = i // S1 和 S2 最初为空  for (int k = i+1; k <= j; ++k) // 探索未知区域    if ((A[k] < p) || ((A[k] == p) && (rand()%2 == 0)))  { // 情况 2+3      ++m      swap(A[k], A[m]) // 交换这两个索引    // 注意我们在情况 1: A[k] > p 时不做任何事情  swap(A[i], A[m]) // 最后一步，交换枢轴和 a[m]  return m // 返回枢轴的索引`
🕑
`method quickSort(array A, integer low, integer 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); // 然后排序右子数组`

🕑

🕑

partition(A, i, j)中，只有一个for循环，它迭代了(j-i)次。由于j可以大到N-1，i可以小到0，所以partition的时间复杂度是O(N)。

🕑

🕑

...

🕑

🕑

🕑

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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

🕑

🕑

🕑

🕑

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

🕑

🕑

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

🕑

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

Bubble Sort
Merge Sort
Insertion Sort
Quick Sort (Deterministic)

🕑

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

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

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

🕑

🕑

Kattis - mjehuric
Kattis - sortofsorting，或者
Kattis - sidewayssorting

🕑

start of 3230 material

🕑

You have reached the last slide. 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.

🕑

0 1 2 3 4 5 6 7 8 9 A B C D E F

>
N =

Many Duplicates

A =

Set base

Set base

#### 关于

VisuAlgo最初由副教授Steven Halim于2011年构思，旨在通过提供自学、互动式学习平台，帮助学生更深入地理解数据结构和算法。

VisuAlgo涵盖了Steven Halim博士与Felix Halim博士、Suhendry Effendy博士合著的书《竞技编程》中讨论的许多高级算法。即使过去十年，VisuAlgo仍然是可视化和动画化这些复杂算法的独家平台。

VisuAlgo仍然在不断发展中，正在开发更复杂的可视化。目前，该平台拥有24个可视化模块。

VisuAlgo配备了内置的问题生成器和答案验证器，其“在线测验系统”使学生能够测试他们对基本数据结构和算法的理解。问题根据特定规则随机生成，并且学生提交答案后会自动得到评分。随着越来越多的计算机科学教师在全球范围内采用这种在线测验系统，它可以有效地消除许多大学标准计算机科学考试中手工基本数据结构和算法问题。通过给通过在线测验的学生分配一个小但非零的权重，计算机科学教师可以显著提高学生对这些基本概念的掌握程度，因为他们可以在参加在线测验之前立即验证几乎无限数量的练习题。每个VisuAlgo可视化模块现在都包含自己的在线测验组件。

VisuAlgo已经被翻译成三种主要语言：英语、中文和印尼语。此外，我们还用各种语言撰写了关于VisuAlgo的公开笔记，包括印尼语、韩语、越南语和泰语：

id, kr, vn, th.

#### 团队

Associate Professor Steven Halim, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Senior Software Engineer, Google (Mountain View)

CDTL TEG 1: Jul 2011-Apr 2012: Koh Zi Chun, Victor Loh Bo Huai

Jul 2012-Dec 2013: Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy
Jun 2013-Apr 2014 Rose Marie Tan Zhao Yun, Ivan Reinaldo

CDTL TEG 2: May 2014-Jul 2014: Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

Jun 2014-Apr 2015: Erin Teo Yi Ling, Wang Zi
Jun 2016-Dec 2017: Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir
Aug 2021-Apr 2023: Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long, Ting Xiao, Lim Dewen Aloysius

Optiver: Aug 2023-Oct 2023: Bui Hong Duc, Oleh Naver, Tay Ngan Lin

Aug 2023-Apr 2024: Xiong Jingya, Radian Krisno, Ng Wee Han

List of translators who have contributed ≥ 100 translations can be found at statistics page.

NUS教学与学习发展中心（CDTL）授予拨款以启动这个项目。在2023/24学年，Optiver的慷慨捐赠将被用来进一步开发 VisuAlgo。

#### 使用条款

VisuAlgo并不是一个完成的项目。Steven Halim副教授仍在积极改进VisuAlgo。如果您在使用VisuAlgo时发现任何可视化页面/在线测验工具中的错误，或者您想要请求新功能，请联系Steven Halim副教授。他的联系方式是将他的名字连接起来，然后加上gmail dot com。