Only applicable on monotonic values (Increasing or Decreasing)
Sorting
Selection Sort
Select the minimum element and place it at the correct place
Space Complexity = O(1)
Time Complexity = O(n2) => Same in Best/Worst case
Used when array/vector size is small
It is not a Stable sorting algorithm
It is a In-Place algorithm
Bubble Sort
Round ith => Place ith largest element in its correct place
Space Complexity = O(1)
Time Complexity = O(n2)
Best case = O(n)
Worst case = O(n2)
It is a Stable sorting algorithm
It is a In-Place algorithm
Insertion Sort
Insert the new element in the sorted array
Good algorithm for a running stream where new data is added
Space Complexity = O(1)
Time Complexity = O(n2)
Best case = O(n)
Worst case = O(n2)
Adaptable algorithm => We don't have to loop through entire array
It is a Stable sorting algorithm
It is a In-Place algorithm
Merge Sort
Break array into 2 parts and Sort it and merge those 2 sorted arrays
Space Complexity = O(n)
O(logn) in case of LL
Time Complexity
Average case = O(nlogn)
Worst case = O(nlogn)
Preferred over Quick sort for Linked List
Random access of data is not possible for quick sort
In-place merge operation for merge sort
It is a Stable sorting algorithm
It is not a In-Place algorithm
Quick Sort
Do Partition where the left elements are small and right elements are all bigger
Time Complexity
Best case = O(nlogn)
Average case = O(nlogn)
Worst case = O(n2)
Preferred over Merge sort for Arrays
Better locality of reference than merge sort
Locality of reference refers to a phenomenon in which a computer program tends to access same set of memory locations for a particular time period
It is not a Stable sorting algorithm
It is a In-Place algorithm
Extra space required is not used to manipulate input, but only for recursive calls
Heap Sort
Time Complexity
Average case = O(nlogn)
It is a not Stable sorting algorithm
It is a In-Place algorithm
Count Sort
It is a Stable sorting algorithm
Radix Sort
Time Complexity = O(n+k)
k = Range of Elements
Recursion
Components of the Function
Base Case/Condition
Where recursion stops
return is mandatory, otherwise segmentation fault (StackOverFlow)
Recursive Relation
If this is after Processing then its called Tail Recurring otherwise Head Recurring
Processing Part
Steps
Find base case > Find relation between the problem and subproblem > Generalize the relation
Theory
A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted
An in-place algorithm is an algorithm that does not need an extra space and produces an output in the same memory that contains the data by transforming the input "in-place"
