[SOLVED] Cse2050 homework 7: sorting algorithms performance

4.  def bubblesort(L):
global instructions
for iteration in range(len(L) – 1):
for i in range(len(L) – 1 – iteration):
instructions += 1 # Increment for comparison
if L[i] > L[i + 1]:
L[i], L[i + 1] = L[i + 1], L[i]

def selectionsort(L):
global instructions
n = len(L)
for i in range(n – 1):
min_index = i
for j in range(i + 1, n):
instructions += 1  # Increment for comparison
if L[j] < L[min_index]:
min_index = j
L[i], L[min_index] = L[min_index], L[i]

def insertionsort(L):
global instructions
for i in range(1, len(L)):
key = L[i]
j = i – 1
while j >= 0:
instructions += 1  # Increment for comparison
if L[j] > key:
L[j + 1] = L[j]
j -= 1
else:
break
L[j + 1] = key

def merge(A, B):
global instructions
result = []
i = j = 0
while i < len(A) and j < len(B):
instructions += 1  # Increment for comparison
if A[i] < B[j]:
result.append(A[i])
i += 1
else:
result.append(B[j])
j += 1
# Extend without incrementing instructions, assuming extend isn’t a set of instructions
result.extend(A[i:])
result.extend(B[j:])
return result

def mergesort(L):
if len(L) > 1:
mid = len(L) // 2
A, B = L[:mid], L[mid:]
mergesort(A)
mergesort(B)
L[:] = merge(A, B)

def partition(L, low, high):
global instructions
pivot = L[high]
i = low – 1
for j in range(low, high):
instructions += 1  # Increment for comparison
if L[j] <= pivot:
i += 1
L[i], L[j] = L[j], L[i]
L[i + 1], L[high] = L[high], L[i + 1]
return i + 1

def quicksort(L, low, high):
if low < high:
pi = partition(L, low, high)
quicksort(L, low, pi-1)
quicksort(L, pi+1, high)

if __name__ == “__main__”:
# Test cases
test_cases = [
([], []),
([1], [1]),
([4, 2], [2, 4]),
([1, 2, 3, 4, 5], [1, 2, 3, 4, 5]),
([5, 4, 3, 2, 1], [1, 2, 3, 4, 5]),
(random.sample(range(10), 10), sorted(random.sample(range(10), 10))),
([1, 3, 2, 5, 4], [1, 2, 3, 4, 5]),
([5, 3, 1, 2, 3, 1], [1, 1, 2, 3, 3, 5]),
]

for arr, description in test_cases:
instructions = 0  # Reset the instruction count
bubblesort(arr)
print(f”{description} list instructions: {instructions}”)

“C:UsersartjsOneDrive – University of ConnecticutDocumentsSpring 24CSE 2050cse2050hw7.venvScriptspython.exe” “C:UsersartjsOneDrive – University of ConnecticutDocumentsSpring 24CSE 2050cse2050hw7HW7.py”

[] list instructions: 0

[1] list instructions: 0

[2, 4] list instructions: 1

[1, 2, 3, 4, 5] list instructions: 10

[1, 2, 3, 4, 5] list instructions: 10

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] list instructions: 45

[1, 2, 3, 4, 5] list instructions: 10

[1, 1, 2, 3, 3, 5] list instructions: 15

Process finished with exit code 0

7.  def bubblesort(L):
global instructions
n = len(L)
keepgoing = True
while keepgoing:
keepgoing = False
for i in range(n-1):
instructions += 1  # Increment for comparison
if L[i] > L[i+1]:
L[i], L[i+1] = L[i+1], L[i]
instructions += 3  # Increment for swap
keepgoing = True
n -= 18.  if __name__ == “__main__”:
# Test cases
test_cases = [
([], []),
([1], [1]),
([4, 2], [2, 4]),
([1, 2, 3, 4, 5], [1, 2, 3, 4, 5]),
([5, 4, 3, 2, 1], [1, 2, 3, 4, 5]),
(random.sample(range(10), 10), sorted(random.sample(range(10), 10))),
([1, 3, 2, 5, 4], [1, 2, 3, 4, 5]),
([5, 3, 1, 2, 3, 1], [1, 1, 2, 3, 3, 5]),
]

for arr, description in test_cases:
instructions = 0  # Reset the instruction count
bubblesort(arr)
print(f”{description} list instructions: {instructions}”)9.  [] list instructions: 010.[1] list instructions: 011.[2, 4] list instructions: 412.[1, 2, 3, 4, 5] list instructions: 413.[1, 2, 3, 4, 5] list instructions: 4014.[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] list instructions: 13515.[1, 2, 3, 4, 5] list instructions: 1316.[1, 1, 2, 3, 3, 5] list instructions: 45

def cocktailsort(L):
global instructions
n = len(L)
swapped = True
start = 0
end = n – 1
while swapped:
swapped = False
# Move larger elements to the end
for i in range(start, end):
instructions += 1  # Increment for comparison
if L[i] > L[i + 1]:
L[i], L[i + 1] = L[i + 1], L[i]
instructions += 3  # Increment for swap
swapped = True
if not swapped:
break
swapped = False
end -= 1
for i in range(end – 1, start – 1, -1):
instructions += 1  # Increment for comparison
if L[i] > L[i + 1]:
L[i], L[i + 1] = L[i + 1], L[i]
instructions += 3  # Increment for swap
swapped = True
start += 1if __name__ == “__main__”:
# Test cases
test_cases = [
([], []),
([1], [1]),
([4, 2], [2, 4]),
([1, 2, 3, 4, 5], [1, 2, 3, 4, 5]),
([5, 4, 3, 2, 1], [1, 2, 3, 4, 5]),
(random.sample(range(10), 10), sorted(random.sample(range(10), 10))),
([1, 3, 2, 5, 4], [1, 2, 3, 4, 5]),
([5, 3, 1, 2, 3, 1], [1, 1, 2, 3, 3, 5]),
]

for arr, description in test_cases:
instructions = 0  # Reset the instruction count
# bubblesort(arr)
# print(f”{description} list instructions: {instructions}”)
cocktailsort(arr)
print(f”{description} list instructions: {instructions}”)

“C:UsersartjsOneDrive – University of ConnecticutDocumentsSpring 24CSE 2050cse2050hw7.venvScriptspython.exe” “C:UsersartjsOneDrive – University of ConnecticutDocumentsSpring 24CSE 2050cse2050hw7invariant.py”

import unittest
import random
from HW7 import bubblesort, selectionsort, insertionsort, mergesort, quicksort

class TestSortingAlgorithms(unittest.TestCase):
global instructions

def setUp(self):
# Reset instructions count before each test
self.instructions = 0

def test_bubblesort(self):
self.run_sort_tests(bubblesort)

def test_selectionsort(self):
self.run_sort_tests(selectionsort)

def test_insertionsort(self):
self.run_sort_tests(insertionsort)

def test_mergesort(self):
self.run_sort_tests(mergesort)

def test_quicksort(self):
# Test cases for quicksort
test_cases = [
([], []),
([1], [1]),
([4, 2], [2, 4]),
([1, 2, 3, 4, 5], [1, 2, 3, 4, 5]),
([5, 4, 3, 2, 1], [1, 2, 3, 4, 5]),
(random.sample(range(10), 10), sorted(random.sample(range(10), 10))),
([1, 3, 2, 5, 4], [1, 2, 3, 4, 5]),
([5, 3, 1, 2, 3, 1], [1, 1, 2, 3, 3, 5]),
]
for arr, expected in test_cases:
self.instructions = 0
quicksort(arr, 0, len(arr) – 1)
self.assertEqual(arr, expected)

def run_sort_tests(self, sort_func):
test_cases = [
([], []),
([1], [1]),
([4, 2], [2, 4]),
([1, 2, 3, 4, 5], [1, 2, 3, 4, 5]),
([5, 4, 3, 2, 1], [1, 2, 3, 4, 5]),
(random.sample(range(10), 10), sorted(random.sample(range(10), 10))),
([1, 3, 2, 5, 4], [1, 2, 3, 4, 5]),
([5, 3, 1, 2, 3, 1], [1, 1, 2, 3, 3, 5]),
]

for original, expected in test_cases:
arr = original[:]  # Make a copy of the array to sort
if sort_func == quicksort:
sort_func(arr, 0, len(arr) – 1)
else:
sort_func(arr)
self.assertEqual(arr, expected)

if __name__ == ‘__main__’:
unittest.main()