Show Menu
Cheatography

Sorting

Sorting is rearra­nging the given data in a specific format- ascending or descen­ding.
The purpose of sorting elements is to greatly improve the efficiency of searching while doing comput­ations on the data.
In Java, we can sort primitive data (using sorting algori­thms) , or user-d­efined data (using Comparable or Comparator interf­aces)
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 recurs­ively 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. Recurs­ively 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 "­hea­pif­y" 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)
       
 

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

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          Related Cheat Sheets

          Eclipse Cheat Sheet
          Selenium WebDriver Cheat Sheet Cheat Sheet

          More Cheat Sheets by evanescesn09