7    VisuAlgo.net / /sorting Login Bubble Select Insert Merge Quick R-Quick Count Radix
Exploration Mode ▿

>

>
slow
fast
go to beginning previous frame pause play next frame go to end

Sorting is a very classic problem of reordering items that can be compared (Integers, floating-point numbers, strings, etc) of an array (or a list) in a certain order (increasing, non-decreasing, decreasing, non-increasing, 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.


Click 'Next' (on the top right)/press 'Page Down' to advance this e-Lecture slide, use the drop down list/press 'Space' to jump to a specific slide, or Click 'X' (on the bottom right)/press 'Esc' to go to Exploration mode.


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.

X Esc
Next PgDn

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

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

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.

X Esc
Prev PgUp
Next PgDn

When an array A is sorted, many problems involving array become easy (or easier), e.g.

  1. Searching for a specific value v in array A — binary search,
  2. Finding the min/max/k-th smallest/largest value in the (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, etc.

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


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.

X Esc
Prev PgUp
Next PgDn

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

X Esc
Prev PgUp
Next PgDn

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

  1. Totally random,
  2. Random but sorted (in ascending/descending order),
  3. Random but nearly sorted (in ascending/descending order), or
  4. Defined solely by yourself.
X Esc
Prev PgUp
Next PgDn

The second action is the most important one: Execute the active sorting algorithm by clicking "Sort" menu and then clicking Go.


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


Some sorting algorithms have certain additional options. You may toggle the options as you wish before clicking Go. For example, in Bubble Sort (and Merge Sort), there is an option to also compute the inversion index of the input array.

X Esc
Prev PgUp
Next PgDn

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 ascending order state.

X Esc
Prev PgUp
Next PgDn

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 → Go".


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


The first six algorithms 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.

X Esc
Prev PgUp
Next PgDn

To save screen space, we abbreviate algorithm names into three characters each:

  1. Comparison-based Sorting Algorithms:
    1. BUB - Bubble Sort,
    2. SEL - Selection Sort,
    3. INS - Insertion Sort,
    4. MER - Merge Sort (recursive implementation),
    5. QUI - Quick Sort (recursive implementation),
    6. R-Q - Random Quick Sort (recursive implementation).
  2. Not Comparison-based Sorting Algorithms:
    1. COU - Counting Sort,
    2. RAD - Radix Sort.
X Esc
Prev PgUp
Next PgDn

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

  1. Bubble Sort,
  2. Selection Sort,
  3. Insertion Sort.

They are called comparison-based as they compare pairs of elements of the array and decide whether to swap them or not.


These three sorting algorithms are the easiest to implement but also not the most efficient, as they run in O(N2).

X Esc
Prev PgUp
Next PgDn

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


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

X Esc
Prev PgUp
Next PgDn

Comparison and swap require time that is bounded by a constant c.


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
Total time = c*N*(N−1)/2 = O(N^2)

X Esc
Prev PgUp
Next PgDn

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 still need at worst 100 seconds to complete.


However, it can be terminated early, e.g. try Bubble Sort on the small sorted ascending example shown above where it 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?

X Esc
Prev PgUp
Next PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Prev PgUp
Next PgDn

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

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

Without further ado, let's try Selection Sort on the same small example array above.


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.

X Esc
Prev PgUp
Next PgDn
void selectionSort(int a[], int N) {
for (int L = 0; L <= N-2; L++) { // O(N)
find the position of the minimum element X ∈ [L..N-1] // O(N)
swap(X, L) // O(1), note that X may be equal to L (no actual swap)
}
}

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

X Esc
Prev PgUp
Next PgDn

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

3
2
1
4
X Esc
Prev PgUp
Next PgDn

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

  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.

Without further ado, let's try Insertion Sort on the small example array above.

X Esc
Prev PgUp
Next PgDn
void insertionSort(int a[], int N) {
for (int i = 1; i < N; i++) { // O(N)
X = a[i]; // X is the item to be inserted
for (j = i-1; 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; // this is the insertion point
}
}
X Esc
Prev PgUp
Next PgDn

The outer loop executes N−1 times, that's quite clear.


But the number of times the inner-loop is executed depends on the input:

  1. In best-case scenario, the array is already sorted and (a[j] > X) is always false
    So no shifting of data is necessary and the inner loop runs in O(1),
  2. In worst-case scenario, the array is reverse sorted and (a[j] > X) is always true
    Insertion always occur at the front of the array and the inner loop runs in O(N).

Thus, the best-case time is O(N × 1) = O(N) and the worst-case time is O(N × N) = O(N2).

X Esc
Prev PgUp
Next PgDn

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

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


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

X Esc
Prev PgUp
Next PgDn

We will discuss two (+half) comparison-based sorting algorithms in the next few slides:

  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 (except for the non-randomized version of Quick Sort).

X Esc
Prev PgUp
Next PgDn

Given an array of N items, Merge Sort will:

  1. Merge each pair of individual element (which is by default, sorted) into sorted arrays of 2 elements,
  2. Merge each pair of sorted arrays of 2 elements into sorted arrays of 4 elements,
    Repeat the process...,
  3. Final step: Merge 2 sorted arrays of N/2 elements (for simplicity of this discussion, we assume that N is even) to obtain a fully sorted array of N elements.

This is just the general idea and we need a few more details before we can discuss the true form of Merge Sort.

X Esc
Prev PgUp
Next PgDn

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, we will need additional array to do this merging correctly. See the next slide.

X Esc
Prev PgUp
Next PgDn
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 = new int[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
delete[] b; // remove the temporary array b
}

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

X Esc
Prev PgUp
Next PgDn

Before we continue, let's talk about Divide and Conquer (abbreviated as D&C), a powerful problem solving paradigm.


Divide and Conquer algorithm solves (certain kind of) problem — like our sorting problem — in the following steps:

  1. Divide step: Divide the large, original problem into smaller sub-problems and recursively solve the smaller sub-problems,
  2. Conquer step: Combine the results of the smaller sub-problems to produce the result of the larger, original problem.
X Esc
Prev PgUp
Next PgDn

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 routine discussed earlier.

X Esc
Prev PgUp
Next PgDn
void mergeSort(int a[], int low, int high) {
// the array to be sorted is a[low..high]
if (low < high) { // base case: low >= high (0 or 1 item)
int mid = (low+high) / 2;
mergeSort(a, low , mid ); // divide into two halves
mergeSort(a, mid+1, high); // then recursively sort them
merge(a, low, mid, high); // conquer: the merge routine
}
}
X Esc
Prev PgUp
Next PgDn

Please try Merge Sort on the example array to see more details.


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, on the example array {7,2,6,3,8,4,5}, it will recurse to {7,2,6,3}, then {7,2}, then {7} (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.

X Esc
Prev PgUp
Next PgDn

In Merge Sort, the bulk of work is done in the conquer/merge step as the divide step does not really do anything (treated as O(1)).


When we call merge(a, low, mid, high), we process k = (high-low+1) items.
There will be at most k-1 comparisons.
There are k moves from original array a to temporary array b and another k moves back.
In total, number of operations inside merge operation is < 3k-1 = O(k).


The important question is how many times this merge operation is called?

X Esc
Prev PgUp
Next PgDn
The Recursion Tree of Merge Sort
X Esc
Prev PgUp
Next PgDn

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.

X Esc
Prev PgUp
Next PgDn

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.

X Esc
Prev PgUp
Next PgDn

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.

X Esc
Prev PgUp
Next PgDn

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 p.
a[m] is the pivot 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.

X Esc
Prev PgUp
Next PgDn

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


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 item ≥ 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?

X Esc
Prev PgUp
Next PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Prev PgUp
Next PgDn

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 two cases:

  1. If a[k]p, put a[k] into S2, or
  2. Otherwise, put a[k] into S1.

These two 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.

X Esc
Prev PgUp
Next PgDn
Case when a[k] >= p, increment k, extend S2 by 1 item
X Esc
Prev PgUp
Next PgDn
Case when a[k] < p, increment m, swap a[k] with a[m], increment k, extend S1 by 1 item
X Esc
Prev PgUp
Next PgDn
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) { // case 2
m++;
swap(a[k], a[m]); // C++ STL algorithm::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, to be used by Quick Sort
}
X Esc
Prev PgUp
Next PgDn
void quickSort(int a[], int low, int high) {
if (low < high) {
int pivotIdx = partition(a, low, high); // O(N)
// a[low..high] ~> a[low..pivotIdx–1], pivot, a[pivotIdx+1..high]
quickSort(a, low, pivotIdx-1); // recursively sort left subarray
// a[pivotIdx] = pivot is already sorted after partition
quickSort(a, pivotIdx+1, high); // then sort right subarray
}
}
X Esc
Prev PgUp
Next PgDn

Try Quick Sort.


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[3] = 27 as part of S2 so S1 = {12} and S2 = {38,39,27}.
We swap a[2] = 38 with a[5] = 16 so S1 = {12,16} and S2 = {39,27,38}.
We swap p = a[0] = 27 with a[2] = 16 so S1 = {12,16}, p = {27}, and S2 = {39,27,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].

X Esc
Prev PgUp
Next PgDn

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.

X Esc
Prev PgUp
Next PgDn

When the array a is already in ascending order, like the example above, 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).


Try Quick Sort on this example input array.

X Esc
Prev PgUp
Next PgDn

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

X Esc
Prev PgUp
Next PgDn

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 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 above.
In practice, this is rare, thus we need to devise a better way: Random Quick Sort.

X Esc
Prev PgUp
Next PgDn

Same as Quick Sort except just before executing the partition algorithm, it randomly select the pivot between a[low..high] instead of always choosing a[low] deterministically.


Try Random Quick Sort on this large and somewhat random example array.

X Esc
Prev PgUp
Next PgDn

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 visualization, 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) time complexity.

X Esc
Prev PgUp
Next PgDn

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.

X Esc
Prev PgUp
Next PgDn

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.

X Esc
Prev PgUp
Next PgDn

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 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(k) 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 O(N+k) which is O(N) if k is (very) small.


We will not be able to do the counting part of Counting Sort when k is relatively big due to memory limitation.

X Esc
Prev PgUp
Next PgDn

Assumption: If the items to be sorted are Integers with somewhat large range, 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 d digits (we pad Integers that have less than d 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(d × (N+k)) iterations. In this example, d = 4 and k = 10.

X Esc
Prev PgUp
Next PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Prev PgUp
Next PgDn

There are a few other properties that can be used to differentiate sorting algorithms on top of whether they are comparison or non-comparison, recursive or iterative.


In this section, we will talk about in-place versus not in-place, stable vs not stable, and caching performance of sorting algorithms.

X Esc
Prev PgUp
Next PgDn

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, due to its Merge 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?

X Esc
Prev PgUp
Next PgDn

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 groups still appear in alphabetical order of their names.


Discussion: Which of the sorting algorithms discussed in this visualization are stable?

X Esc
Prev PgUp
Next PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Prev PgUp
Next PgDn

We are nearing the end of this e-Lecture.


Time for a few simple questions.

X Esc
Prev PgUp
Next PgDn

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

Bubble Sort
Insertion Sort
QuickSort (Deterministic)
Merge Sort
X Esc
Prev PgUp
Next PgDn

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

Merge Sort
Insertion Sort
Radix Sort
Selection Sort
Bubble Sort


Θ is a tight time complexity analysis where the best case Ω and the worst case big-O analysis match.

X Esc
Prev PgUp
Next PgDn

We have reached the end of sorting e-Lecture.


However, there are two other sorting algorithms in VisuAlgo that are embedded in other data structures: Heap Sort and Balanced BST Sort. We will discuss them when you go through the e-Lecture of those two data structures.

X Esc
Prev PgUp
Next PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Prev PgUp
Next PgDn

We don't provide source code for these basic sorting algorithms. 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.


In C++, you can use STL algorithm::sort. In Java, you can use Collections.sort.


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

X Esc
Prev PgUp
Next PgDn

Note: Please Sign up/Login before attempting the training!


Test your understanding here!

X Esc
Prev PgUp
Next PgDn

Now that you have reached the end of this e-Lecture, do you think sorting problem is just as simple as calling built-in sort routine?


Try these two online judge problems to find out more: Kattis - sortofsorting or Kattis - sidewayssorting


This is not the end of the topic of sorting. When you explore other topics in VisuAlgo, you will realise that sorting is a pre-processing step for many other advanced algorithms for harder problems.

X Esc
Prev PgUp
Next PgDn

As the action is being carried out, each step will be described in the status panel.

X Esc
Prev PgUp
Next PgDn

e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).

X Esc
Prev PgUp
Next PgDn

Control the animation with the player controls! Keyboard shortcuts are:

Spacebar: play/pause/replay
Left/right arrows: step backward/step forward
-/+: decrease/increase speed
X Esc
Prev PgUp
Next PgDn

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.

X Esc
Prev PgUp

0 1 2 3 4 5 6 7 8 9

Create

Sort

>

Random

Sorted

Increasing

Decreasing

Nearly sorted

Increasing

Decreasing

Go

 Compute Inversion Index

Go

About Team Terms of use

About

VisuAlgo was conceptualised in 2011 by Dr Steven Halim as a tool to help his students better understand data structures and algorithms, by allowing them to learn the basics on their own and at their own pace.

VisuAlgo contains many advanced algorithms that are discussed in Dr Steven Halim's book ('Competitive Programming', co-authored with his brother Dr Felix Halim) and beyond. Today, some of these advanced algorithms visualization/animation can only be found in VisuAlgo.

Though specifically designed for National University of Singapore (NUS) students taking various data structure and algorithm classes (e.g. CS1010, CS1020, CS2010, CS2020, CS3230, and CS3230), as advocators of online learning, we hope that curious minds around the world will find these visualisations useful too.

VisuAlgo is not designed to work well on small touch screens (e.g. smartphones) from the outset due to the need to cater for many complex algorithm visualizations that require lots of pixels and click-and-drag gestures for interaction. The minimum screen resolution for a respectable user experience is 1024x768 and only the landing page is relatively mobile-friendly.

VisuAlgo is an ongoing project and more complex visualisations are still being developed.

The most exciting development is the automated question generator and verifier (the online quiz system) that allows students to test their knowledge of basic data structures and algorithms. The questions are randomly generated via some rules and students' answers are instantly and automatically graded upon submission to our grading server. This online quiz system, when it is adopted by more CS instructors worldwide, should technically eliminate manual basic data structure and algorithm questions from typical Computer Science examinations in many Universities. By setting a small (but non-zero) weightage on passing the online quiz, a CS instructor can (significantly) increase his/her students mastery on these basic questions as the students have virtually infinite number of training questions that can be verified instantly before they take the online quiz. The training mode currently contains questions for 12 visualization modules. We will soon add the remaining 8 visualization modules so that every visualization module in VisuAlgo have online quiz component.

Another active branch of development is the internationalization sub-project of VisuAlgo. We want to prepare a database of CS terminologies for all English text that ever appear in VisuAlgo system. This is a big task and requires crowdsourcing. Once the system is ready, we will invite VisuAlgo visitors to contribute, especially if you are not a native English speaker. Currently, we have also written public notes about VisuAlgo in various languages: zh, id, kr, vn, th.

Team

Project Leader & Advisor (Jul 2011-present)
Dr Steven Halim, Senior Lecturer, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Software Engineer, Google (Mountain View)

Undergraduate Student Researchers 1 (Jul 2011-Apr 2012)
Koh Zi Chun, Victor Loh Bo Huai

Final Year Project/UROP students 1 (Jul 2012-Dec 2013)
Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy

Final Year Project/UROP students 2 (Jun 2013-Apr 2014)
Rose Marie Tan Zhao Yun, Ivan Reinaldo

Undergraduate Student Researchers 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

Final Year Project/UROP students 3 (Jun 2014-Apr 2015)
Erin Teo Yi Ling, Wang Zi

Final Year Project/UROP students 4 (Jun 2016-Dec 2017)
Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir

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

Acknowledgements
This project is made possible by the generous Teaching Enhancement Grant from NUS Centre for Development of Teaching and Learning (CDTL).

Terms of use

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, course webpage, blog review, email, 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 (http://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 a real examination in NUS. Other interested CS instructor should contact Steven if you want to try such 'test mode'.

List of Publications

This work has been presented briefly at the CLI Workshop at the ACM 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).

This work is done mostly by my past students. The most recent final reports are here: Erin, Wang Zi, Rose, Ivan.

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.