ASSESSMENT TASK BRIEF

Context

You are tasked with measuring and implementing an efficient sorting and searching algorithm to sort and search a large dataset of integers. The goal is to evaluate your understanding of various data structures and algorithms, as well as your ability to choose and implement an appropriate solution based on metrics.

Instructions

Assessment Tasks

This assessment has 2 Tasks:

Task 1: Python Program

Choose a sorting and a search algorithm that you believe is well-suited for the given problem. Consider factors such as time complexity, space complexity, and the characteristics of the dataset. Implement the chosen algorithms in Python and measure their performance in terms of time it takes to perform the searching and sorting tasks across datasets of 1000, 50000, 10000 and 100000 records.

Task 2: Report

You will submit a report that summarizes your choice of algorithm and data structure for searching and sorting in your application, the process you used to develop your solution, the test data sets used, along with specified metrics for the development. Run a selection of at least two search algorithms and 4 sorting algorithms, 3 from in-place sorting (such as bubble, selection and insertion) and 1 from either merge or quick sort. Document the following in your Report:

1. Overview of the chosen sorting algorithms.
2. Brief Explanation of how the algorithm works.
3. Compare the performance of the two selected search algorithms in terms of the time taken:
4. As demonstrated in class, produce Bar Graphs to showcase the comparisons. Repeat this for all the dataset of above datasets of different lengths.
5. Based on the above results, discuss which algorithm would be the best selection in terms of the fastest time. Explain why.
6. Repeat the steps (a) to (d) for the selected sorting algorithms and focus on:
   • a) Time taken
   • b) Number of Swaps
   • c) Number of Comparisons

Testing:

Create 4 datasets with varying sizes (examples: 1000, 5000, 10000, 100000) to test the efficiency of your algorithms. Include the datasets used for testing along with your submission.

NOTE – You can use ChatGPT to produce the datasets of unsorted random integers. Searching and Sorting algorithms can be generated using ChatGPT along with code to generate the comparative Bar Graphs.

IMPORTANT: Document all the prompts you used in your Report.

You are to submit the following:

1. Submit your Python code in files.
2. Submit the datasets used for testing.
3. Submit the report in a well-organized document format (Word).

Online submissions via subject Study Hub/Open Learning site.

Marking Guide

Note: This report is provided as a sample for reference purposes only. For further guidance, detailed solutions, or personalized assignment support, please contact us directly.

Sample Solution for PRO501AC – Assessment 3

Computer Science Introduction to Programming and Algorithm

This sample solution includes:

• Python program structure
• Sorting algorithms
• Searching algorithms
• Performance measurement
• Graph generation idea
• Report structure
• Reflection sample
• ChatGPT prompts documentation sample

Task 1 – Python Program

Selected Sorting Algorithms

In-Place Sorting Algorithms

1. Bubble Sort
2. Selection Sort
3. Insertion Sort

Efficient Sorting Algorithm

1. Quick Sort

Selected Searching Algorithms

1. Linear Search
2. Binary Search

Why These Algorithms?

Sample Python Code

import random
import time
import matplotlib.pyplot as plt

# -----------------------------------
# DATASET GENERATION
# -----------------------------------

sizes = [1000, 5000, 10000, 100000]

datasets = {}

for size in sizes:
    datasets[size] = random.sample(range(1, size * 10), size)

# -----------------------------------
# SORTING ALGORITHMS
# -----------------------------------

def bubble_sort(arr):
    arr = arr.copy()
    n = len(arr)

    swaps = 0
    comparisons = 0

    start = time.time()

    for i in range(n):
        for j in range(0, n - i - 1):
            comparisons += 1

            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swaps += 1

    end = time.time()

    return end - start, swaps, comparisons


def selection_sort(arr):
    arr = arr.copy()
    n = len(arr)

    swaps = 0
    comparisons = 0

    start = time.time()

    for i in range(n):
        min_idx = i

        for j in range(i + 1, n):
            comparisons += 1

            if arr[j] < arr[min_idx]:
                min_idx = j

        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        swaps += 1

    end = time.time()

    return end - start, swaps, comparisons


def insertion_sort(arr):
    arr = arr.copy()

    swaps = 0
    comparisons = 0

    start = time.time()

    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and key < arr[j]:
            comparisons += 1
            arr[j + 1] = arr[j]
            swaps += 1
            j -= 1

        arr[j + 1] = key

    end = time.time()

    return end - start, swaps, comparisons


def quick_sort(arr):

    comparisons = [0]

    def _quick_sort(items):
        if len(items) <= 1:
            return items

        pivot = items[len(items) // 2]

        left = []
        middle = []
        right = []

        for x in items:
            comparisons[0] += 1

            if x < pivot:
                left.append(x)
            elif x == pivot:
                middle.append(x)
            else:
                right.append(x)

        return _quick_sort(left) + middle + _quick_sort(right)

    start = time.time()

    sorted_arr = _quick_sort(arr.copy())

    end = time.time()

    swaps = 0

    return end - start, swaps, comparisons[0]

# -----------------------------------
# SEARCHING ALGORITHMS
# -----------------------------------

def linear_search(arr, target):

    start = time.time()

    for i in range(len(arr)):
        if arr[i] == target:
            end = time.time()
            return end - start

    end = time.time()
    return end - start


def binary_search(arr, target):

    start = time.time()

    low = 0
    high = len(arr) - 1

    while low <= high:

        mid = (low + high) // 2

        if arr[mid] == target:
            end = time.time()
            return end - start

        elif arr[mid] < target:
            low = mid + 1

        else:
            high = mid - 1

    end = time.time()
    return end - start

# -----------------------------------
# TESTING
# -----------------------------------

sorting_results = {}

for size in sizes:

    data = datasets[size]

    sorting_results[size] = {}

    sorting_results[size]["Bubble"] = bubble_sort(data)
    sorting_results[size]["Selection"] = selection_sort(data)
    sorting_results[size]["Insertion"] = insertion_sort(data)
    sorting_results[size]["Quick"] = quick_sort(data)

    print(f"\nDataset Size: {size}")

    for algo, result in sorting_results[size].items():
        print(algo, result)

# -----------------------------------
# SEARCH TESTING
# -----------------------------------

search_results = {}

for size in sizes:

    data = sorted(datasets[size])

    target = data[len(data) // 2]

    linear_time = linear_search(data, target)
    binary_time = binary_search(data, target)

    search_results[size] = {
        "Linear": linear_time,
        "Binary": binary_time
    }

# -----------------------------------
# BAR GRAPH
# -----------------------------------

quick_times = []
bubble_times = []

for size in sizes:
    bubble_times.append(sorting_results[size]["Bubble"][0])
    quick_times.append(sorting_results[size]["Quick"][0])

plt.bar([str(s) for s in sizes], bubble_times, label='Bubble')
plt.bar([str(s) for s in sizes], quick_times, label='Quick')

plt.xlabel("Dataset Size")
plt.ylabel("Time Taken")
plt.title("Sorting Algorithm Comparison")
plt.legend()

plt.show()

Sample Dataset Generation

You must also submit datasets.

Example:

import random

data_1000 = random.sample(range(1, 10000), 1000)

with open("dataset_1000.txt", "w") as file:
    for item in data_1000:
        file.write(str(item) + "\n")

Repeat for:

• 5000
• 10000
• 100000

Task 2 – Sample Report Structure

Title Page

• Subject Name
• Subject Code
• Assessment Number
• Student Name
• Student ID

Table of Contents

1. Introduction

This report evaluates the performance of various sorting and searching algorithms using Python programming. The algorithms were tested on datasets of different sizes to compare efficiency based on execution time, comparisons, and swaps.

2. Sorting Algorithms Overview

Bubble Sort

Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.

Advantages

• Easy to implement

Disadvantages

• Very slow for large datasets

Selection Sort

Selection Sort finds the minimum value and places it in the correct position.

Advantages

• Fewer swaps

Disadvantages

• High time complexity

Insertion Sort

Insertion Sort inserts elements into the correct position one by one.

Advantages

• Good for small datasets

Disadvantages

• Inefficient for large datasets

Quick Sort

Quick Sort uses divide-and-conquer strategy.

Advantages

• Very fast
• Efficient for large datasets

Disadvantages

• Recursive implementation

3. Searching Algorithms Overview

Linear Search

Checks every element one by one.

Binary Search

Repeatedly divides the sorted dataset into halves.

4. Testing Datasets

5. Results and Analysis

Sorting Time Comparison

(Add Bar Graph Screenshot)

Discussion

Quick Sort produced the fastest results because its average time complexity is:

O(nlog⁡n)O(n\log n)O(nlogn)

Bubble Sort showed the slowest performance due to:

O(n2)O(n^2)O(n2)

6. Comparison of Swaps and Comparisons

7. Best Algorithm Selection

Quick Sort was selected as the best sorting algorithm because it had:

• Lowest execution time
• Better scalability
• Efficient divide-and-conquer method

Binary Search was selected as the best searching algorithm because it performs much faster on sorted datasets.

8. Problems Encountered

• Large datasets caused Bubble Sort to execute slowly.
• Measuring accurate execution time required multiple tests.
• Managing memory usage for large datasets.

9. Reflection

This assessment improved my understanding of algorithms, time complexity, and performance analysis. I learned how different algorithms behave with large datasets and how to measure their efficiency using Python. In the future, I would improve the implementation by using advanced algorithms such as Merge Sort and Hash Searching.

10. ChatGPT Prompts Used

Example:

1. “Generate Python code for Bubble Sort with swap counting.”
2. “Create random integer datasets in Python.”
3. “Generate bar graphs using matplotlib.”
4. “Explain Quick Sort in simple words.”

Files to Submit

Python Files

• bubble_sort.py
• selection_sort.py
• insertion_sort.py
• quick_sort.py
• search_algorithms.py

Dataset Files

• dataset_1000.txt
• dataset_5000.txt
• dataset_10000.txt
• dataset_100000.txt

Report File

• PRO501AC_Assessment3_Report.docx

Final Submission

• Zip Folder containing all files

Recommended Folder Structure

PRO501AC_Assessment3/
│
├── datasets/
├── graphs/
├── python_code/
├── screenshots/
└── report/