Cheatography
https://cheatography.com
Sorting
Sorting is rearranging the given data in a specific format- ascending or descending.
The purpose of sorting elements is to greatly improve the efficiency of searching while doing computations on the data.
In Java, we can sort primitive data (using sorting algorithms) , or user-defined data (using Comparable or Comparator interfaces) |
We have 2 main kinds of sorting:
1. Internal Sorting - done in main memory
2. External Sorting - algorithms that use external memory like tape, or a disk for sorting.
External sorting is used when data is too large to fit into main memory.
Bubble Sort
Technique |
Brute Force |
How? |
Each element is compared with every other element, and when they are not in correct order, they are swapped |
Time Complexity |
n^2 |
Space Complexity |
O(1) - because it is done in place |
Merge Sort
Technique |
Divide and Conquer |
Best Used |
when merging 2 or more already sorted input lists |
How? |
Dividing the input data into half recursively till each input is of size=1. Then merging the sorted data into one |
Time Complexity |
O(nlogn) - logn to sort half the data in each recursion, n to merge all the input data to give the final sorted output |
Space Complexity |
O(n) extra space required when merging back the sorted data |
Merge Sort does not preserve ordering or elements of the same value
|
|
Insertion Sort
Technique |
Best used |
for small data |
Advantages |
Preserves insertion order of elements of same values |
How? |
Removes an element from the input list and insert into the correct position of the already sorted list. |
Time Complexity |
O(n^2) |
Space Complexity |
O(1) - because it is done in place |
Quick Sort
Technique |
Divide and Conquer |
How? |
Select a pivot element. Split the array into 2 parts - elements less than pivot and elements > pivot. Recursively repeat this process till all the elements are sorted. |
Time Complexity |
O(n logn) |
Space Complexity |
O(1) - it is done in place |
|
|
Selection Sort
Technique |
Best Used |
only for small set of data, it doesn't scale well for larger data sets |
How? |
Find min value in the list, swap it with element at current index. Repeat the process till the list is sorted. |
Time Complexity |
O(n^2) |
Space Complexity |
O(1) - because it is done in place |
Heap Sort
Technique |
Divide and Conquer |
Best Used |
Priority Queues |
How? |
Insert all elements into a heap (minHeap or MaxHeap). Then remove elements from the heap till the heap is empty. |
Heap |
The main property of a heap is that it always contains the min/max element at the root. As elements are inserted and deleted, the heap makes use of the "heapify" property to ensure that the min/max element is always at the root. So, always the min/max element is returned when the heap is dequeued |
Time Complexity |
O(nlogn) |
Space |
O(n) |
|
Created By
Metadata
Favourited By
Comments
Most useful cheat sheet I've seen in a long time. Add RadixSort. Its the best for special cases. Give worst-case complexity for each algorithm (and when it is to be expected. e.g. that QuickSort degrades to O(n^2) on already sorted data -- which is dangerous because it happens often in practice). You could add an introductory note on the danger of already-sorted data on some many of the algorithms. Or maybe add a section on each "complexity on pre-sorted input"?
Add a Comment
Related Cheat Sheets
More Cheat Sheets by evanescesn09