Sorting - AlgoVis.io

Overview

A sorting algorithm is an algorithm that puts elements of a list in a certain order (thus sorting the list). The most frequently used orders are numerical order for lists of numbers and lexicographical order for lists of strings.

To put it more formally, the output generally has to fulfill two conditions:

The output is in nondecreasing order
The output is a permutation of the input

Or, to put it simply, when running a sorting algorithm we expect an output that contains all the elements originally present in the input arranged in such a way that the smallest element (according to the operation used to sort the list) is in the leftmost place, with every element following being either bigger or equal to its predecessor.

Sorting algorithms can generally be classified into three distinct categories:

Comparison sorts
Non-comparison sorts
Others

On this page you can find many implementations for every category. If you need a visualization for a certain algorithm, just use the search function to find it quickly.

Search

A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occur first in the final sorted list.

Bubblesort

Comparison sort

Bubblesort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Best-case: O(n)
Average-case: O(n²)
Worst-case: O(n²)

Cocktail shaker sort

Comparison sort

Cocktail shaker sort is an extension of bubble sort. It extends bubble sort by operating in two directions. While it improves on bubble sort by more quickly moving items to the beginning of the list, it provides only marginal performance improvements.

Best-case: O(n)
Average-case: O(n²)
Worst-case: O(n²)

Combsort

Comparison sort

Combsort is an extension of bubble sort. It compares elements divided by a gap which shrinks after each pass through the list. This helps move smaller elements to the beginning of the list faster, which is a main problem of bubble sort.

Best-case: O(n log n)
Average-case: O(n²)
Worst-case: O(n²)

Gnomesort

Comparison sort

The gnome sort is a sorting algorithm which is similar to insertion sort in that it works with one item at a time but gets the item to the proper place by a series of swaps, similar to a bubble sort.

Best-case: O(n)
Average-case: O(n²)
Worst-case: O(n²)

Insertionsort

Comparison sort

Insertion sort is a simple sorting algorithm that builds the final sorted list one item at a time by inserting each element at its correct position.

Best-case: O(n)
Average-case: O(n²)
Worst-case: O(n²)

Quicksort

Comparison sort

Quicksort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting.
Best-case: O(n log n)
Average-case: O(n log n)
Worst-case: O(n²)

Selection sort

Comparison sort

Selection sort divides the input list into two parts: a sorted sublist of items which is built up from left to right and an unsorted sublist. The algorithm repeatedly iterates over the unsorted sublist, finds the smallest element in that sublist, swaps it with the leftmost unsorted element, and moves the sublist boundaries one element to the right.

Best-case: O(n)
Average-case: O(n²)
Worst-case: O(n²)

Non-Comparison Sorts are sorting algorithms which sort a given input without comparing the elements, rather making certain assumptions about the data. Examples for non-comparison sorting algorithms are Counting sort which sorts using key-value and Bucket Sort which examines bits of keys.

Counting sort

Non-Comparison sort

Counting sort is an algorithm for sorting a collection of objects according to keys that are small integers. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence.

Time complexity: O(n+k)
with n being the number of elements and k being the number of keys.

Radix sort

Non-Comparison sort

Radix sort avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered.

Time complexity: O(nw)
with n being the number of elements and w being the key length.

Algorithms in this category are impractical for real-life use in traditional software contexts due to extremely poor performance or specialized hardware requirements. These sorts are usually described for educational purposes in order to demonstrate how run time of algorithms is estimated.

Bogosort

Other sort

Bogosort is a highly inefficient sorting algorithm based on the generate and test paradigm. The function successively generates permutations of its input until it finds one that is sorted. An analogy for the working of the algorithm is to sort a deck of cards by throwing the deck into the air, picking the cards up at random, and repeating the process until the deck is sorted

Best-case: O(n)
Average-case: O((n+1)!)
Worst-case: unbounded