CPT212 - Radix Sort: Integer and String Analysis

This repository contains the implementation and complexity analysis of Radix Sort for both integers and strings, as part of the CPT212 Design and Analysis of Algorithms assignment.

📝 Project Overview

The project explores Radix Sort, a non-comparative sorting algorithm that sorts elements digit by digit. Two implementations are provided:

• Integer Sort: Sorts positive integers.
• String Sort: Sorts lowercase alphabetical words.

A complexity analysis was performed by measuring the number of primitive operations against increasing input sizes (5, 7, 10, and 20) to experimentally determine the time complexity.

⚙️ How to Run

The sorting algorithms are written in Java.

1. Navigate to the src directory.
2. Compile the Java files:

   javac IntegerSort.java
   javac StringSort.java

3. Run the programs:

   java IntegerSort
   java StringSort

📊 Complexity Analysis Results

The analysis confirms that Radix Sort has a time complexity of $O(n \cdot k)$, where n is the number of elements and k is the number of digits (for integers) or the length of the longest string.

The String Sort algorithm shows a steeper growth in operations compared to Integer Sort, as k (string length) can grow more significantly than the number of digits in an integer.