Time Complexity Comparison Sheet Of Elementary Sorting Algorithms

It is always good to sharpen your blade from time to time. Data structures and algorithms is my sword.

Recently, I visited all the elementary sorting algorithms. And it is always fun to understand the complexity and mindset behind it.

This time I thought of writing a small program to run all the algorithms against a variable set of inputs to generate the time complexity chart for it.

And this chart is almost exactly matched with the calculations. So, it also gives verification of the process used to calculate the time complexity of a program.

I won’t take a lot of your time, below is the elementary sorting algorithms time complexity chart.

You can also download the pdf version of the same from here.

Here is the code snippet that is used for generating the above Sorting Comparision chart.

	import com.bma.algorithms.sort.elementary.Util;
	import java.io.BufferedWriter;
	import java.io.File;
	import java.io.FileWriter;
	import java.io.IOException;
	import java.util.Collections;
	import java.util.LinkedList;
	import java.util.List;
	import java.util.Random;
	import static java.util.Arrays.copyOf;
	public class SortingAlgorithmComparision {
	private int maxInputArrSize;
	public SortingAlgorithmComparision(int maxInputArrSize) {
	this.maxInputArrSize = maxInputArrSize;
	}
	private List<String> compare(int totalRun) throws InterruptedException {
	List<Thread> workerThreads = new LinkedList<>();
	List<String> stats = Collections.synchronizedList(new LinkedList<>());
	stats.add("Input Size,Quick,Merge,BottomUpMerge,Shell,Insertion,Selection" + System.lineSeparator());
	Random rand = new Random();
	for (int i = 0; i < totalRun; i++) {
	int inputSize = rand.nextInt(maxInputArrSize);
	int input[] = Util.generateUnsortedArray(inputSize);
	Thread t = new Thread(() -> {
	StringBuilder sb = new StringBuilder();
	sb.append(inputSize).append(",")
	.append(Sort.quickSort(copyOf(input, input.length))).append("ms,")
	.append(Sort.mergeSort(copyOf(input, input.length))).append("ms,")
	.append(Sort.bottomUpMergeSort(copyOf(input, input.length))).append("ms,")
	.append(Sort.shellSort(copyOf(input, input.length))).append("ms,")
	.append(Sort.insertionSort(copyOf(input, input.length))).append("ms,")
	.append(Sort.selectionSort(copyOf(input, input.length))).append("ms,")
	.append(System.lineSeparator());
	stats.add(sb.toString());
	});
	t.start();
	Util.println(String.format("Thread<%d> started!", t.getId()));
	workerThreads.add(t);
	}
	for (Thread workerThread : workerThreads)
	workerThread.join();
	return stats;
	}
	public void generateReport(int totalRun, String outputFileName) throws IOException, InterruptedException {
	try (BufferedWriter bw = new BufferedWriter(new FileWriter(new File(outputFileName)))) {
	for (String line : compare(totalRun))
	bw.write(line);
	}
	}
	}

view raw SortingAlgorithmComparision.java hosted with by GitHub

The code is pretty much self-explanatory. But I will try to take out some time to write and talk about the entire code.

Let me know your thoughts on the same.

Do not forget to explore Programming Category.