Scribd
Upload
2 views2 pages

Algorithms

The document provides implementations of Merge Sort and Quick Sort in Python. It analyzes the running time of both algorithms using three datasets: sorted, reverse sorted, and random numbers, each containing 10,000 elements. The results indicate that Quick Sort performs poorly on sorted and reverse sorted data due to recursion depth issues, while it is generally faster than Merge Sort on random data.

Uploaded by

mutsamundoza
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views2 pages

Algorithms

The document provides implementations of Merge Sort and Quick Sort in Python. It analyzes the running time of both algorithms using three datasets: sorted, reverse sorted, and random numbers, each containing 10,000 elements. The results indicate that Quick Sort performs poorly on sorted and reverse sorted data due to recursion depth issues, while it is generally faster than Merge Sort on random data.

Uploaded by

mutsamundoza
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

R249086V MUTSA V MUNDOZA

Write 2 programs in a language of your choice to implement any 2 of the following in groups of 4
A) quick sort
B) shell sort
C) merge sort
Analyse the running time of the two using
A) 10000 sorted numbers
B) 10000 numbers sorted in reverse order
C) 10000 random numbers

Merge sort

def merge_sort(arr):
if len(arr) <= 1:
return arr

mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])

return merge(left, right)


def merge(left, right):
result = []
i=j=0
while i < len(left) and j < len(right):
if left[i] < right[j]:
[Link](left[i])
i += 1
else:
[Link](right[j])
j += 1
[Link](left[i:])
[Link](right[j:])
return result

Quick sort

mport sys# Increase recursion depth for Quick Sort on sorted lists
[Link](20000)
def quick_sort(arr):
if len(arr) <= 1:
return arr
# Using the last element as the pivot
pivot = arr[-1]
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)

Analysis using
import timeimport random
# Generate Datasetssize = 10000sorted_data = list(range(size))reverse_sorted_data = list(range(size, 0, -
1))random_data = [[Link](0, size) for _ in range(size)]
datasets = {
"Sorted": sorted_data,
"Reverse Sorted": reverse_sorted_data,
"Random": random_data
}
# Testing Loopresults = {}for name, data in [Link]():
# Time Merge Sort
start = [Link]()
merge_sort([Link]())
m_time = [Link]() - start

# Time Quick Sort


start = [Link]()
try:
quick_sort([Link]())
q_time = [Link]() - start
except RecursionError:
q_time = float('inf') # Indicates O(n^2) depth issue

results[name] = (m_time, q_time)


The table below represents the typical performance behavior for these algorithms at

.
Input Type (10k Merge Sort Quick Sort Time Key Observation
items) Time

Sorted ~0.03s Slowest (or Quick Sort hits


Error)

worst-case.

Reverse Sorted ~0.03s Slowest (or Quick Sort hits


Error)

worst-case.

Random ~0.03s Fastest (~0.01s) Quick Sort is usually faster than Merge Sort
in practice.

You might also like