Algorithms and Data Structures with Python

Practical Exercises: Chapter 4

Exercise 1: Implement Basic Sorts

• Write Python functions for Bubble Sort, Selection Sort, and Insertion Sort.
• Test each function using the list: [64, 34, 25, 12, 22, 11, 90]

Solution:

# Bubble Sort

def bubbleSort(arr):

n = len(arr)

for i in range(n-1):

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

 

# Selection Sort

def selectionSort(arr):

for i in range(len(arr)):

min_idx = i

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

if arr[min_idx] > arr[j]:

min_idx = j

arr[i], arr[min_idx] = arr[min_idx], arr[i]

return arr

 

# Insertion Sort

def insertionSort(arr):

for i in range(1, len(arr)):

key = arr[i]

j = i-1

while j >=0 and key < arr[j]:

arr[j+1] = arr[j]

j -= 1

arr[j+1] = key

return arr ...