QuickSort Analysis & AI-Generated Code Evaluation

CS 351 - Data Structures and Algorithms

Author
Affiliation

Lucas P. Cordova, Ph.D.

Willamette University

Abstract

This lecture explores the core of the QuickSort algorithm, focusing on the critical role of partitioning schemes; specifically, the Lomuto and Hoare methods. We compare their design, efficiency, and practical trade-offs, highlighting how partitioning choice impacts performance and implementation complexity. The session also introduces a structured approach to evaluating AI-generated code, emphasizing the importance of critical analysis, prompt engineering, and thorough testing. By the end, you’ll understand how to select and analyze partitioning strategies, and how to apply best practices when leveraging AI tools for algorithm development.

Outline

Part 1: QuickSort Deep Dive

  • Partitioning algorithms comparison
  • Hands-on algorithm exploration
  • Observation and reflection

Part 2: Evaluating AI-Generated Algorithms

  • Critical analysis of AI code
  • Prompt engineering for algorithms
  • Interactive evaluation exercise

Part 1: QuickSort Partitioning Algorithms

Understanding the heart of QuickSort: partitioning

graph TD
    A[Unsorted Array] --> B[Choose Pivot]
    B --> C[Partition]
    C --> D[Elements ≤ pivot]
    C --> E[Elements > pivot]
    D --> F[Recursively sort left]
    E --> G[Recursively sort right]

The Two Champions: Lomuto vs Hoare

Question for Discussion:

What makes a good partitioning algorithm?

Think about:

  • Simplicity of implementation
  • Number of swaps
  • Cache performance
  • Edge case handling

Lomuto Partitioning Scheme

Invented by: Nico Lomuto (1990s)
Key Idea: Single pointer scanning from left to right

def lomuto_partition(arr, low, high):
    pivot = arr[high]  # Choose last element as pivot
    i = low - 1        # Index of smaller element
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

Characteristics:

  • Easy to understand and implement
  • Always places pivot in final position
  • Performs more swaps on average

Hoare Partitioning Scheme

Invented by: Tony Hoare (1961) - Original QuickSort creator
Key Idea: Two pointers moving toward each other

def hoare_partition(arr, low, high):
    pivot = arr[low]  # Choose first (or last) element as pivot
    i = low - 1
    j = high + 1
    
    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
            
        j -= 1
        while arr[j] > pivot:
            j -= 1
            
        if i >= j:
            return j
            
        arr[i], arr[j] = arr[j], arr[i]

Characteristics:

  • Fewer swaps on average
  • Pivot not necessarily in final position
  • More complex logic

Comparison Table

Aspect Lomuto Hoare
Simplicity High Medium
Swaps (average) More Fewer
Pivot placement Exact final position Approximate
Cache performance Good Better
Edge cases Easier to handle More complex

Exploration Time!

Activity 1: Algorithm Visualization

Visit: https://courses.lpcordova.com/cs351/algoviz/quicksort.html

Your Mission:

  1. Test QuickSort with Hoare partitioning

Try these scenarios:

  • Randomly generated data (default settings)
  • Use own data option
    • Already sorted array: [1, 2, 3, 4, 5, 6, 7, 8]
    • Reverse sorted: [8, 7, 6, 5, 4, 3, 2, 1]
    • Random: [3, 7, 1, 9, 4, 6, 8, 2]
    • Duplicates: [5, 3, 5, 1, 5, 7, 5]

Reflection & Observations

Discussion Questions:

Group Discussion: What patterns did you notice?

Specific observations to consider:

  • How did performance differ with sorted vs random data?
  • Any unexpected behaviors or peculiarities?

Key Insights from QuickSort Analysis

Performance Characteristics:

graph LR
    A[Input Type] --> B{Partitioning Quality}
    B -->|Good| C["O(n log n)"]
    B -->|Poor| D["O(n²)"]
    
    E[Pivot Selection] --> B
    F[Data Distribution] --> B

Real-world implications:

  • Choice of partitioning affects constant factors and simplicity
  • Pivot selection strategy matters more than partitioning scheme
  • Understanding algorithms deeply helps in optimization

Part 2: Evaluating AI-Generated Algorithms

The New Reality: AI can generate algorithm code instantly, but can we trust it?

Objectives:

  • Develop critical evaluation skills
  • Learn effective prompt engineering
  • Understand AI limitations in algorithmic thinking

Case Study: AI-Generated Merge Sort

Scenario: You ask an AI to implement Merge Sort

Your prompt: “Write a merge sort algorithm in Python”

Let’s see what we might get and how to evaluate it…

AI Response Example

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Evaluation Framework

The TRACE Method for Algorithm Evaluation:

Time Complexity Analysis
Readability and Structure
Accuracy and Correctness
Corner Cases and Edge Handling
Efficiency and Space Usage

T - Time Complexity Analysis

Questions to ask:

  • What’s the theoretical time complexity?
  • Does the implementation match the expected complexity?
  • Are there hidden inefficiencies?

For our Merge Sort: - Expected: O(n log n) - Implementation: ✓ Correct recursive structure - Hidden issue: Array slicing creates copies (Python-specific)

R - Readability and Structure

Code Quality Checklist:

  • Clear variable names
  • Logical function decomposition
  • Appropriate comments
  • Consistent style

Our example assessment:

  • ✓ Clear function separation
  • ✓ Meaningful variable names
  • ⚠️ Missing docstrings
  • ✓ Clean, readable structure

A - Accuracy and Correctness

Testing Strategy:

def test_merge_sort():
    # Basic functionality
    assert merge_sort([3, 1, 4, 1, 5]) == [1, 1, 3, 4, 5]
    
    # Edge cases
    assert merge_sort([]) == []
    assert merge_sort([1]) == [1]
    
    # Duplicates
    assert merge_sort([2, 2, 2]) == [2, 2, 2]
    
    # Already sorted
    assert merge_sort([1, 2, 3, 4]) == [1, 2, 3, 4]

C - Corner Cases and Edge Handling

Critical scenarios to test:

  • Empty arrays
  • Single element arrays
  • All elements identical
  • Already sorted (best case)
  • Reverse sorted (worst case for some algorithms)
  • Very large datasets

E - Efficiency and Space Usage

Space Complexity Analysis:

graph TD
    A[Merge Sort Space] --> B[Recursive Call Stack]
    A --> C[Temporary Arrays]
    B --> D["O(log n)"]
    C --> E["O(n)"]
    D --> F["Total: O(n)"]
    E --> F

Python-specific considerations:

  • List slicing creates copies
  • Memory overhead for temporary lists
  • Garbage collection impact

Exercise: Prompt Engineering for Algorithms

Activity 2: Crafting Better Prompts

Basic Prompt: “Write a heap sort algorithm”

Enhanced Prompt: “Write an in-place heap sort algorithm in Python with the following requirements:

  • Include time and space complexity analysis
  • Add comprehensive docstrings
  • Handle edge cases (empty array, single element)
  • Include test cases
  • Optimize for minimal memory usage
  • Add comments explaining the heapify process”

Your turn: Work in pairs to improve this prompt for bubble sort

Prompt Engineering Strategies

The CLEAR Framework:

Context - Provide background and constraints
Length - Specify desired code length/complexity
Examples - Include input/output examples
Analysis - Request complexity analysis
Requirements - List specific technical requirements

Example: CLEAR Applied

Context: “I’m implementing sorting algorithms for a computer science course”

Length: “Write a concise but well-documented implementation”

Examples: “Should sort [64, 34, 25, 12, 22, 11, 90] to [11, 12, 22, 25, 34, 64, 90]”

Analysis: “Include time and space complexity in comments”

Requirements: “Use Python, include error handling, optimize for readability”

Red Flags in AI-Generated Code

Watch out for:

  • Infinite recursion in recursive algorithms
  • Off-by-one errors in array indexing
  • Memory leaks in languages requiring manual management
  • Incorrect complexity claims in comments
  • Missing edge case handling
  • Non-optimal implementations that work but are inefficient

Interactive Evaluation Exercise

Activity 3: Code Review Challenge

I’ll show you an AI-generated selection sort. Use the TRACE method to evaluate it:

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Work in groups:

  • Apply TRACE method
  • Identify strengths and weaknesses
  • Suggest improvements

Best Practices for AI Algorithm Assistance

DO:

  • Use AI for initial implementation ideas
  • Ask for multiple approaches
  • Request explanation of design choices
  • Verify with your own test cases
  • Cross-reference with authoritative sources

DON’T:

  • Blindly trust AI output
  • Skip manual testing
  • Ignore complexity analysis
  • Copy without understanding
  • Forget to optimize for your specific use case

Practical Workflow

graph TD
    A[Define Problem] --> B[Craft Detailed Prompt]
    B --> C[Get AI Response]
    C --> D[Apply TRACE Method]
    D --> E{Acceptable?}
    E -->|No| F[Refine Prompt]
    E -->|Yes| G[Test Thoroughly]
    F --> C
    G --> H[Optimize if Needed]
    H --> I[Document and Deploy]

Summary: Key Takeaways

QuickSort Insights:

  • Partitioning choice affects performance constants
  • Hoare generally more efficient, Lomuto more intuitive
  • Understanding internals helps optimization decisions

AI Algorithm Evaluation:

  • Always apply critical analysis (TRACE method)
  • Good prompts yield better results (CLEAR framework)
  • AI is a tool, not a replacement for understanding
  • Testing and verification are non-negotiable

Next Steps

For your QuickSort assignment:

  1. Apply today’s knowledge to analyze your implementation
  2. Use TRACE method to evaluate any AI assistance
  3. Test thoroughly with various input types
  4. Document your analysis of partitioning choice

Questions to ponder:

  • How might modern library implementations handle these trade-offs?
  • What other factors might affect sorting performance in practice?
  • How can profiling tools help validate theoretical analysis?