Cyclomatic complexity

Statement

• Consider the following quicksort sorting algorithm:

QUICKSORT(A, p, r)

  if p < r
    then q ← PARTITION(A, p, r)
    QUICKSORT(A, p, q − 1)
    QUICKSORT(A, q + 1, r)



PARTITION(A, p, r)
    x ← A[r]
    i ← p − 1
    for j ← p to r − 1
         if A[j] ≤ x
            then i ← i + 1
            exchange A[i] ↔ A[j]

    exchange A[i + 1] ↔ A[r]
    return i + 1

questions

1. Draw the flowchart of the above algorithm.
2. Draw the corresponding graph and label the nodes as n1, n2, … and edges as e1, e2, …
3. Calculate the cyclomatic complexity of the above algorithm

Solution

1. Draw the flowchart of the above algorithm.

2. Draw the corresponding graph and label the nodes as n1, n2, … and edges as e1, e2, …

3. Calculate the cyclomatic complexity of the above algorithm

• we can calculate the cyclomatic complexity according to the law V(G) = e - n + 2 (Marsic, 2012, p.231) where n is the number of nodes and e is the number of edges.
• according to the graphs in the previous question, n = 13, e = 18.
• V(G) = e - n + 2 = 18 - 13 + 2 = 7
• cyclomatic complexity = 7

References

• Marsic, I. (2012). Software engineering. Rutgers Unversity. https://www.ece.rutgers.edu/~marsic/books/SE/book-SE_marsic.pdf