SUNY Geneseo Department of Computer Science

Performance of Insertion Sort

Return to List of Lectures

Misc

Return hour exams

Lab 7 due tomorrow

Questions?

Analyzing Loops' Performance

Basic idea is to calculate the number of steps executed as loop runs

This always means summing the number of steps executed in each iteration over all the iterations

• If each iteration executes the same number of steps, this simplifies to multiplying that number by the number of iterations

Best and worst cases are often different

Example: Insertion Sort

    insertionSort( array A )
        for ( i = 1; i < A.length; i++ ) {
            for ( j = i; j > 0 && A[j] < A[j-1]; j-- ) {
                k = A[j-1];
                A[j-1] = A[j];
                A[j] = k;
            }
        }

• Asymptotically, how fast is this?
• Best case
  • Outer loop runs for whole length of array
  • If array already sorted, inner loop does one iteration to see that loop exits
  • n outer iterations times 1 inner = n units of work
  • = Θ(n)
• (n = A.length)
• Beware that best vs worst case should capture effects on execution time other than input size
• Worst case
  • Analysis 1
    • Array of size n is unsorted
    • Body of inner loop executes 3 instructions per iteration
      • 3n execution time
    • Outer loop executes inner loop once per iteration
    • n iterations
    • Therefore Θ(n²) execution time total
• Or...
  • Inner loop repeats i times
  • So 3i steps per iteration of outer loop

Hand out Problem Set 10

Next

Quicksort, an algorithm that improves on the Θ(n²) performance of insertion sort and selection sort

Read sections 10.1 and 10.2

• Main goal being to understand how Quicksort works, read proofs for that purpose, not for their own sake

Hand out Lab 8