Keywords:
algorithms,data structures,sorting,graphs,strings,big o
Legends
-
swapping elements -
sorted elements
Bubble Sort (sometimes called siking sort), is an simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. It has an O(n2) time complexity, which makes it inefficient on large collections, and generally performs poorly in real world use and is used primarily as an educational tool.
Bubble Sort is one of the simplest sorting algorithms to understand and implement, its O(n2) complexity means that its efficiency decreases dramatically on lists of more than a small number of elements. Even among simple O(n2) sorting algorithms, algorithms like Insertion Sort are usually considerably more efficient.
Property Description Data Structure Array Stable Yes Worst-case performance O(n2) comparisons
O(n2) swapsBest-case performance O(n) comparisons
O(n) swaps (if we keep track of swaps)Average performance O(n2) comparisons
O(n2) swapsWorst-case space complexity O(1) auxiliary
...
...
...
Legends
-
element to be inserted -
partition index -
sorted elements
Insertion Sort is a simple in-place sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as Quicksort, Heapsort, or Merge Sort. However, Insertion Sort provides several advantages:
- Simple implementation: Jon Bentley shows a three-line C version, and a five-line optimized version.
- Efficient for (quite) small data sets, much like other quadratic sorting algorithms
- More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as
Selection SortorBubble Sort. - Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each element in the input is no more than k places away from its sorted position.
Property Description Data Structure Array Stable Yes Worst-case performance O(n2) comparisons
O(n2) swapsBest-case performance O(n) comparisons
O(1) swapsAverage performance O(n2) comparisons
O(n2) swapsWorst-case space complexity O(n) total, O(1) auxiliary
Legends
sorted elements
Merge Sort is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output.
Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up mergesort appeared in a report by Goldstine and von Neumann as early as 1948.
Conceptually, a merge sort works as follows:
- Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).
- Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.
Property Description Data Structure Array Stable Yes Worst-case performance O(n log n) typical Best-case performance O(n log n) typical
O(n log n) natural variantAverage performance O(n log n) Worst-case space complexity O(n) total with O(n) auxiliary,
O(1) auxiliary with linked lists
Legends
-
pivot -
current element -
right partition element -
left partition element -
sorted elements
View Code v1: Middle element as Pivot
Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm. Developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, Merge Sort and Heapsort.
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.
Quicksort is a comparison sort, meaning that it can sort items of any type for which a less-than relation (formally, a total order) is defined. Efficient implementations of Quicksort are not a stable sort, meaning that the relative order of equal sort items is not preserved.
Property Description Data Structure Array Stable No Worst-case performance O(n2) Best-case performance O(n log n) simple partition
O(n) three-way partition on equal keyAverage performance O(n log n) Worst-case space complexity O(n) naive
O(log n) auxiliary (Sedgewick 1978)
...
Legends
-
smallest element -
current element -
sorted elements
Selection Sort is an in-place comparison sorting algorithm. It has an O(n2) time complexity, which makes it inefficient on large collections, and generally performs worse than the similar Insertion Sort.
Selection Sort is noted for its simplicity and has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.
The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.
The time efficiency of Selection Sort is quadratic, so there are a number of sorting techniques which have better time complexity than Selection Sort. One thing which distinguishes Selection Sort from other sorting algorithms is that it makes the minimum possible number of swaps, n − 1 in the worst case.
Property Description Data Structure Array Stable No Worst-case performance O(n2) comparisons
O(n) swapsBest-case performance O(n2) comparisons
O(n) swapsAverage performance O(n2) comparisons
O(n) swapsWorst-case space complexity O(1)
...
...
Marcos Lima
- GNU General Public License v3.0
- Copyright 2020 © marcosmapl.
