الكود كامل مع عداد المقارنات (اسفله يوجد الكود بدون العداد)
import time
import random
import sys
# ---------------------------------------------------------
# Student Info [cite: 15-18]
# ---------------------------------------------------------
# Student Name:
# ID:
# Group#:
# ---------------------------------------------------------
comparisons = 0
swaps = 0
# ==========================================
# 1. Quicksort Implementation [cite: 53-73]
# ==========================================
def partition(arr, left, right):
global swaps, comparisons
pivot = arr[left] # Choose first element as pivot [cite: 62]
i = left
for j in range(left + 1, right + 1):
comparisons += 1
if arr[j] < pivot:
i += 1
swaps += 1
arr[i], arr[j] = arr[j], arr[i]
# Place pivot in correct position
swaps += 1
arr[left], arr[i] = arr[i], arr[left]
return i
def quicksort(arr, left = None, right = None):
global swaps, comparisons
if left is None:
left = 0
if right is None:
right = len(arr) - 1
comparisons += 1
if left < right:
p = partition(arr, left, right)
quicksort(arr, left, p - 1)
quicksort(arr, p + 1, right)
return arr
def heapify(arr, n, i):
global swaps, comparisons
largest = i
left = 2 * i + 1
right = 2 * i + 2
# Check left child
comparisons += 2
if left < n and arr[left] > arr[largest]:
largest = left
# Check right child
comparisons += 2
if right < n and arr[right] > arr[largest]:
largest = right
# Swap and continue heapifying if root is not largest
comparisons += 1
if largest != i:
swaps += 1
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapsort(arr):
global swaps, comparisons
n = len(arr)
# Build a Max Heap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract elements one by one
for end in range(n - 1, 0, -1):
swaps += 1
arr[0], arr[end] = arr[end], arr[0]
heapify(arr, end, 0)
return arr
def merge(left, right):
global swaps, comparisons
result = []
i = j = 0
comparisons += 2
while i < len(left) and j < len(right):
comparisons += 1
if left[i] < right[j]:
swaps += 1
result.append(left[i])
i += 1
else:
swaps += 1
result.append(right[j])
j += 1
swaps += len(left[i:])
result.extend(left[i:])
swaps += len(right[j:])
result.extend(right[j:])
return result
def merge_sort(arr):
global swaps, comparisons
comparisons += 1
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
sorted_left = merge_sort(left_half)
sorted_right = merge_sort(right_half)
return merge(sorted_left, sorted_right)
def selection_sort(arr):
global swaps, comparisons
n = len(arr)
for i in range(n):
min_index = i
for j in range(i + 1, n):
comparisons += 1
if arr[j] < arr[min_index]:
min_index = j
swaps += 1
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
def insertion_sort(arr):
global swaps, comparisons
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
comparisons += 2
while j >= 0 and arr[j] > key:
swaps += 1
arr[j + 1] = arr[j]
j -= 1
swaps += 1
arr[j + 1] = key
return arr
def compare_sorts(arr: list):
global swaps, comparisons
algorithms = [quicksort, heapsort, merge_sort, selection_sort, insertion_sort]
for algorithm in algorithms:
swaps = 0
comparisons = 0
copy = arr.copy()
start = time.time()
sorted = algorithm(copy)
end = time.time()
print(f"{algorithm.__name__:<15} {(end - start) * 1000:<10.5f} {sorted} comparisons: {comparisons}, swaps: {swaps}")
a = [12, 5, 9, 1, 14, 3, 7]
compare_sorts(a)
الكود كامل بدون عداد المقارنات:
import time
import random
import sys
# ---------------------------------------------------------
# Student Info [cite: 15-18]
# ---------------------------------------------------------
# Student Name:
# ID:
# Group#:
# ---------------------------------------------------------
# ==========================================
# 1. Quicksort Implementation [cite: 53-73]
# ==========================================
def partition(arr, left, right):
pivot = arr[left] # Choose first element as pivot [cite: 62]
i = left
for j in range(left + 1, right + 1):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
# Place pivot in correct position
arr[left], arr[i] = arr[i], arr[left]
return i
def quicksort(arr, left, right):
if left < right:
p = partition(arr, left, right)
quicksort(arr, left, p - 1)
quicksort(arr, p + 1, right)
# ==========================================
# 2. Heap Sort Implementation [cite: 113-160]
# ==========================================
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
# Check left child
if left < n and arr[left] > arr[largest]:
largest = left
# Check right child
if right < n and arr[right] > arr[largest]:
largest = right
# Swap and continue heapifying if root is not largest
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapsort(arr):
n = len(arr)
# Build a Max Heap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract elements one by one
for end in range(n - 1, 0, -1):
arr[0], arr[end] = arr[end], arr[0]
heapify(arr, end, 0)
# ==========================================
# 3. Merge Sort Implementation [cite: 192-236]
# ==========================================
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
sorted_left = merge_sort(left_half)
sorted_right = merge_sort(right_half)
return merge(sorted_left, sorted_right)
# ==========================================
# 4. Selection Sort Implementation [cite: 274-292]
# ==========================================
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]
# ==========================================
# 5. Insertion Sort Implementation [cite: 326-343]
# ==========================================
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
# ==========================================
# Q3: Coding Challenge - Compare Sorts [cite: 390-393]
# ==========================================
def compare_sorts(arr):
# Dictionary to store results
results = {}
# List of algorithms and their function calls
# Note: We copy the array each time so one sort doesn't affect the next
# 1. Quicksort
test_arr = arr.copy()
start = time.time()
quicksort(test_arr, 0, len(test_arr) - 1)
end = time.time()
results['Quicksort'] = end - start
# 2. Heap Sort
test_arr = arr.copy()
start = time.time()
heapsort(test_arr)
end = time.time()
results['Heap Sort'] = end - start
# 3. Merge Sort
test_arr = arr.copy()
start = time.time()
merge_sort(test_arr) # Merge sort returns a new list
end = time.time()
results['Merge Sort'] = end - start
# 4. Selection Sort
test_arr = arr.copy()
start = time.time()
selection_sort(test_arr)
end = time.time()
results['Selection Sort'] = end - start
# 5. Insertion Sort
test_arr = arr.copy()
start = time.time()
insertion_sort(test_arr)
end = time.time()
results['Insertion Sort'] = end - start
return results
# ==========================================
# Main Execution Block
# ==========================================
if __name__ == "__main__":
# Test array from Take-Home Exercise Q1 [cite: 384]
sample_array = [12, 5, 9, 1, 14, 3, 7]
print(f"Original Array: {sample_array}\n")
# Verify algorithms independently
arr_quick = sample_array.copy()
quicksort(arr_quick, 0, len(arr_quick)-1)
print(f"Quicksort Result: {arr_quick}")
arr_heap = sample_array.copy()
heapsort(arr_heap)
print(f"Heapsort Result: {arr_heap}")
arr_merge = merge_sort(sample_array.copy())
print(f"Mergesort Result: {arr_merge}")
arr_sel = sample_array.copy()
selection_sort(arr_sel)
print(f"Selection Result: {arr_sel}")
arr_ins = sample_array.copy()
insertion_sort(arr_ins)
print(f"Insertion Result: {arr_ins}")
print("-" * 30)
# Run Comparison (Q3)
# Using a slightly larger random array to make time differences visible
# as the sample array is too small to register significant time differences.
random_array = [random.randint(1, 1000) for _ in range(1000)]
print("\nRunning performance comparison on 1,000 random integers:")
performance = compare_sorts(random_array)
for algo, t in performance.items():
print(f"{algo}: {t:.6f} seconds")
التتبع كامل: https://claude.ai/public/artifacts/9cdd4c0c-d496-4ff1-b026-7869c3ade714