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.

🕑

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.

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, vs
f(100000) = 2*1000002 + 100*100000 = 20010M。

🕑

🕑

🕑

🕑

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

🕑
`void bubbleSort(int a[], int N) { // 标准版本  for (; N > 0; --N) // N次迭代    for (int i = 0; i < N-1; ++i) // 除最后一次, O(N)      if (a[i] > a[i+1]) // 若数组元素i和i+1成非递减次序        swap(a[i], a[i+1]); // 在O(1)时间内交换}`

（标准）冒泡排序中有两个嵌套循环。

1. 当 i = 0，内循环进行N-1次比较和交换的迭代；
2. 当 i = 1，N-2次迭代；
3. 当 i = N-2 时，1次迭代；
4. 当 i = N-1 时，0次迭代。

🕑

🕑

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

🕑
`void selectionSort(int a[], int N) {  for (int L = 0; L <= N-2; L++) { // O(N)    找到[L,N-1]区间的最小的数的序号X // O(N)    swap(X, L) // O(1), 注意X可能等于L（没有交换）  }}`

🕑

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

1
3
4
2

🕑

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

🕑
`void insertionSort(int a[], int N) { //插入排序  for (int i = 1; i < N; i++) { // O(N)    X = a[i]; // X 是要被插入的那个数    for (j = i-1; j >= 0 && a[j] > X; j--) // 速度有快有慢      a[j+1] = a[j]; // 为 X 腾出一个空间    a[j+1] = X; // 此处为插入点  }}`
🕑

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^2)
O(N log N)
O(N)
O(1)

🕑

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

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

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. 划分步骤：将大的原始问题划分成较小的子问题并递归地解决较小的子问题，
2. 解决步骤：结合较小的子问题的结果来解决较大的原始问题。
🕑

🕑
`void mergeSort(int a[], int low, int 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.

🕑

🕑

🕑

1. S1 = a [i + 1..m]其中项目 ≤ p
2. S2 = a [m + 1..k-1]，其中项目 ≥ p，且
3. 未知的= a [k..j]，其中项目尚未分配给 S1 S2

🕑

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] 放入 S2 还是 S1 中。

🕑
🕑
🕑
`int partition(int a[], int i, int j) {  int p = a[i]; // p 是 pivot  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]交换 pivot  return m; // 返回pivot的索引, 用于快速排序（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); // 然后将右侧子数列排序  }}`
🕑

🕑

🕑

🕑

...

🕑

🕑

🕑

🕑

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?

Insertion Sort
Bubble Sort
Quick Sort (Deterministic)
Merge Sort

🕑

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

Insertion Sort
Selection Sort
Merge Sort
Bubble 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

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

>

Many Duplicates

A =

We use cookies to improve our website.
By clicking ACCEPT, you agree to our use of Google Analytics for analysing user behaviour and improving user experience as described in our Privacy Policy.
By clicking reject, only cookies necessary for site functions will be used.

#### 关于

VisuAlgo于2011年由Steven Halim博士创建，是一个允许学生以自己的速度自学基础知识，从而更好地学习数据结构与算法的工具。
VisuAlgo包含许多高级算法，这些算法在Steven Halim博士的书（“Competitive Programming”，与他的兄弟Felix Halim博士合作）和其他书中有讨论。今天，一些高级算法的可视化/动画只能在VisuAlgo中找到。

VisuAlgo不是从一开始就设计为在小触摸屏（例如智能手机）上工作良好，因为为了满足许多复杂算法可视化，需要大量的像素和点击并拖动手势进行交互。为得到良好的用户体验，最低屏幕分辨率应为1024x768，并且本网站只有首页相对适合移动设备。但是，我们正在测试一个准备在2022年4月发布的移动版本。
VisuAlgo是一个正在进行的项目，更复杂的可视化仍在开发中。

VisuAlgo支持三种语言：英语，中文，印尼语。目前，我们还以各种语言写了有关VisuAlgo的公共注释：
id, kr, vn, th.

#### 团队

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

Koh Zi Chun, Victor Loh Bo Huai

Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy

Rose Marie Tan Zhao Yun, Ivan Reinaldo

Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

Erin Teo Yi Ling, Wang Zi

Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir

Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long

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

#### 使用条款

VisuAlgo is free of charge for Computer Science community on earth. If you like VisuAlgo, the only "payment" that we ask of you is for you to tell the existence of VisuAlgo to other Computer Science students/instructors that you know =) via Facebook/Twitter/Instagram/TikTok posts, course webpages, blog reviews, emails, etc.

If you are a data structure and algorithm student/instructor, you are allowed to use this website directly for your classes. If you take screen shots (videos) from this website, you can use the screen shots (videos) elsewhere as long as you cite the URL of this website (https://visualgo.net) and/or list of publications below as reference. However, you are NOT allowed to download VisuAlgo (client-side) files and host it on your own website as it is plagiarism. As of now, we do NOT allow other people to fork this project and create variants of VisuAlgo. Using the offline copy of (client-side) VisuAlgo for your personal usage is fine.

Note that VisuAlgo's online quiz component is by nature has heavy server-side component and there is no easy way to save the server-side scripts and databases locally. Currently, the general public can only use the 'training mode' to access these online quiz system. Currently the 'test mode' is a more controlled environment for using these randomly generated questions and automatic verification for real examinations in NUS.

List of Publications

This work has been presented briefly at the CLI Workshop at the ICPC World Finals 2012 (Poland, Warsaw) and at the IOI Conference at IOI 2012 (Sirmione-Montichiari, Italy). You can click this link to read our 2012 paper about this system (it was not yet called VisuAlgo back in 2012) and this link for the short update in 2015 (to link VisuAlgo name with the previous project).

This work is done mostly by my past students.

Bug Reports or Request for New Features

VisuAlgo is not a finished project. Dr Steven Halim is still actively improving VisuAlgo. If you are using VisuAlgo and spot a bug in any of our visualization page/online quiz tool or if you want to request for new features, please contact Dr Steven Halim. His contact is the concatenation of his name and add gmail dot com.

#### 隐私政策

Version 1.1 (Updated Fri, 14 Jan 2022).

Disclosure to all visitors: We currently use Google Analytics to get an overview understanding of our site visitors. We now give option for user to Accept or Reject this tracker.

Since Wed, 22 Dec 2021, only National University of Singapore (NUS) staffs/students and approved CS lecturers outside of NUS who have written a request to Steven can login to VisuAlgo, anyone else in the world will have to use VisuAlgo as an anonymous user that is not really trackable other than what are tracked by Google Analytics.

For other NUS students, you can self-register a VisuAlgo account by yourself (OPT-IN).

For other CS lecturers worldwide who have written to Steven, a VisuAlgo account (your (non-NUS) email address, you can use any display name, and encrypted password) is needed to distinguish your online credential versus the rest of the world. Your account will be tracked similarly as a normal NUS student account above but it will have CS lecturer specific features, namely the ability to see the hidden slides that contain (interesting) answers to the questions presented in the preceding slides before the hidden slides. You can also access Hard setting of the VisuAlgo Online Quizzes. You can freely use the material to enhance your data structures and algorithm classes. Note that there can be other CS lecturer specific features in the future.

For anyone with VisuAlgo account, you can remove your own account by yourself should you wish to no longer be associated with VisuAlgo tool.