Sorting algorithms 📚
source link: https://bernhardfritz.github.io/p8g/blog/2023/04/06/sorting-algorithms/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Sorting algorithms 📚
Nearly every standard library offers data structures that can be sorted without really thinking about it. Still, it might come in handy to know about commonly used sorting algorithms or even implement some of them yourself as an exercise. After all, most sorting algorithms make heavy use of array indexing and recursion, and for this reason alone, they are often used as a medium to learn about and apply these concepts.
Even though sorting algorithms can be categorized by just a handful of different methods, there are hundreds of variations out there. Some algorithms are more efficient than others. You can compare their efficiency by both time complexity and memory consumption. It is worth noting that some sorting algorithms may perform worse in certain situations while, on average, they perform better than others. Finally, a stable sorting algorithm is expected to preserve the order of elements considered to be equal.
As you can tell, choosing the right sorting algorithm may not always be so easy. For this reason, I have compiled the following list, including implementation details for future reference:
Name | Best Average Worst | Memory | Stable | Method | Visualization |
---|---|---|---|---|---|
Quicksort | nlognn \log nnlogn nlognn \log nnlogn n2n^2n2 | logn\log nlogn | No | Partitioning | |
Merge sort | nlognn \log nnlogn nlognn \log nnlogn nlognn \log nnlogn | nnn | Yes | Merging | |
Heapsort | nlognn \log nnlogn nlognn \log nnlogn nlognn \log nnlogn | 1 | No | Selection | |
Insertion sort | nnn n2n^2n2 n2n^2n2 | 1 | Yes | Insertion | |
Selection sort | n2n^2n2 n2n^2n2 n2n^2n2 | 1 | No | Selection | |
Shellsort | nlognn \log nnlogn n43n^{4 \over 3}n34 n32n^{3 \over 2}n23 | 1 | No | Insertion | |
Bubble sort | nnn n2n^2n2 n2n^2n2 | 1 | Yes | Exchanging |
Further reading
- Sorting algorithm on Wikipedia, the free encyclopedia
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK