- Bubble Sort: compares two adjacent elements and swaps them if they are not in the intended order.
bubbleSort(array)
for i <- 1 to indexOfLastUnsortedElement-1
if leftElement > rightElement
swap leftElement and rightElement
end bubbleSort
- Insertion Sort: places an unsorted element at its suitable place in each iteration.
insertionSort(array)
mark first element as sorted
for each unsorted element X
'extract' the element X
for j <- lastSortedIndex down to 0
if current element j > X
move sorted element to the right by 1
break loop and insert X here
end insertionSort
- Selection Sort: selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.
selectionSort(array, size)
repeat (size - 1) times
set the first unsorted element as the minimum
for each of the unsorted elements
if element < currentMinimum
set element as new minimum
swap minimum with first unsorted position
end selectionSort
| Sorting | Average | Worst | Best | Space | Stability |
|---|---|---|---|---|---|
| Bubble Sort | O(N^2) | O(N^2) | O(N) | O(1) | YES |
| Insertion Sort | O(N^2) | O(N^2) | O(N) | O(1) | YES |
| Selection Sort | O(N^2) | O(N^2) | O(N^2) | O(1) | NO |
- Merge Sort: the MergeSort function repeatedly divides the array into two halves until we reach a stage where we try to perform MergeSort on a subarray of size 1 (i.e. left == right). After that, the merge function comes into play and combines the sorted arrays into larger arrays until the whole array is merged.
MergeSort(A, l, r):
if l > r
return
m = (l+r)/2
mergeSort(A, l, m)
mergeSort(A, m+1, r)
merge(A, l, m, r)
- Quick Sort: An array is divided into sub-arrays by selecting a pivot element from the array. The pivot element should be positioned in such a way that elements less than pivot are kept on the left side and elements greater than pivot are on the right side of the pivot. The left and right sub-arrays are also divided using the same approach. This process continues until each subarray contains a single element. At this point, elements are already sorted. Finally, elements are combined to form a sorted array.
quickSort(array, leftmostIndex, rightmostIndex)
if (leftmostIndex < rightmostIndex)
pivotIndex <- partition(array,leftmostIndex, rightmostIndex)
quickSort(array, leftmostIndex, pivotIndex - 1)
quickSort(array, pivotIndex, rightmostIndex)
partition(array, leftmostIndex, rightmostIndex)
set rightmostIndex as pivotIndex
storeIndex <- leftmostIndex - 1
for i <- leftmostIndex + 1 to rightmostIndex
if element[i] < pivotElement
swap element[i] and element[storeIndex]
storeIndex++
swap pivotElement and element[storeIndex+1]
return storeIndex + 1
- Heap Sort: Build a max-heap based on the array (heapify), the largest item is stored at the root node. Remove the root element and put at the end of the array (nth position) Put the last item of the tree (heap) at the vacant place. Reduce the size of the heap by 1. Heapify the root element again so that we have the highest element at root. The process is repeated until all the items of the list are sorted.
heapify(array, index)
Root = array[index]
Largest = largest(root, left child, right child)
if(Root != Largest)
Swap(Root, Largest)
heapify(array, Largest)
heapSort(array)
for index <- n//2-1 to 0
heapify the index
for index <- n-1 to 0
Swap(array[0], array[index])
heapify(array, index, 0)
| Sorting | Average | Worst | Best | Space | Stability |
|---|---|---|---|---|---|
| Merge Sort | O(N*logN) | O(N*logN) | O(N*logN) | O(N) | YES |
| Quick Sort | O(N*logN) | O(N^2) | O(N*logN) | O(N*logN) | NO |
| Heap Sort | O(N*logN) | O(N*logN) | O(N*logN) | O(1) | YES |
- Counting Sort
- Bucket Sort
- Radix Sort
| Sorting | Average | Worst | Best | Space | Stability |
|---|---|---|---|---|---|
| Counting Sort | O(N+k) | O(N+k) | O(N+k) | O(N+k) | YES |
| Bucket Sort | O(N+k) | O(N^2) | O(N) | O(N+k) | YES |
| Radix Sort | O(N*k) | O(N*k) | O(N*k) | O(N+k) | YES |
Linear search is a sequential searching algorithm where we start from one end and check every element of the list until the desired element is found. It is the simplest searching algorithm.
LinearSearch(array, key)
for each item in the array
if item == value
return its index
Binary Search is a searching algorithm for finding an element's position in a sorted array. Binary search can be implemented only when the array is:
- Monotonically increasing/decreasing
- Bounded (have upper and lower bound)
- Index accessible
Iterative Method
def binary_search(nums, target)
left, right = 0, len(nums) - 1
while left <= right:
# use (left + right) // 2 might be out of bound
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else: # found
return mid
return -1Recursive Method
def binary_search(nums, target):
def helper(left, right):
if left <= right:
# use (left + right) // 2 might be out of bound
mid = left + (right - left) // 2
if nums[mid] < target:
return helper(mid + 1, right)
elif nums[mid] > target:
return helper(left, mid - 1)
else: # found
return mid
return -1
return helper(0, len(nums) - 1)Variation 1: Find the first match (array contains duplicates)
def binary_search1(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
# use (left + right) // 2 might be out of bound
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
if mid == 0 or a[mid - 1] != target:
return mid # the first match
else:
right = mid - 1 # keep searching
return -1Variation 2: Find the last match (array contains duplicates)
def binary_search2(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
# use (left + right) // 2 might be out of bound
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
if mid == n - 1 or a[mid + 1] != target:
return mid # the last match
else:
left = mid + 1 # keep searching
return -1Variation 3: Find first number greater than target (array contains duplicates)
def binary_search3(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
# use (left + right) // 2 might be out of bound
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
if mid == 0 or a[mid - 1] < target:
return mid # the first number greater than target
else:
right = mid - 1 # keep searching
return -1Variation 4: Find first number smaller than target (array contains duplicates)
def binary_search4(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
# use (left + right) // 2 might be out of bound
mid = left + (right - left) // 2
if nums[mid] > target:
right = mid - 1
else:
if mid == n - 1 or a[mid + 1] > target:
return mid # the first number smaller than target
else:
left = mid + 1 # keep searching
return -1Target Function g(m)
def binary_search(l, r):
"""
Returns the smallest number m in range [l, r] such that g(m) is true.
Returns r+1 if not found.
Time Complexity: O(log(r - l) * (f(m) + g(m)))
Space Complexity: O(1)
"""
while l <= r:
m = l + (r - l) // 2
if f(m): # optional: if somehow we can determine m is the answer, return it
return m
if g(m):
r = m - 1 # new range [l, m-1]
else:
l = m + 1 # new range [m+1, r]
return l # or not found| Searching | Average | Worst | Best | Space |
|---|---|---|---|---|
| Linear Search | O(n) | O(n) | O(n) | O(1) |
| Binary Search | O(log n) | O(log n) | O(1) | O(1) |
Leetcode Problems