ASSIGNMENT 17

1. Bubble Sort

Bubble Sort is the simplest sorting algorithm. It repeatedly compares adjacent elements and swaps them if they are in the wrong order.

How it works:

• Compare adjacent elements
• Swap if needed
• Repeat until sorted

CODE:

def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr

1. Selection Sort

Selection Sort selects the smallest element from the unsorted part and places it at the beginning.

How it works:

• Find minimum element
• Swap with first unsorted element
• Repeat

CODE:

def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i] return arr

1. Insertion Sort

Insertion Sort builds the sorted array one element at a time.

How it works:

• Pick element
• Insert it into correct position

CODE:

def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr

1. Merge Sort

Merge Sort uses the divide and conquer approach.

How it works:

• Divide array into halves
• Sort each half
• Merge sorted halves

CODE:

`def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
merge_sort(left)
merge_sort(right)
i = j = k = 0

 while i < len(left) and j < len(right): 
     if left[i] < right[j]:
          arr[k] = left[i] 
          i += 1 
     else: 
          arr[k] = right[j] 
          j += 1 
     k += 1
     while i < len(left):
          arr[k] = left[i] 
          i += 1 
          k += 1 
     while j < len(right): 
           arr[k] = right[j] 
           j += 1 
           k += 1 
 return arr`

1. Quick Sort

Quick Sort is one of the fastest sorting algorithms in practice.

How it works:

• Choose a pivot
• Partition array
• Recursively sort

CODE:

`def quick_sort(arr):
if len(arr) <= 1:
return arr

pivot = arr[0]  # choosing first element as pivot
left = [x for x in arr[1:] if x <= pivot]
right = [x for x in arr[1:] if x > pivot]

return quick_sort(left) + [pivot] + quick_sort(right)`

Complexity Analysis

Algorithm Time Complexiy Space
Bubble Sort O(n²) O(1)
Selection Sort O(n²) O(1)
Insertion Sort O(n²) O(1)
Merge Sort O(n log n) O(n)
Quick Sort O(n log n) O(log n)

Conclusion

Sorting algorithms are essential tools in data structures, each designed with a unique strategy to organize data efficiently. While simpler algorithms like Bubble Sort help in understanding basic concepts, advanced methods like Merge Sort and Quick Sort provide optimal performance for large datasets.