Energy consumption, cyclomatic and time complexities of variants of quicksort algorithm: A comparative study

Abstract

The increasing demand for sorting big data, software quality and proliferation of battery-powered computing devices
require efficient sorting algorithms and performance metrics to measure energy consumption and cyclomatic complexity.
The introduction of a faster two- pivot quicksort by Yaroslavskiy in 2009 displaced one pivot-quicksort in Java Runtime
Library 7.However, the two-pivot quicksort algorithm is less efficient for sorting small data sizes. In addition to the Hoare’s
one-pivot and Yaroslavskiy’s two-pivot quicksort algorithms, the Yaroslavskiy’s two-pivot quicksort technique was
modified and implemented with java programming language in this study. Randomized, unsorted data was generated into
arrays ranging from small to large sizes and were subjected to Quicksort algorithm variants up to five times each. The
average time spent by the algorithms to sort the data as well as their energy consumed for the sorting were recorded. The
cyclomatic complexities of the algorithms were computed. The modified two-pivot was found to be time and energy
efficient for all the data sizes. There was a high correlation between time and energy consumed with energy increasing
linearly with time. Hoare’s one pivot quicksort has the best software complexity followed by the modified Yaroslavskiy
two-pivot quicksort algorithm. The modified two-pivot quicksort is recommended for sorting applications deployed on
computing devices where time and energy are critical factors.