CSCI 3212 Lab 2

Due Sunday, 02/11/2024, 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. Submission Guide

  • Each student only submits one file, lab_1_lastname.zip (file size less than 5 M), including

    1. A Code folder for your Java code files, including all the programming tasks mentioned above.

    2. Notes_lab_2_lastname.pdf for your notes, including all the writing tasks mentioned above.

3. Notes

  • Submit your zip file for lab 2 to Blackboard.

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