What is the cyclomatic complexity of Selection sort?

Before we go ahead and calculate the cyclomatic complexity of selection sort, let us revise cyclomatic complexity in general.

Cyclomatic complexity

Cyclomatic complexity is a metric for calculating the number of linearly independent paths that run through a software program. Moreover, it helps us determine the complexity of the program and provides us with an internal view of the codehence, why it is referred to as structural complexity. The higher the cyclomatic complexity, the more complex the code.

The steps used to calculate cyclomatic complexity include:

  • Draw a Control flow graph(CFG)CFG is a graph notation representation of all paths that could be traversed through a software program during execution. of the program. The arrows in the graph indicate the flow of control while the nodes represent actions or the commands of the program.
  • Determine the cyclomatic complexity. There are several ways this can be done:

  1. Cyclomatic Complexity = Edges - Nodes + 2p

  2. Cyclomatic Complexity = # of Regions in the CFG

  3. Cyclomatic Complexity = # of Predicate Nodes + 1

where:

  • p represents connected componentFor a single program or sub-routine, the value of p is always equal to 1
  • Predicate nodes are the ones that contain conditionsHint: Contains Two Outgoing Edges. We won’t include the nodes with more than two edges as predicate nodes.
  • Region is an enclosed area or a cycle in the graph. Other than that there is also a common region - the external region.

Cyclomatic complexity of selection sort

The following is the code for selection sort. We can draw a control flow graph for this program from the code and each line’s corresponding line number.

void SelectionSort(int array1[]) {
	 int size = array1.length; 
	 for (int i = 0; i < size-1; i++) {  
		 int minIndex = i;
		 for (int j = i+1; j < size; j++)
			if (array1[j] < array1[minIndex])
				minIndex = j; 
		int temp = array1[minIndex];
		array1[minIndex] = array1[i]; 
		array1[i] = temp; 
	}
}

CFG for sort

Nodes have been labeled in the diagram, with respect to the code lines, for clear understanding.

Control Flow Graph of the Sort Function

Predicate Nodes are highlighted above in red in the CFG, i.e., the red colored nodes are predicate nodes. Pink-colored nodes represent the entry and exit points.

The number of regions in the CFG are:

  • 3 --> 4 --> 5 --> 8 --> 9 --> 10 --> 3
  • 5 --> 6 --> 5
  • 5 --> 6 --> 7 --> 5
  • Common External region

Cyclomatic Complexity

Looking at the above CFG

  1. Edges = 13, Nodes = 11, p = 1

Hence,

Cyclomatic Complexity = 13 - 11 + 2*1 = 4

  1. Number of Regions in the CFG = 4

Hence,

Cyclomatic Complexity = 4

  1. Predicate Nodes = 3

Hence,

Cyclomatic Complexity = 3 + 1 = 4

As demonstrated, all the formulas yield the same results. You may use any one of these to determine the cyclomatic complexity of selection sort. However, to sum it all up, the cyclomatic complexity of selection sort is 4.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)