CSCI 3212 Lab 2

Due Sunday, 09/14/2025, by midnight (23:59, EST), on Blackboard

Announcements

1. Quick Sort and Merge Sort

  • Objective:

Students will gain hands-on experience in implementing, analyzing, and comparing the Quick Sort and Merge Sort algorithms. By the end of the lab, students should understand the mechanisms, efficiencies, and differences between these two sorting techniques.

1.1. Pre-Lab Requirements:

  • Review the concepts of divide-and-conquer algorithms.

  • Understand the time complexity analysis for average, best, and worst-case scenarios.

  • Familiarize with the concept of recursion and how it applies to sorting algorithms.

1.2. Part 1: Quick Sort Implementation

  • Task: Implement the Quick Sort algorithm in Java

    1. Choose a pivot element from the array (you can explore different strategies: first element, last element, median, etc.).

    2. Partition the array into two parts such that elements less than the pivot are on the left, and elements greater than the pivot are on the right.

    3. Recursively apply the same logic to the left and right partitions.

  • Experiment:

    1. Modify your Quick Sort to include different pivot selection strategies. Compare their performances by sorting arrays of varying sizes and distributions (random, nearly sorted, reversed).

  • Questions:

    1. How does the choice of pivot affect the performance of Quick Sort?

    2. What is the worst-case time complexity of Quick Sort, and when does it occur?

1.3. Part 2: Merge Sort Implementation

  • Task: Implement the Merge Sort algorithm in Java

    1. Divide the array into halves until you have subarrays of size 1.

    2. Merge the subarrays to produce new sorted subarrays until the whole array is merged back and sorted.

  • Experiment:

    1. Analyze the space complexity of Merge Sort by tracking the memory usage during the execution of your implementation.

  • Questions:

    1. How does Merge Sort ensure stability in sorting?

    2. Compare the time complexity of Merge Sort in the worst and best cases. Is there a difference?

1.4. Part 3: Comparative Analysis

  • Task: Develop a comparative analysis of Quick Sort and Merge Sort.

    1. Create a table or graph comparing the execution times of both sorting algorithms across different array sizes and types.

    2. Partition the array into two parts such that elements less than the pivot are on the left, and elements greater than the pivot are on the right.

    3. Recursively apply the same logic to the left and right partitions.

  • Experiment:

    1. Implement a hybrid sorting algorithm that uses Quick Sort for larger subarrays and switches to another simpler sorting algorithm (like Insertion Sort) for smaller subarrays. Determine the optimal threshold for switching.

  • Questions:

    1. In what scenarios might Merge Sort be preferred over Quick Sort, and vice versa?

    2. How does the hybrid sorting approach improve the performance of Quick Sort?

1.5. Lab Report:

  • Students should submit a lab report that includes:

    1. Source code for all implemented algorithms.

    2. A brief description of each algorithm’s implementation.

    3. Comparative analysis results with discussion.

    4. Answers to all the questions listed above.

    5. Reflection on what was learned and any challenges encountered.

1.6. Resources:

  • Divide-and-Conquer Strategy

    1. Divide-and-conquer is an algorithm design paradigm that involves three main steps:

    2. Divide: The problem is divided into smaller subproblems that are similar to the original problem but simpler to solve.

    3. Conquer: The subproblems are solved recursively. If they are simple enough, they may be solved directly.

    4. Combine: The solutions to the subproblems are then combined to give a solution to the original problem.

2. Implementation & Submission Details

  • File layout & name:

    1. Put all code for this lab in a single Java source file named exactly: SortingComparison.java.

    2. Do not include any package declarations.

  • Required structure:

    1. Implement QuickSort and MergeSort as methods inside SortingComparison.java.

    2. For QuickSort, include separate methods for each pivot selection strategy.

    3. Provide a main(String[] args) method that constructs test inputs and calls each algorithm.

  • Test cases:

    1. Include both edge cases (empty array, single element, already sorted, reverse sorted, duplicates).

    2. Include general cases (arrays with mixed values).

  • Program output:

    1. Print the unsorted input array.

    2. Print the algorithm names (QuickSort with pivot choice, MergeSort).

    3. Print the sorted result for each algorithm.

    4. Print the time cost of each algorithm.

  • How we will compile and run your program:

    1. javac SortingComparison.java

    2. java SortingComparison

3. Submission Guide

  • Each student only submits one file: lab_2_lastname.zip (file size less than 5 MB), including

    1. A Code folder containing your Java source file(s) for all programming tasks described above.

    2. Notes_lab_2_lastname.pdf with all required notes and writing tasks.

  • Important rules:

    1. Do not include .class files or any compiled artifacts in your submission.

  • Submit your zip file for lab 2 to Blackboard.

  • Lab assignments will typically be due by midnight on Sunday.