Sorting Algorithms Cheat Sheet

Hey Sorting ! Let's deal with you today !

PreviousData Structures Cheatsheet NextData Structures Cheatsheet

Last updated 1 year ago

Was this helpful?

Sorting Algorithms Cheat Sheet

Hey Sorting ! Let's deal with you today !

All major programming languages have a built-in method for sorting. It is usually correct to assume and say sorting costs O ( n ⋅ log ⁡ n ) , where n is the number of elements being sorted. For completeness, here is a chart that lists many common sorting algorithms and their completeness. The algorithm implemented by a programming language varies; for example, Python uses Timsort but in C++, the specific algorithm is not mandated and varies.

Some Important Terms

Comparison Sorting : Many sorting algorithms work by comparing elements and swapping them if they are in the wrong order. Algorithms like bubble sort and quicksort fall into this category.
Non-Comparison Sorting: Some sorting algorithms don't rely on direct element comparisons. Examples include counting sort, radix sort, and bucket sort. These algorithms are often more efficient for specific types of data.
Stability: A sorting algorithm is stable if it preserves the relative order of equal elements in the sorted output. Stability is important in situations where you want to maintain the original order of elements when they have equal keys.
In-Place Sorting: In-place sorting algorithms do not require additional memory to rearrange elements; they rearrange elements within the existing data structure. Quicksort is an example of an in-place sorting algorithm.
Out-of-Place Sorting: Out-of-place sorting algorithms create a new data structure to store the sorted elements, leaving the original data structure unchanged. Merge sort is an example of an out-of-place sorting algorithm.
Adaptive Sorting: An algorithm is adaptive if it takes advantage of existing order in the input data to improve efficiency. For example, insertion sort performs well on partially sorted data.
External Sorting: External sorting is used for large datasets that cannot fit entirely in memory. It involves sorting chunks of data that can fit in memory and then merging these sorted chunks to obtain the final sorted output.
Parallel Sorting: Sorting can be parallelized to take advantage of multiple processors or cores in modern computing systems. Parallel sorting algorithms aim to improve sorting speed by distributing the work across multiple processing units.
External Memory Sorting: This is a specialized type of sorting for situations where data is too large to fit in RAM. External memory sorting algorithms minimize the number of reads and writes to the slow external storage.

PreviousData Structures Cheatsheet NextData Structures Cheatsheet

Last updated 1 year ago

Was this helpful?

Some Important Terms

Comparison Sorting : Many sorting algorithms work by comparing elements and swapping them if they are in the wrong order. Algorithms like bubble sort and quicksort fall into this category.
Non-Comparison Sorting: Some sorting algorithms don't rely on direct element comparisons. Examples include counting sort, radix sort, and bucket sort. These algorithms are often more efficient for specific types of data.
Stability: A sorting algorithm is stable if it preserves the relative order of equal elements in the sorted output. Stability is important in situations where you want to maintain the original order of elements when they have equal keys.
In-Place Sorting: In-place sorting algorithms do not require additional memory to rearrange elements; they rearrange elements within the existing data structure. Quicksort is an example of an in-place sorting algorithm.
Out-of-Place Sorting: Out-of-place sorting algorithms create a new data structure to store the sorted elements, leaving the original data structure unchanged. Merge sort is an example of an out-of-place sorting algorithm.
Adaptive Sorting: An algorithm is adaptive if it takes advantage of existing order in the input data to improve efficiency. For example, insertion sort performs well on partially sorted data.
External Sorting: External sorting is used for large datasets that cannot fit entirely in memory. It involves sorting chunks of data that can fit in memory and then merging these sorted chunks to obtain the final sorted output.
Parallel Sorting: Sorting can be parallelized to take advantage of multiple processors or cores in modern computing systems. Parallel sorting algorithms aim to improve sorting speed by distributing the work across multiple processing units.
External Memory Sorting: This is a specialized type of sorting for situations where data is too large to fit in RAM. External memory sorting algorithms minimize the number of reads and writes to the slow external storage.