Comparison of sorting algorithms : Sheet1

1 | Name | Compare | Best case | Average case | Worst case | In-place | Stable | Shorthand Description (only useful if you already know the processes) | Notes |
---|---|---|---|---|---|---|---|---|---|

2 | Bubble sort | yes | n | n^2 | n^2 | yes | yes | swap elements, until greatest at end. mark sorted. loop. if no swaps occur, stop. | very inefficient |

3 | Selection sort | yes | n^2 | n^2 | n^2 | yes | yes* | find greatest element, swap with beginning index. iterate index. do until end. | good for small amounts of data; *normally unstable bc will replace b with B if B is biggest in rest of list, have to replace swap with insert |

4 | Tree sort | yes | nlog(n) | nlog(n) | n^2 | no | no | builds bst, performs in order traversal | n^2 when unbalanced |

5 | Heap sort | yes | nlog(n) | nlog(n) | nlog(n) | no | no | build min/max heap, remove until all nodes gone. | heap often represented in array when doing this sort |

6 | Quick sort | yes | nlog(n) | nlog(n) | n^2 | yes | no | pick pivot, elements go below and above. repeat on partitions recursively. | n^2 when data is pre-sorted |

7 | Merge sort | yes | nlog(n) | nlog(n) | nlog(n) | no | yes | divide list of elements into sublists of size 1. merge sublists together recursively. | guaranteed nlog(n) |

8 | Counting sort | no | n | n | n | no | yes | count number of each element and put into array. loop through array. | works for numbers only |

9 | Bucket sort | no | n | n | n^2 | no | yes | distribute elements into buckets. then sort buckets using another sorting algorithm. | similar to radix sort. works for huge datasets. |

10 | Radix sort | no | n | n | n | no | yes | sort based on rightmost character. then sort w character to left. repeat. | works for equal length sequences. usually strings or numbers. |