ICQ5-Sorting Algorithms (1)

CSCI 3230A Data Structures - Fall 2024 In-class Quiz Notes

Quiz Structure

  • Title: CSCI 3230A Data Structures - Fall 2024 In-class Quiz

  • Total Points: 10

  • Time Duration: 30 minutes

  • Instructions:

    • No Resources Allowed: Candidates must rely on their understanding and preparation.

    • No Collaboration: Each participant must work independently without assistance from peers.

    • MCQ Selection Must Be Unambiguous: Ensure clarity in options to avoid confusion during the quiz.

Quiz Content

Questions Overview

  • Q1: Identifying AlgorithmsQuestion: Which algorithm uses divide and conquer for sorting an array of 10 integers?Options:(a) Insertion Sort(b) Bubble Sort(c) Selection Sort(d) None of these

  • Q2: Advantages of Bubble SortQuestion: Which is an advantage of Bubble Sort compared to Insertion Sort and Selection Sort?Options:(a) Always better time complexity(b) Can detect if the array is already sorted(c) It is a stable sorting algorithm(d) All of the options above

  • Q3: True or False Questions(a) Average case run time of Insertion Sort is O(log n).(b) Before performing Selection Sort, the data must be arranged in ascending order.

  • Q4: Favorite Sorting Algorithm WalkthroughTask: Show all intermediate steps of your favorite sorting algorithm for the array: [2, 1, 8, 9, 4].This task focuses on demonstrating the understanding of the sorting processes.

  • Q5: Bonus Question on Sorting AlgorithmsQuestion: If your array is nearly sorted in ascending order, should you use Selection Sort or Insertion Sort? Why?Instruction: Provide an answer in only one sentence, reinforcing the ability to articulate reasoning clearly and concisely.

Key Concepts to Review

  • Sorting Algorithms:

    • Study common sorting algorithms, emphasizing their methods and efficiency:

      • Insertion Sort: Builds the final sorted array one item at a time, suitable for small datasets.

      • Bubble Sort: Repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order; best used for educational purposes rather than efficiency.

      • Selection Sort: Divides the input list into a sorted and an unsorted region and iteratively selects the smallest element from the unsorted section.

    • Understand the concept of divide and conquer in relation to sorting algorithms, particularly how it applies to algorithms such as Merge Sort and Quick Sort.

  • Time Complexity:

    • Be familiar with average case run times for different sorting algorithms, as understanding efficiency is crucial for data management.

    • Include best, worst, and average case scenarios for key algorithms to fully grasp their performance under various conditions.

  • Characteristics of Sorting Algorithms:

    • Stability: Understand the meaning of stable sorting algorithms (where equal elements maintain their relative order) and the implications for data integrity.

    • Identify suitable use cases for different algorithms based on data arrangements, sizes, and requirements to optimize performance.