CompSci Notes MON 4/27

Introduction

• Morning attendance check discussed.

Overview of Sorting Algorithms

• Previous discussion on three quadratic sorting algorithms:
    - Selection Sort
    - Insertion Sort
    - Bubble Sort

• These algorithms are intuitive and easy to understand but are quadratic in nature, making them inefficient for larger input sizes.

Quadratic Sorting Algorithms

• All three quadratic algorithms exhibit worst-case time complexities of:
    - Selection sort: Always quadratic
    - Insertion sort: Quadratic in the worst case
    - Bubble sort: Quadratic in the worst case

• Due to their quadratic complexity, these algorithms are considered slow for large datasets.

Divide and Conquer Algorithms

• To improve efficiency for larger input sizes, divide and conquer algorithms are employed.

• Focus on discussing Merge Sort and possibly Quick Sort (though Quick Sort won't be on the exam).

Merge Sort Fundamentals

• Merge Sort is characterized as a divide and conquer algorithm involving recursion.

• Fundamental steps of Merge Sort:
    1. Base Case: If the portion of the list to be sorted has less than two items, it is sorted:
       - For one item, it is inherently sorted.
       - For zero items, there is nothing to sort.
    2. Recursive Division: Divide the list into two halves and recursively sort each half.
    3. Merging: Merge the two sorted halves back into a single sorted array.

Merging Process

• The merge step consolidates the two sorted lists into one sorted list. The necessary components for the merge process include:
    - Original data array
    - Temporary array to hold sorted elements during merging.
  

Parameters for Merge Method

• Data array to be merged.

• Index where the first half begins.

• Number of elements in the first half.

• Number of elements in the second half.

Efficient Merging Strategy

• When merging, three indices are maintained:
    1. First index for the first half of the array.
    2. Second index for the second half of the array.
    3. Index for the temporary array storing the sorted result.

• Elements are compared and the smaller one is placed into the temporary array.

• When one half of the array is exhausted, the remaining elements from the other half are copied directly to the temporary array.

• The data from the temporary array is then copied back into the original data array.

Recursion and Its Complexity in Merge Sort

• Merge Sort recursively splits the array, generating a recursion tree which visualizes the division. Each level of the tree corresponds to a stage in the sorting process.

• Upon reaching the base case, the recursive calls propagate back up, merging the results at each level until the entire array is recombined and sorted.

Analyzing Time Complexity

• Time Complexity Breakdown:
    - The runtime at each level of recursion for merging is linear, approximately O(n) for the merge step.
    - There are multiple levels in recursion. When analyzing:
        - At each recursion level, you are always processing n elements.
        - The height of the recursion tree, with elements being halved at each step, is log₂(n).
    - Therefore, the overall time complexity is given by:
      $O(n imes ext{log}_2(n))$

Conclusion and Exam Notes

• The semester's material covered Merge Sort in depth, including theoretical aspects and practical complexities.

• Next session would be review, followed by the exam, which is not scheduled to cover Merge Sort specifically but focuses on quadratic sorting algorithms.

Additional Tasks and Homework

• Assignment involves tracing the three quadratic sorting algorithms: Selection sort, Insertion sort, and Bubble sort, with reference to class slides.

• Encouragement to finish the assignment early for submission by Wednesday.

Class Logistics

• Class ended with reminders for submitting assignments and upcoming exam information.