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

🕑

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. 基数排序.

🕑

It is known (also not proven in this visualization as it will take about half-an-hour lecture about decision tree model 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.

🕑

Assumption: If the items to be sorted are Integers with small range, we can count the frequency of occurrence of each Integer (in that small range) and then loop through that small range to output the items in sorted order.

Try Counting Sort on the example array above where all Integers are within [1..9], thus we just need to count how many times Integer 1 appears, Integer 2 appears, ..., Integer 9 appears, and then loop through 1 to 9 to print out x copies of Integer y if frequency[y] = x.

The time complexity is O(N) to count the frequencies and O(N+k) to print out the output in sorted order where k is the range of the input Integers, which is 9-1+1 = 9 in this example. The time complexity of Counting Sort is thus O(N+k), which is O(N) if k is small.

We will not be able to do the counting part of Counting Sort when k is relatively big due to memory limitation, as we need to store frequencies of those k integers.

PS: This version of Counting Sort is not stable, as it does not actually remember the (input) ordering of duplicate integers. The version presented in CLRS is stable, but is a bit more complex than this form.

🕑

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 (remember, the Counting Sort version shown in this slide earlier is not a stable sort). Then we re-concatenate the groups again for subsequent iteration.

Try Radix Sort on the random 4-digits array above for clearer explanation.

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

🕑

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

Discussion: Using base-10 as shown in this visualization is actually not the best way to sort N 32-bit signed integers. What should be the better setup?

🕑

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 sorting algorithm is called stable if the relative order of elements with the same key value is preserved by the algorithm after sorting is performed.

Example application of stable sort: Assume that we have student names that have been sorted in alphabetical order. Now, if this list is sorted again by tutorial group number (recall that one tutorial group usually has many students), a stable sort algorithm would ensure that all students in the same tutorial group still appear in alphabetical order of their names. Radix sort that goes through multiple round of sorts digit-by-digit requires a stable sort sub-routine for it to work correctly.

Discussion: Which of the sorting algorithms discussed in this e-Lecture are stable?
Try sorting array A = {3, 4a, 2, 4b, 1}, i.e. there are two copies of 4 (4a first, then 4b).

🕑

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
Quick Sort (Deterministic)
Merge Sort
Insertion Sort

🕑

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

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

Change Scale

>

Many Duplicates

A =

Default

Compact

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.

#### 关于

Initially conceived in 2011 by Dr. Steven Halim, VisuAlgo aimed to facilitate a deeper understanding of data structures and algorithms for his students by providing a self-paced, interactive learning platform.

Featuring numerous advanced algorithms discussed in Dr. Steven Halim's book, 'Competitive Programming' — co-authored with Dr. Felix Halim and Dr. Suhendry Effendy — VisuAlgo remains the exclusive platform for visualizing and animating several of these complex algorithms even after a decade.

While primarily designed for National University of Singapore (NUS) students enrolled in various data structure and algorithm courses (e.g., CS1010/equivalent, CS2040/equivalent (including IT5003), CS3230, CS3233, and CS4234), VisuAlgo also serves as a valuable resource for inquisitive minds worldwide, promoting online learning.

Initially, VisuAlgo was not designed for small touch screens like smartphones, as intricate algorithm visualizations required substantial pixel space and click-and-drag interactions. For an optimal user experience, a minimum screen resolution of 1366x768 is recommended. However, since April 2022, a mobile (lite) version of VisuAlgo has been made available, making it possible to use a subset of VisuAlgo features on smartphone screens.

VisuAlgo remains a work in progress, with the ongoing development of more complex visualizations. At present, the platform features 24 visualization modules.

Equipped with a built-in question generator and answer verifier, VisuAlgo's "online quiz system" enables students to test their knowledge of basic data structures and algorithms. Questions are randomly generated based on specific rules, and students' answers are automatically graded upon submission to our grading server. As more CS instructors adopt this online quiz system worldwide, it could effectively eliminate manual basic data structure and algorithm questions from standard Computer Science exams in many universities. By assigning a small (but non-zero) weight to passing the online quiz, CS instructors can significantly enhance their students' mastery of these basic concepts, as they have access to an almost unlimited number of practice questions that can be instantly verified before taking the online quiz. Each VisuAlgo visualization module now includes its own online quiz component.

VisuAlgo has been translated into three primary languages: English, Chinese, and Indonesian. Additionally, we have authored public notes about VisuAlgo in various languages, including Indonesian, Korean, Vietnamese, and Thai:

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

Lim Dewen Aloysius, Ting Xiao

TBA1, TBA2, TBA3

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

The birth of this project was made possible by the generous Teaching Enhancement Grant from NUS Centre for Development of Teaching and Learning (CDTL).

#### 使用条款

VisuAlgo is generously offered at no cost to the global Computer Science community. If you appreciate VisuAlgo, we kindly request that you spread the word about its existence to fellow Computer Science students and instructors. You can share VisuAlgo through social media platforms (e.g., Facebook, YouTube, Instagram, TikTok, Twitter, etc), course webpages, blog reviews, emails, and more.

Data Structures and Algorithms (DSA) students and instructors are welcome to use this website directly for their classes. If you capture screenshots or videos from this site, feel free to use them elsewhere, provided that you cite the URL of this website (https://visualgo.net) and/or the list of publications below as references. However, please refrain from downloading VisuAlgo's client-side files and hosting them on your website, as this constitutes plagiarism. At this time, we do not permit others to fork this project or create VisuAlgo variants. Personal use of an offline copy of the client-side VisuAlgo is acceptable.

Please note that VisuAlgo's online quiz component has a substantial server-side element, and it is not easy to save server-side scripts and databases locally. Currently, the general public can access the online quiz system only through the 'training mode.' The 'test mode' offers a more controlled environment for using randomly generated questions and automatic verification in real examinations at NUS.

List of Publications

This work has been presented 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).

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.