#Hack 1
import time
import random
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]
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left, right = arr[:mid], 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
# Generate data
data = [random.randint(1, 1000) for _ in range(100)]
# Time Bubble Sort
start = time.time()
bubble_sort(data.copy())
t_bubble = time.time() - start
# Time Merge Sort
start = time.time()
merge_sort(data.copy())
t_merge = time.time() - start
print(f"Bubble Sort: {t_bubble:.6f}s")
print(f"Merge Sort: {t_merge:.6f}s")
print("Faster algorithm:", "Merge Sort" if t_merge < t_bubble else "Bubble Sort")
# Which is faster?
# Merge Sort on nearly any non-trivial input.
# Why does Merge Sort consistently outperform Bubble Sort?
# Merge Sort runs in O(n log n) by recursively dividing and merging, whereas Bubble Sort runs in O(n²) by repeated adjacent swaps, so for larger n its quadratic growth makes it much slower.
Bubble Sort: 0.001620s
Merge Sort: 0.000910s
Faster algorithm: Merge Sort
#Hack 2
import random
def linear_search(arr, target):
count = 0
for x in arr:
count += 1
if x == target:
return count
return count
def binary_search(arr, target):
left, right, count = 0, len(arr) - 1, 0
while left <= right:
count += 1
mid = (left + right) // 2
if arr[mid] == target:
return count
if arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return count
# Prepare data
arr = list(range(1, 100001))
target = random.choice(arr)
# Run searches
lin_comps = linear_search(arr, target)
bin_comps = binary_search(arr, target)
print(f"Linear Search comparisons: {lin_comps}")
print(f"Binary Search comparisons: {bin_comps}")
# Which search is faster, and why?
# Binary Search is faster (O(log n) vs. O(n)) because it halves the search interval each comparison instead of scanning each element.
# What happens on an unsorted list?
# Binary Search fails (wrong result) or must first sort (O(n log n)), making Linear Search the only correct O(n) option on arbitrary data.
# Popcorn Hack 1 – The Even/Odd Check Challenge
# Chosen options:
# Use the modulus operator (n % 2 == 0).
# Check if the last digit is one of {0, 2, 4, 6, 8}.
# Both run in constant time, O(1), with a single arithmetic or digit‐check operation each, whereas every other method either loops, converts to a string, or builds extra data.