Sorting Algorithms

Sorting algorithms are ubiquitous in computer science. This webpage provides a visual demonstration of some popular sorting algorithms.

Visualization

The height of the candles represents their numerical value. Initially, the candles are randomly distributed. You can use various sorting algorithms to put them in ascending order. Sorted sections of the list are shown in blue, whereas unsorted sections are shown in red. In divide-andconquer algorithms like quick sort and merge sort, sections of the list being ignored are colored gray. White candles convey that the iterator is at their position. Yellow candles are used to depict candles of interest, eg: the maximum number envountered so far during selection sort. In quick sort, the pivot candle is colored purple (and is placed at the end of the list).

Metrics:



Choose a sorting algorithm:


Description

  1. Bubble sort: A simple sorting algorithm that just goes through the list comparing adjacent elements and swapping them if they are not in order. It's performance and utiity are very poor, and is primarily taught for educational purposes. It has an average time complexity of O(n2). However, if the machine performing the sort has a sizeable probability of not comparing elements properly, then bubble sort is the most fault tolerant algorithm in this list (since it makes frequent comparisons, and can detect mistakes made previously).

  2. Selection sort: Another simple sorting algorithm. It scans all N elements, finds the largest one, and puts it at the Nth position. Then, it scans all N-1 elements, finds the largest one, puts it at the (N-1)th position, and so on. It is as worse as bubble sort, with an average time complexity of O(n2). It doesn't use the advantages from an approimately sorted list. However, it is noted for it's simplicity.

  3. Insertion sort: An algorithm that most humans likely use unconsciously to sort things. It considers the first k elements to be sorted, and figures out where the (k+1)th element should be placed within the sorted portion. Although it's time complexity is still O(n2), insertion sort has significant advantages over the last two. It is extremely good to sorting lists that are already approximately sorted, nearing a time complexity of O(n) in this case. Even if a list is already sorted, it can readily accept another element and put it in it's correct place.

  4. Cocktail Shaker sort: A variation of selection sort that scans for the maximum element while going forward, and the minimum element while going backwards. It is useful for electromechanical machines that use a physical data reader to scan and sort through values sorted in a tape.

  5. Heap sort: A slightly complex sorting algorithm that uses a data structure called heaps. First algorithm on this list to have a time complexity of O(n log n), although it comes with a space complexity of O(n), and the only algorithm on this list to require explicit space. It is extremely good at keeping frequently updated lists sorted dynamically, an advantage conferred by the data structure that it is built on. For information on the heap data structure, please refer GeeksForGeeks website.

  6. Quick sort: As the name implies, it has the fastest time complexity of O(n log n) despite not requiring any explicit memory. It randomly choses an element as a pivot, and transports all elements lower than the pivot to the left, and the elements greater than the pivot to the right of the pivot. The same operation is repeated on the portion of the list to the left and right of the pivot, recursively. Despite it's charasmatic name, it is difficult to implement, and certain choices of pivots can be disastrous on it's runtime.

  7. Merge sort: The industrial standard for sorting huge lists. It recursively divides the list into smaller lists, sorts the smaller ones and merges them in the right way. It always has a time complexity of O(n log n). A merge sort routine with multithreading support can sort billions of numbers in no time. However, it uses some auxillary memory while merging, and is really difficult to implement.

Note:
  1. If the simulation freezes then please refresh the page
  2. Related: Maze Generation

Developed by ChanRT | Fork me at GitHub