Data Structures: Lists and Sorting Algorithms

Data Structures: Lists and Sorts

• CSC 1061 course covers data structures, specifically lists and sorting algorithms.
• Objectives include designing and implementing collection classes using partially filled arrays, simulating various sorting methods (selection, bubble, insertion, merge, quick, and heap sorts), and explaining runtime advantages of different sorting approaches.

Data Structures: Bags and Lists

• Bag: An unordered collection of values; duplicates are allowed.
• List: An ordered collection of values; duplicates are allowed. List elements must be kept in order.

RemoveByIndex Example (Bag and List)

• Bag Implementation: Removes an element by shifting elements and adjusting size. Returns true if removed, false otherwise. Time complexity can vary depending on implementation.
• List Implementation: Removes an element by shifting elements and adjusting size. Returns true if removed, false otherwise. Time complexity can vary depending on implementation.

Comparing Bags and Lists

• Similarities: Both can store duplicate items.
• Differences: Bags are unordered, lists are ordered. Operations like GetItem, IsEmpty, and Add differ depending on whether the data structure is a Bag or List.

ADT (Abstract Data Type) Class Design Do's and Don'ts

• Do's*

• Constructors: Initialize objects and create members. Classes have data members, for instance setDataMember.

• Getters (accessors): Methods to retrieve data, such as getDataMember.

• Setters (modifiers): Methods to modify data, such as setDataMember.

• toString: Format data for console output as a string.

• toFileString: Format data for file output as a string. Overload operators for comparison. Examples: ==, !=, <, >, <=, >=. Overloaded operators for insertion (<<) and extraction (>>).

• Don'ts*

• Data Structure Input/Output: Avoid reading data from the keyboard in getter functions or having data structure output in a setter function. This could lead to redundant or unnecessary code, causing ambiguity and inefficiency in the program if it's done frequently.

• Redundant Code: Avoid writing duplicate code to avoid redundancy.

• Return Paths: Ensure every function has a valid return path.

• Inline Functions: Avoid using inline functions when there are more than one code instruction. This can lead to efficiency and ambiguity issues in large-scale programs.

Data Structure Class Do's and Don'ts

• Do's:*

• Default Constructor: Initialize an empty collection.

• Invariant Rules: Follow data member rules appropriately.

• Accessor Methods: Define appropriate getter methods for data retrieval. For example, methods to contains, get size, or check isEmpty.

• Mutator Methods: Provide methods to modify data; for instance at, operator[], writeFile (for file output), append, readFile (for file input),removeItem, removeByIndex, and clearAll.

• Don'ts:*

• Data Input/Output: Avoid reading or writing data to/from the keyboard or console within a data structure.

• Redundant Code: Avoid redundant code and ensure that code is consistent throughout the entire program.

• Missing Return Paths: Ensure that all paths in each function lead to a return statement.

• Inline Functions: Avoid exceeding one instruction in inline functions as this may cause program ambiguity.

Sorting Algorithms: Bubble Sort

• Algorithm for sorting.
• First iteration compares and swaps adjacent elements.
• Remaining iterations repeat the process until all elements are sorted.

Sorting Algorithms: Selection Sort

• Algorithm for sorting.
• Sets the first element as minimum (or maximum).
• Compares the minimum with subsequent elements.
• Places the minimum element at the beginning of the unsorted portion.
• Repeats until the list is sorted.

Sorting Algorithms: General Algorithm and BigO Analysis

• Research the general algorithm and BigO analysis of Merge Sort, Insertion Sort, Quick Sort, and Shell Sort using XSortLab, ZyBooks weekly module, and Runestone Tutorials. This should include a deep dive into the specific algorithms. Analyze the time and space complexity of each sorting method.