Abstract

Introduction

At the very foundation of programming is a simple but powerful necessity: sorting things out. Sorting is one of the most useful tools for a programmer, taking jumbled data and turning it into organized information that is easy to locate, examine, and maximize. For any code writer, having knowledge of the different ways to sort isn't abstract — it's practical. Knowing which technique to employ can be the difference between a speedy application and a slow one, particularly as data volume increases.

This project answers one central question of this field: in practice, how do different sorting algorithms work? We're bridging theory and practice by comparing how long it takes to run each one. The goal is to demonstrate that an algorithm's inherent complexity has a direct impact on real-world speed, and how our choices as programmers affect the behavior of a program.

To achieve this, we designed a special list to manage the enrollments of the students into courses. We took the data and sorted it four times through regular sorts: the inefficient but simple Selection and Insertion Sorts, and the more sophisticated divide-and-conquer Merge Sort and Quick Sort. We also timed each one in order to see how their theoretical performance stacked up against their actual speed. Ultimately, this project serves as a practical example.

High-Level Solution / System Design Overview

This application is meant to develop a Prince Sultan University-specific system that takes the record of the student's course registration and computes the demand for each course accordingly. Additionally, this system undergoes three major phases:

Overall, it results in a more efficient way of course registration management while enhancing the student experience with a data-driven and intuitive registration system.

Asymptotic Performance Analysis

The Writing and Reading Running Time

The file reading and writing operations have a linear time complexity of O(n), where n is the number of registrations. Each record is processed exactly once during reading, and each record is written exactly once during the output phase.

The Processing (Demand Score Computation) Run Time

The demand score calculation for all registrations has a time complexity of O(n). The system iterates through each node in the linked list exactly once, performing a constant-time calculation for each student's demand score based on the four criteria.

The Sorting Running Time

Selection Sort

Selection Sort has a time complexity of O(n²). The algorithm uses two nested loops: the outer loop runs n times, and for each iteration, the inner loop searches through the remaining unsorted elements to find the maximum value. This results in approximately n²/2 comparisons.

Insertion Sort

Insertion Sort also has a time complexity of O(n²) in the worst case. Starting from the second element, each element is compared with all elements to its left and inserted in the correct position. In the worst case (reverse sorted array), this results in n²/2 comparisons.

Merge Sort

Merge Sort has a time complexity of O(n log n). The algorithm recursively divides the array into two halves until base cases are reached, then merges the sorted halves. The division creates log n levels, and each level requires O(n) work to merge.

Quick Sort

Quick Sort has an average time complexity of O(n log n). The algorithm selects a pivot element and partitions the array around it, then recursively sorts the partitions. With good pivot selection, the array is divided roughly in half at each level, creating log n levels with O(n) work per level.

Runtime Measurement

The following table presents the actual runtime measurements for all operations performed by the system on a dataset of 3,432 registrations:

Interpretation of Results

The results in the runtime table were obtained using a dataset of 3,432 registrations. Stating the dataset is significant because it places the measured runtimes in context and enables the performance results to be fairly interpreted. Since algorithmic efficiency depends on input size, reporting that all timings were measured with 3,432 records shows that analysis was conducted under realistic and standard conditions.

This also allows fair comparison between the sorting algorithms and makes it easier to reproduce in the event that the same dataset is used again. The results clearly demonstrate the practical impact of theoretical time complexity:

• Linear operations (O(n)): File reading, demand score calculation, and file writing all completed in under 110ms, demonstrating efficient linear-time performance.
• Quadratic algorithms (O(n²)): Selection Sort (45ms) and Insertion Sort (26ms) performed reasonably well on this dataset size, though their performance would degrade significantly with larger datasets.
• Linearithmic algorithms (O(n log n)): Merge Sort (17ms) and Quick Sort (22ms) showed superior performance, confirming their efficiency for larger datasets. These algorithms are clearly the best choice for production systems handling thousands of records.

The results validate the theoretical complexity analysis and demonstrate why algorithm selection is crucial for system performance, especially as data scales.

Teamwork Contribution and Coordination

This project was completed in teamwork by Shoug Alomran and Layan Bindayel under the supervision of Dr. Najla Althuniyan. The two members worked together during the development, keeping each other posted and sharing the responsibilities to ensure smooth flow and integration.

Layan Bindayel

Layan coordinated and organized the project. She created the report template, drew up the document outline, and divided the work evenly between the two members. Layan did the implementation of the lower-level system components, including:

• Node.java
• LinkedList.java
• FileService.java
• Comparators.java

Layan wrote the High-Level Solution and Asymptotic Performance Analysis section of the report, explaining the overall design and theoretical performance of the algorithms.

Shoug Alomran

Shoug completed the analysis and runtime components of the project. She implemented:

• Input Validator Class
• Demand Scorer Class
• Sorting algorithms (SelectionSort, InsertionSort, MergeSort, and QuickSort)
• Bench Marker Class
• Timer Class

Shoug also completed the Runtime Measurement section of the report, including measuring actual runtimes, generating tables, and including screenshots to illustrate the performance of the system.

Collaborative Work

Both partners collaborated on Main Class, bringing all components together in one program. Layan did data input and list integration, while Shoug did processing, sorting, and benchmarking phases. Together, they tested, debugged, and validated the entire system, demonstrating overall teamwork, coordination, and fair contribution.

Conclusion

In essence, the results of this project confirmed that the algorithms used behaved as theoretical and empirical expectations. Runtime was utilized as a metric to determine that Merge Sort and Quick Sort were the fastest in terms of runtime because of their sound O(n log n) complexity, with Selection Sort and Insertion Sort being much slower, as would be expected from their O(n²) complexity. That theoretical consideration would match actual results in such a manner ensures system implementation and design correctness and optimality.

Along the way, we were taught a valuable lesson in the trade-off between simplicity and efficiency. The more straightforward algorithms that we have such as Selection Sort and Insertion Sort are easier to comprehend and implement but thus adequate for small data or teaching purposes. Their performance is traded off, however, with larger input size, to the more complicated divide-and-conquer approach used by Merge Sort and Quick Sort.

This project expressed extremely well the direct relation of algorithmic efficiency to program performance in real-world applications. The system can be adapted to take actual registration data directly from university databases to analyze live course demand patterns in the future.

Any other features, such as the graphical user interface to display the demand scores, machine verification of the input data, or inclusion of yet another complicated algorithm like Heap Sort or Counting Sort, would also make it all the more performance-driven and user-friendly. Overall, the project accomplished what it intended to do — coming up with an effective system that demonstrates how an algorithm's design is incorporated into data structures and run-time behavior in the real world for a learning context.

References and Resources

1. Alomran, S., & Bindayel, L. (2025). CS210 Project, Student Course Registration Analysis [Computer software]. GitHub. https://github.com/Shoug-Alomran/CS210-Project-Linked-List-Implementation-and-Runtime-Analysis
2. GeeksforGeeks. (n.d.). Sorting Algorithms – Complete Guide. Retrieved October 2025. https://www.geeksforgeeks.org/sorting-algorithms/
3. W3Schools. (n.d.). Java BufferedWriter. Retrieved October 2025. https://www.w3schools.com/java/java_bufferedwriter.asp
4. W3Schools. (n.d.). Java BufferedReader. Retrieved October 2025. https://www.w3schools.com/java/java_bufferedreader.asp
5. W3Schools. (n.d.). Java Files. Retrieved October 2025. https://www.w3schools.com/java/java_files.asp
6. Alsomali, Y., & Alsubaie, H. (n.d.). Prince Sultan University Parking Intelligent System Report. CS210: Data Structures and Algorithms, Dr. Najla Althuniyan, Prince Sultan University.

Appendix A: Flow Chart Illustration

Appendix B: Full Java Code Implementation

Main Class

import java.util.Arrays;

public class Main {
public static void main(String[] args) {
Timer timer = new Timer();

    System.out.println("Starting file reading...");
    timer.start();
    LinkedList registrations = InputValidator.readAndValidateFile("Input.txt");
    timer.stop();
    System.out.println("File reading completed in: " + timer.getElapsedTimeMillis() + " ms");
    System.out.println("Successfully read " + registrations.size + " registrations.");

    System.out.println("Starting demand score calculations...");
    timer.start();
    calculateAllDemandScores(registrations);
    timer.stop();
    System.out.println("Demand score calculations completed in: " + timer.getElapsedTimeMillis() + " ms");

    Registration[] array = registrations.convToArray();

    System.out.println("Writing unsorted data to file...");
    timer.start();
    FileService.writeRegistrationsToFile(array, "Output.txt");
    timer.stop();
    System.out.println("File writing completed in: " + timer.getElapsedTimeMillis() + " ms");

    System.out.println("Starting sorting algorithms...");
    Benchmarker.runAllSorts(array);
    System.out.println("All sorting completed and results saved.");

    System.out.println("\n--- ADDITIONAL COMPARATOR SORTING ---");
    Registration[] idSorted = registrations.convToArray();
    Arrays.sort(idSorted, Comparators.by_ID);
    FileService.writeRegistrationsToFile(idSorted, "Sorted_By_ID.txt");

    Registration[] courseSorted = registrations.convToArray();
    Arrays.sort(courseSorted, Comparators.by_CourseCode);
    FileService.writeRegistrationsToFile(courseSorted, "Sorted_By_Course.txt");

    Registration[] levelSorted = registrations.convToArray();
    Arrays.sort(levelSorted, Comparators.by_Level);
    FileService.writeRegistrationsToFile(levelSorted, "Sorted_By_Level.txt");

    Registration[] timeSorted = registrations.convToArray();
    Arrays.sort(timeSorted, Comparators.by_RegTime);
    FileService.writeRegistrationsToFile(timeSorted, "Sorted_By_Time.txt");
}

public static void calculateAllDemandScores(LinkedList registrations) {
    Node current = registrations.head;
    while (current != null) {
        DemandScorer.computeDemandScore(current.studData);
        current = current.next;
    }
}
}

Sorter Interface

public interface Sorter {
    void sort(Registration[] a);
    String name();
}

Node Class

public class Node {
    Registration studData;
    Node next;

    public Node(Registration studData) {
        this.studData = studData;
        this.next = null;
    }
}

Timer Class

public class Timer {
    private long startTime;
    private long endTime;

    public void start() { startTime = System.currentTimeMillis(); }
    public void stop()  { endTime   = System.currentTimeMillis(); }
    public long getElapsedTimeMillis() { return endTime - startTime; }
}

LinkedList Class

public class LinkedList {
    Node head;
    int size;
    Node tail;

    public void insertNodeAtHead(Registration data) {
        Node newNode = new Node(data);
        if (head == null) { head = newNode; tail = newNode; size++; return; }
        newNode.next = head;
        head = newNode;
        size++;
    }

    public void insertNodeAtTail(Registration data) {
        Node newNode = new Node(data);
        if (head == null) { head = newNode; tail = newNode; size++; return; }
        tail.next = newNode;
        tail = newNode;
        size++;
    }

    public void deleteNodeByValue(Registration data) {
        if (head == null) return;
        if (head.studData.equals(data)) { head = head.next; size--; return; }
        Node prev = head, curr = head.next;
        while (curr != null) {
            if (curr.studData.equals(data)) { prev.next = curr.next; size--; return; }
            prev = curr; curr = curr.next;
        }
    }

    public boolean searchKey(Registration data) {
        Node temp = head;
        while (temp.next != null) {
            if (temp.studData.equals(data)) return true;
            temp = temp.next;
        }
        return false;
    }

    public void displayLinkedList() {
        Node temp = head;
        while (temp != null) { System.out.println(temp.studData); temp = temp.next; }
    }

    public Registration[] convToArray() {
        int size = 0;
        Node temp = head;
        while (temp != null) { size++; temp = temp.next; }
        Registration[] dataArray = new Registration[size];
        temp = head;
        int index = 0;
        while (temp != null) { dataArray[index++] = temp.studData; temp = temp.next; }
        return dataArray;
    }
}

Benchmarker Class

public class Benchmarker {
    private static Registration[] makeCopy(Registration[] original) {
        Registration[] copy = new Registration[original.length];
        for (int i = 0; i < original.length; i++) copy[i] = original[i];
        return copy;
    }

    public static void runAllSorts(Registration[] originalArray) {
        System.out.println("--- RUNNING ALL SORTS ---");
        Timer timer = new Timer();

        Registration[] copy1 = makeCopy(originalArray);
        timer.start(); new SelectionSort().sort(copy1); timer.stop();
        FileService.writeRegistrationsToFile(copy1, "Sorted_Output_SS.txt");
        System.out.println("Selection Sort: " + timer.getElapsedTimeMillis() + " ms");

        Registration[] copy2 = makeCopy(originalArray);
        timer.start(); new InsertionSort().sort(copy2); timer.stop();
        FileService.writeRegistrationsToFile(copy2, "Sorted_Output_IS.txt");
        System.out.println("Insertion Sort: " + timer.getElapsedTimeMillis() + " ms");

        Registration[] copy3 = makeCopy(originalArray);
        timer.start(); new MergeSort().sort(copy3); timer.stop();
        FileService.writeRegistrationsToFile(copy3, "Sorted_Output_MS.txt");
        System.out.println("Merge Sort: " + timer.getElapsedTimeMillis() + " ms");

        Registration[] copy4 = makeCopy(originalArray);
        timer.start(); new QuickSort().sort(copy4); timer.stop();
        FileService.writeRegistrationsToFile(copy4, "Sorted_Output_QS.txt");
        System.out.println("Quick Sort: " + timer.getElapsedTimeMillis() + " ms");
    }
}

Comparator Class

import java.util.Comparator;

public final class Comparators {
    private Comparators() {}

    public static final Comparator<Registration> by_ID = (r1, r2) ->
        r1.getStudentID().compareTo(r2.getStudentID());

    public static final Comparator<Registration> by_CourseCode = (r1, r2) ->
        r1.getCourseID().compareTo(r2.getCourseID());

    public static final Comparator<Registration> by_Level = (r1, r2) ->
        Integer.compare(r1.getAcademicLevel(), r2.getAcademicLevel());

    public static final Comparator<Registration> by_RegTime = (r1, r2) ->
        Integer.compare(r1.getRegTime(), r2.getRegTime());

    public static Comparator<Registration> getComparator(String criterion) {
        switch (criterion.toLowerCase()) {
            case "id":     return by_ID;
            case "course": return by_CourseCode;
            case "level":  return by_Level;
            case "time":   return by_RegTime;
            default: throw new IllegalArgumentException("Unknown: " + criterion);
        }
    }
}

Registration Class

public class Registration {
    private String studentID;
    private String courseID;
    private int academicLevel;
    private int regTime;
    private double studDemandScore;

    public Registration(String studentID, String courseID, int academicLevel,
                        int regTime, double studDemandScore) {
        this.studentID = studentID;
        this.courseID = courseID;
        this.academicLevel = academicLevel;
        this.regTime = regTime;
        this.studDemandScore = 0;
    }

    public String getStudentID()               { return studentID; }
    public void   setStudentID(String v)       { this.studentID = v; }
    public String getCourseID()                { return courseID; }
    public void   setCourseID(String v)        { this.courseID = v; }
    public int    getAcademicLevel()           { return academicLevel; }
    public void   setAcademicLevel(int v)      { this.academicLevel = v; }
    public int    getRegTime()                 { return regTime; }
    public void   setRegTime(int v)            { this.regTime = v; }
    public double getStudDemandScore()         { return studDemandScore; }
    public void   setStudDemandScore(double v) { this.studDemandScore = v; }

    @Override
    public String toString() {
        return studentID + ";" + courseID + ";" + academicLevel + ";" +
               regTime + ";" + Math.round(studDemandScore) + ";";
    }
}

DemandScorer Class

public class DemandScorer {
    public static void computeDemandScore(Registration reg) {
        double score = 50;
        score = applyStudentClassMultiplier(score, reg.getAcademicLevel());
        score = applyTimePreferenceMultiplier(score, reg.getRegTime());
        score = applyCoursePriority(score, reg.getCourseID());
        score = Math.round(score);
        score = Math.max(0, Math.min(100, score));
        reg.setStudDemandScore(score);
    }

    private static double applyStudentClassMultiplier(double score, int studentClass) {
        if      (studentClass == 1) score *= 0.75;
        else if (studentClass == 2) score *= 0.90;
        else if (studentClass == 3) score *= 1.10;
        else if (studentClass == 4) score *= 1.25;
        else if (studentClass == 5) score *= 1.5;
        return score;
    }

    public static double applyTimePreferenceMultiplier(double score, int time) {
        if      (time >= 6  && time < 8 ) score += 5;
        else if (time >= 8  && time < 10) score += 10;
        else if (time >= 10 && time < 12) score += 5;
        else if (time >= 12 && time < 14) score += 0;
        else if (time >= 14 && time < 16) score -= 5;
        else if (time >= 16 && time < 20) score -= 10;
        else                              score -= 15;
        return score;
    }

    private static double applyCoursePriority(double score, String courseID) {
        char lastChar = courseID.charAt(courseID.length() - 1);
        if (Character.isDigit(lastChar)) {
            int lastDigit = Integer.parseInt(String.valueOf(lastChar));
            score += (lastDigit % 2 == 1) ? 20 : -10;
        }
        return score;
    }
}

InputValidator Class

import java.io.*;
import java.util.*;

public class InputValidator {
    private static Set<String> validCourses = new HashSet<>();

    public static boolean isValidFilePath(String filePath) {
        File file = new File(filePath);
        return file.exists() && file.canRead();
    }

    public static LinkedList readAndValidateFile(String input) {
        LinkedList registrations = new LinkedList();
        if (!isValidFilePath(input)) {
            System.out.println("ERROR: File '" + input + "' not found or not readable.");
            return registrations;
        }
        try (BufferedReader list = new BufferedReader(new FileReader(input))) {
            String line;
            while ((line = list.readLine()) != null) {
                String[] parts = line.split(";");
                if (parts.length != 4) { System.out.println("Invalid entry: " + line); continue; }
                String studentID = parts[0];
                String courseID  = parts[1];
                try {
                    int academicLevel = Integer.parseInt(parts[2]);
                    int studyTime     = Integer.parseInt(parts[3]);
                    if (studentID.isEmpty() || courseID.isEmpty()) continue;
                    if (studentID.length() != 7 && studentID.length() != 5) continue;
                    if (academicLevel < 1 || academicLevel > 5) continue;
                    if (studyTime < 0 || studyTime > 23) continue;
                    validCourses.add(courseID);
                    registrations.insertNodeAtTail(new Registration(studentID, courseID, academicLevel, studyTime, 0));
                    System.out.println("VALID: " + line);
                } catch (NumberFormatException e) { System.out.println("Invalid number: " + line); }
            }
        } catch (IOException e) { System.out.println("Error reading file: " + e.getMessage()); }
        return registrations;
    }
}

FileService Class

import java.io.*;

public class FileService {
    public static LinkedList readRegistrationsFromFile(String filename) {
        return InputValidator.readAndValidateFile(filename);
    }

    public static void writeRegistrationsToFile(Registration[] array, String filename) {
        try (BufferedWriter writer = new BufferedWriter(new FileWriter(filename))) {
            for (Registration reg : array) {
                if (reg != null) { writer.write(reg.toString()); writer.newLine(); }
            }
            System.out.println("Registrations successfully written to " + filename);
        } catch (IOException e) {
            System.out.println("An error occurred: " + e.getMessage());
        }
    }
}

Insertion Sort Class

public class InsertionSort implements Sorter {
    @Override
    public void sort(Registration[] array) {
        for (int i = 1; i < array.length; i++) {
            Registration current = array[i];
            double currentScore  = current.getStudDemandScore();
            int j = i - 1;
            while (j >= 0 && array[j].getStudDemandScore() < currentScore) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = current;
        }
    }
    @Override public String name() { return "Insertion Sort"; }
}

Merge Sort Class

public class MergeSort implements Sorter {
    @Override
    public void sort(Registration[] array) {
        if (array.length < 2) return;
        int mid = array.length / 2;
        Registration[] left  = new Registration[mid];
        Registration[] right = new Registration[array.length - mid];
        for (int i = 0;   i < mid;           i++) left[i]       = array[i];
        for (int i = mid; i < array.length;   i++) right[i - mid] = array[i];
        sort(left); sort(right);
        merge(array, left, right);
    }

    private void merge(Registration[] result, Registration[] left, Registration[] right) {
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length)
            result[k++] = (left[i].getStudDemandScore() >= right[j].getStudDemandScore())
                          ? left[i++] : right[j++];
        while (i < left.length)  result[k++] = left[i++];
        while (j < right.length) result[k++] = right[j++];
    }
    @Override public String name() { return "Merge Sort"; }
}

Quick Sort Class

public class QuickSort implements Sorter {
    @Override
    public void sort(Registration[] array) { quickSort(array, 0, array.length - 1); }

    private void quickSort(Registration[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high);
            quickSort(array, low, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, high);
        }
    }

    private int partition(Registration[] array, int low, int high) {
        double pivot = array[high].getStudDemandScore();
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (array[j].getStudDemandScore() >= pivot) {
                i++;
                Registration temp = array[i]; array[i] = array[j]; array[j] = temp;
            }
        }
        Registration temp = array[i + 1]; array[i + 1] = array[high]; array[high] = temp;
        return i + 1;
    }
    @Override public String name() { return "Quick Sort"; }
}

Selection Sort Class

public class SelectionSort implements Sorter {
    @Override
    public void sort(Registration[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int maxIndex = i;
            for (int j = i + 1; j < array.length; j++)
                if (array[j].getStudDemandScore() > array[maxIndex].getStudDemandScore())
                    maxIndex = j;
            Registration temp = array[i]; array[i] = array[maxIndex]; array[maxIndex] = temp;
        }
    }
    @Override public String name() { return "Selection Sort"; }
}

Appendix C: Full Run Pictures