You've learned this already. ✅
Click here to view the next lesson.
Chapter 4: The Art of Sorting
Chapter 4: Practical Exercises of The Art of Sorting
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 arrExercise 2: Time It!
- Using Python's
timeitmodule, measure the time taken for each of the above sorting functions to sort a list of 1000 random numbers. Which is the fastest for this input size?
Hint: You can generate a list of 1000 random numbers using: import random; nums = [random.randint(1, 10000) for _ in range(1000)].
Exercise 3: Implement Advanced Sorts
- Write Python functions for QuickSort, MergeSort, and HeapSort.
- Test each function using the list:
[64, 34, 25, 12, 22, 11, 90]
Solution:
# QuickSort
def quickSort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quickSort(left) + middle + quickSort(right)
# MergeSort
def mergeSort(arr):
if len(arr) > 1:
mid = len(arr)//2
L = arr[:mid]
R = arr[mid:]
mergeSort(L)
mergeSort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
return arr
# For HeapSort, you'll need to implement or use a heap data structure.Exercise 4: Sorting Strings
- Using any of the sorting algorithms you've learned, write a function that sorts a list of strings based on their length. If two strings have the same length, sort them lexicographically.
Hint: You can modify the comparison criteria in the sorting functions to achieve this.
These exercises should provide you with a comprehensive practice experience for this chapter.
Chapter 4: Practical Exercises of The Art of Sorting
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 arrExercise 2: Time It!
- Using Python's
timeitmodule, measure the time taken for each of the above sorting functions to sort a list of 1000 random numbers. Which is the fastest for this input size?
Hint: You can generate a list of 1000 random numbers using: import random; nums = [random.randint(1, 10000) for _ in range(1000)].
Exercise 3: Implement Advanced Sorts
- Write Python functions for QuickSort, MergeSort, and HeapSort.
- Test each function using the list:
[64, 34, 25, 12, 22, 11, 90]
Solution:
# QuickSort
def quickSort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quickSort(left) + middle + quickSort(right)
# MergeSort
def mergeSort(arr):
if len(arr) > 1:
mid = len(arr)//2
L = arr[:mid]
R = arr[mid:]
mergeSort(L)
mergeSort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
return arr
# For HeapSort, you'll need to implement or use a heap data structure.Exercise 4: Sorting Strings
- Using any of the sorting algorithms you've learned, write a function that sorts a list of strings based on their length. If two strings have the same length, sort them lexicographically.
Hint: You can modify the comparison criteria in the sorting functions to achieve this.
These exercises should provide you with a comprehensive practice experience for this chapter.
Chapter 4: Practical Exercises of The Art of Sorting
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 arrExercise 2: Time It!
- Using Python's
timeitmodule, measure the time taken for each of the above sorting functions to sort a list of 1000 random numbers. Which is the fastest for this input size?
Hint: You can generate a list of 1000 random numbers using: import random; nums = [random.randint(1, 10000) for _ in range(1000)].
Exercise 3: Implement Advanced Sorts
- Write Python functions for QuickSort, MergeSort, and HeapSort.
- Test each function using the list:
[64, 34, 25, 12, 22, 11, 90]
Solution:
# QuickSort
def quickSort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quickSort(left) + middle + quickSort(right)
# MergeSort
def mergeSort(arr):
if len(arr) > 1:
mid = len(arr)//2
L = arr[:mid]
R = arr[mid:]
mergeSort(L)
mergeSort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
return arr
# For HeapSort, you'll need to implement or use a heap data structure.Exercise 4: Sorting Strings
- Using any of the sorting algorithms you've learned, write a function that sorts a list of strings based on their length. If two strings have the same length, sort them lexicographically.
Hint: You can modify the comparison criteria in the sorting functions to achieve this.
These exercises should provide you with a comprehensive practice experience for this chapter.
Chapter 4: Practical Exercises of The Art of Sorting
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 arrExercise 2: Time It!
- Using Python's
timeitmodule, measure the time taken for each of the above sorting functions to sort a list of 1000 random numbers. Which is the fastest for this input size?
Hint: You can generate a list of 1000 random numbers using: import random; nums = [random.randint(1, 10000) for _ in range(1000)].
Exercise 3: Implement Advanced Sorts
- Write Python functions for QuickSort, MergeSort, and HeapSort.
- Test each function using the list:
[64, 34, 25, 12, 22, 11, 90]
Solution:
# QuickSort
def quickSort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quickSort(left) + middle + quickSort(right)
# MergeSort
def mergeSort(arr):
if len(arr) > 1:
mid = len(arr)//2
L = arr[:mid]
R = arr[mid:]
mergeSort(L)
mergeSort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
return arr
# For HeapSort, you'll need to implement or use a heap data structure.Exercise 4: Sorting Strings
- Using any of the sorting algorithms you've learned, write a function that sorts a list of strings based on their length. If two strings have the same length, sort them lexicographically.
Hint: You can modify the comparison criteria in the sorting functions to achieve this.
These exercises should provide you with a comprehensive practice experience for this chapter.