Bubble sort

Logic: Adjacent elements are compared and sorted

Increment
Comparing Swapping counter

Compare the Swap the Increment

first two elements to the counter
adjacent sort them (if by 1
elements required)
BUBBLE SORT

def bubble_sort(arr):

for i in range(len(arr)):

for j in range(0, len(arr) - i - 1):

if arr[j] > arr[j+1]:

# Swap their positions

arr[j], arr[j+1] = arr[j+1], arr[j]
Time Complexity
return arr
Best Average Worst

O(n) O(n²) O(n²)

Space Complexity

O(1) O(1) O(1)

Selection sort
Logic: Array is considered into two parts (Sorted and Unsorted
Initially array is unsorted
Increment
Selection Swapping counter

Select the Bring it to the Increment the

lowest element starting counter for
in the position unsorted array
remaining by 1
array
 SELECTION SORT
def selection_sort(arr):
n = len(arr)

for i in range(n):
# Assume the first unsorted element is the
minimum
min_index = i

# Look for a smaller element in the remaining

list
for j in range(i+1, n):
if arr[j] < arr[min_index]:
Time Complexity
min_index = j # update the index of the
smallest ele Best Average Worst

O(n²) O(n²) O(n²)

# Swap the found minimum with the first
unsorted ele Space Complexity
arr[i], arr[min_index] = arr[min_index], arr[i]
O(1) O(1) O(1)
return arr
Insertion sort
Logic: Pick the unsorted element and shift it in position with
the sorted elements

Swapping and Increment

Selecting Shifting marker

Select the Swap other Increment

first unsorted elements to the marker to
element the right to the right by 1
create the
correct
position and
shift the
unsorted
element
 INSERTION SORT

def insertion_sort(arr):
n = len(arr)

# Start from the second element (first is already "sorted")

for i in range(1, n):
key = arr[i] # current element to insert
j=i-1

# Move elements that are greater than key one position

to the right Time Complexity
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j] Best Average Worst
j -= 1
O(n) O(n²) O(n²)

# Place key in its correct position Space Complexity

arr[j+1] = key
O(1) O(1) O(1)
return arr
Heap sort
Logic: Create a Max heap. Swap the root with last element. Repea
the process

Create Max Swap and Remove Repeat

heap Delete
Create a Swap the Remove the
Max heap root and last swapped
with the leaf node. root node
given data (i.e. the
current last
leaf node)
HEAP SORT

def heap_sort(arr):
n = len(arr)

# Step 1: Turn the array into a max heap

build_max_heap(arr) Time Complexity

# Step 2: Repeatedly take out the max Best Average Worst

for end in range(n-1, 0, -1):
O(n log n) O(n log n) O(n log n)
# Swap the root (largest) with the last
element
Space Complexity
arr[0], arr[end] = arr[end], arr[0]
O(1) O(1) O(1)
# Shrink the heap (ignore last element now
sorted)
fix_heap(arr, 0, end)

return arr
Merge sort
Logic: Divide and Conquer. Divide input array into halves call its
For the two halves and merge the two halves
Merge the
Divide Array into Reorder halves
halves
Keep dividing Reorder Merge the
the array into elements one individual
individual by one in halves to form
elements halves the sorted
array
MERGE SORT
def merge_sort(arr):
# Base case: list of size 1 is already
sorted def merge(left, right):
if len(arr) <= 1: result = []
return arr i, j = 0, 0

# Step 1: Divide the list into two # Compare elements from left and right, pick smaller
halves each time
mid = len(arr) // 2 while i < len(left) and j < len(right):
left_half = arr[:mid] if left[i] <= right[j]:
right_half = arr[mid:] [Link](left[i])
i += 1
# Step 2: Recursively sort both else:
halves [Link](right[j])
left_sorted = merge_sort(left_half) j += 1
right_sorted =
merge_sort(right_half) # Copy any remaining elements
Time Complexity
[Link](left[i:])
# Step 3: Merge the two sorted [Link](right[j:]) Best Average Worst
halves return result
return merge(left_sorted, O(n log n) O(n log n) O(n log n)
right_sorted)
Space Complexity

O(n) O(n) O(n)

Quick sort
Logic: Divide and Conquer. Pick an element as pivot such that
elements on left are smaller than on the right, and partition the
array around the pivot.

Divide Array into Quick sort the right

halves around a Quick sort left half half
Pivot
Choose a pivot Recursively sort Recursively sort
such that left the left half the right half
half is smaller
than right half
QUICK SORT
def quick_sort(arr):
# Base case: list of size 0 or 1 is already sorted
if len(arr) <= 1:
return arr

# Step 1: Choose a pivot (for simplicity, take the first

element)
pivot = arr[0]

# Step 2: Partition the array into two groups

left = [x for x in arr[0] if x <= pivot] # smaller or
equal
right = [x for x in arr[0] if x > pivot] # larger
Time Complexity
# Step 3: Recursively sort the two halves Best Average Worst
return quick_sort(left) + [pivot] + quick_sort(right)
O(n log n) O(n log n) O(n²)

Space Complexity

O(log n) O(log n) O(log n)