Sorting Algorithms, Templates, and Recursion Notes

Sorting Algorithms

• Sorting is a common operation in programming, allowing data to be arranged in a specific order (e.g., numeric scores or alphabetical names).
• Implementing sorting functions like bubble sort typically requires writing separate functions for different data types (e.g., strings vs. floats).
  • Bubble Sort Example:
    • void bubbleSort(String[] arr) {...}
    • void bubbleSort(float[] arr) {...}
• The major overhead comes from having to replicate similar logic for each data type.

Templates in C++

• To alleviate redundancy, use templates to create a generalized sorting function.
  • Template structure example:
    cpp template<typename T> void bubbleSort(T[] arr) {...}
  • T represents a placeholder for any data type (e.g., float, string, double, bool).
• A templated function allows the same algorithm to handle various data types without rewriting the code.

Compile-Time vs Run-Time

• Templates allow for compile-time type verification.
  • The compiler generates the specific code path for each type, reducing the need for run-time checks.
• A comparison with virtual functions illustrates that templates resolve at compile time, while virtual functions resolve at run time.

File Type Polymorphism

• Utilizing templates is a form of polymorphism: one function can operate on different data types efficiently.
• Ensures that the template’s syntax remains consistent while the compiler handles the type-specific details.

STL Containers and Templates

• The Standard Template Library (STL) includes templates like vector, which hold elements of any data type and expand as needed.
  • Example of creating a vector of different data types:

   vector<int> intVec;
   vector<float> floatVec;

• Similar principles apply when creating custom classes that can handle multiple types using templates.
  • Define class:
    cpp template<typename T> class MyList {...};

Recursion Basics

• Recursion is a method of solving problems where a function calls itself with adjusted parameters until a base case is met.
  • Example: Calculating factorials.
    • Factorial Function:
      cpp int factorial(int n) { if (n <= 1) return 1; else return n * factorial(n - 1); }
• Recursion needs three components:
  • Recursive call (the function uses itself),
  • Base case (trivial case for which the answer is known),
  • Reduction operation (progress towards the base case).

Factors Influencing Recursion

• Each recursion creates a new stack frame, which can lead to stack overflow if too deep without a base case (exceeding allowed calls).

Fibonacci Sequence Example

• Recursive implementation of Fibonacci numbers:
  • Defined using smaller Fibonacci calculations.
    • Formula:
      
      F(n) = F(n-1) + F(n-2)
      
  • Base cases needed to avoid infinite recursion:
    • $F(0) = 0$ and $F(1) = 1$

The Towers of Hanoi

• A classic problem suitable for recursive solutions
  • Move disks between rods according to specific rules to avoid larger disks over smaller disks.
  • Recursive logic breaks the problem into smaller equivalent problems, enabling solutions without manually computing all steps.

Summary

• Templates streamline type-specific code for collection handling (like sorting) or data structure definition in programming, enhancing code reusability.
• Recursion simplifies complex problems by reducing them into simpler instances, making it intuitive despite potential computational overhead.