Sorting Cheat Sheet

A Programming › Java cheat sheet in English by evanescesn09

18,979 views 3,830 downloads 17 Aug 2019 History

PRs

4.3 avg · 1 rating

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)

Badges

Nice Cheat Sheet Downloaded from Unusual Locations × 1

Comments (1)

towi 08:08 19 Aug 2019

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"?