Sorting and Searching

Thanks for https://www.bigocheatsheet.com/ for building this compact cheat sheet:

• Merge sort: stable, used extensively. (Divide & Conquer)
• Quick sort: not stable, commonly used, beware, if the pivot is chosen poorly, it will hit O(n2). (Divide & Conquer)
• Heap sort: not stable.
• Insertion sort: used it if the array its self is almost sorted. (Decrease and Conquer)
• Counting sort: used for narrow range on the array, since it is run on O(n), will be faster than comparison sorting algorithms.
• Radix sort: for integers, it's O(n) on time complexity too.
• Selection Sort: Locate the smallest item, and put it in the first place, repeat this process n times for an array that contains n items. (Brute Force)
• Bubble Sort: Scan the array from right to left, swap the two elements in comparison if the order is not correct, bubble up the minimum to the left. (Brute Force)

notes:

• The two that are commonly used are Quicksort and Mergesort, depending on the situation, Bubble Sort and Insertion Sort maybe be used too.
• Non-comparison sorting algorithms can go beyond the limit on time complexity O(n log(n)), for example: Bucket Sort and Radix Sort
• The algorithm of quickSort: can be seen here
• The algorithm of quickSelect: can be implemented here
• The implementation of minHeap: with a little tweak, can be a maxHeap too. link

I think that's the end of this series, for now.

I might add more tips in the future as I progress through more and more Technical Interview questions.